Prolog returning true/false instead of variable

Question

I'm working on the very easy reverse list example in Prolog.

append(A, [], [A]).
append(A, B, [A|B]).

reverse([], ReversedList).
reverse([A,B], ReversedList) :-
  reverse(B, TemporaryList),
  append(A, TemporaryList, ReversedList).

append works correctly. However, when I call reverse the interpreter doesn't respond with a variable like append but instead it just write true or false.

Here's the log:

1 ?- consult('capitolo2'.pl). % file containing the code
2 ?- append(a, [b,c,d], L).
L = [a,b,c,d]. % ok, this works
3 ?- reverse([a,b,c], L).
false. % what? why that's not L = something?

The platform is SWI-Prolog 7.2 on Windows

That's a rather non-standard definition of append, usually append is defined to work on lists, e.g. append([a,b,c], [x,y,z], L) ==> L = [a,b,c,x,y,z], stackoverflow.com/questions/11539203/… — npostavs
It seems that's not the problem. If I rename append to my_append it's the same — incud
You need to restart the Prolog system, too. Further there is [A,B] which should probably read [A|B] and much more... — false
Your reverse rule will only succeed if the first argument is an empty list ([]) or a two element list ([A, B]). It will fail all other cases since they won't match. — lurker
Why are you implementing a standard predicate like append/3? And if you have good reasons to do it, why do you not look it up once you run into problems? — user1812457

Nicholas Carey Nicholas Carey · Accepted Answer · 2015-06-02T00:52:22

append/3

Did you unit test it? Did it work properly? Your append/3 implementation is incorrect. The first clause

The first clause:

append( A , [] , [A]   ).

simply creates a list of length 1 from its 1st argument (whatever it might be). Given that, if you said:

append( [1,2,3] , [] , X ) .

You'd get back:

X = [ [1,2,3] ]

A list of length 1, with the sole item it contains being the original 1st argument. The second clause is similarly incorrect:

append( A , B , [A|B] ).

Prepends the 1st argument — whatever it might be, and in its entirety — as the head of that list. Given that, if you said something like:

append( [1,2,3] , [a,b,c] , X ) .

You'd get back:

X = [ [1,2,3] , a , b , c ] .

A list of length 4, the first item of which is the original 1st argument.

Prolog is a descriptive language: you describe the solution and let the engine work things out. append/3 asserts that a list (the 3rd argument to append/3 represent the concatenation of the 1st argument and the 2nd argument.

Here is an implementation of append/3, simplified for clarity:

append( []      , RL , RL ) .  % The concatenation of an empty left-hand list and a right hand list is the right hand list.
append( [LH|LT] , RL , CL ) :- % The concatenation of a non-empty left-hand list and a right-hand list is true IF:
  CL = [LH|CT] ,               % - The left-hand head and the concatenation head are the same, AND
  append( LT , RL , CT )       % - recursively, the concatenated tail represents the conconcatenation of the left-hand tail and the right-hand list.
  .                            % Easy!

As you pop items off the left-hand list, it will eventually decompose into the terminating special case. This can be simplified to the classic implementation:

append( []      , RL , RL      ) .
append( [LH|LT] , RL , [LH|CT] ) :- append( LT , RL , CT ) .

reverse/3

Similarly, your reverse/3 implemenation is incorrect. Your first clause:

reverse([], ReversedList).

pretty much says that pretty much anything is the reverse of the empty list. Since your ReversedList variable is never referenced, your Prolog implementation should at least throw a warning about singleton variables here. Many implementations make it an error.

Your second clause:

reverse([A,B], ReversedList) :-
  reverse(B, TemporaryList),
  append(A, TemporaryList, ReversedList).

says that the reverse of a 2-item list ([A,B]) is obtained by

reversing the 2nd item in the list (B), and
appending the 1st item (A) to that.

Not exactly a correct description of the solution. You might try something like

reverse( []    , [] ) .  % The empty list is already reversed, what with it being atomic and all.
reverse( [H|T] , R  ) :- % a non-empty list can be reversed by decomposing it into its head and tail, and
  reverse(T,T1) ,        % - reversing the tail, and
  append(T1,H,R) .       % - appending the head to the now-reversed tail.

Prolog returning true/false instead of variable

2 Answers