Recursion in Prolog - reversing a list-CodePudding

I'm having quite a bit of trouble with recursion in prolog. I have this predicate that works with removed things from one list and adding them to another list if they fullfill some requisites. The thing is that's not working for some reason, and only returning me a bool value.

I tried debugging it with trace, in which I saw the process is correct and indeed the list gets the elements in want to, but it simply only returns a true/false value,.

I also tried replicating my problem by creating a predicate rcu(L1,L2) to reverse a List. How would I make this work (with just 2 arguments, or at least, a predicate starting with 2 arguments)?

rcu([], List2).

rcu([H | Rest], List2) :-
    rcu(Rest, [H | List2]).

CodePudding user response：

rcu([], List2). will not be helpful, because List2 is undefined - need a third argument involved, to have e.g. rcu([], L, L.

There's background info and example methods at e.g. Reversing a List in Prolog

The usual problems are how to make reverse/2 fast, deterministic, and able to cope with open lists - e.g. [a,b|T] in which the tail ("T") could be zero, 1 or many list elements.

Here's my current best effort (read the thread for more info):

reverse_fast(L, R) :-
    % For reverse_fast([a,b|T], [c,b,a]).
    (   (   is_list(L)
        % For reverse_fast(L, [a,b]).
        ;   \  is_list(R),
            nonvar(L)
        )
    ->  reverse_fast_(L, [], R)
    ;   reverse_fast_(R, [], L)
    ).

reverse_fast_([], Ys, Ys).
reverse_fast_([X|Xs], Rs, Ys) :-
    reverse_fast_(Xs, [X|Rs], Ys).

These examples could trip up a lesser implementation:

?- reverse_fast([a,b|T], [c,b,a]).
T = [c].

?- reverse_fast(L, [a,b]).
L = [b, a].

... whilst also preventing unwanted choicepoints.

CodePudding user response：

My other answer, although faster for most purposes (because it doesn't check the elements of the 2nd argument in the loop), goes to infinity with ?- freeze(L,false), reverse_fast(L,R). as kindly pointed out by @false, so the current state-of-the-art for reverse/2 is as in swi-prolog, which adds 2 arguments:

A list starting at [] (i.e. empty), to repeatedly add an element to the head (start), which is an efficient operation
A copy of the 2nd argument, used to "count down" its elements to [], to ensure that both lists are of the same length - this ensures fast failure if the 2nd argument is shorter, and ensures actual failure if the 2nd argument is length-constrained (because it is being checked as part of the "loop")