1

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

false
  • 10,264
  • 13
  • 101
  • 209
incud
  • 541
  • 1
  • 9
  • 17
  • 1
    That's a rather non-standard definition of [`append`](http://www.swi-prolog.org/pldoc/man?predicate=append/3), 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]`, http://stackoverflow.com/questions/11539203/how-do-i-append-lists-in-prolog – npostavs Jun 01 '15 at 19:54
  • It seems that's not the problem. If I rename `append` to `my_append` it's the same – incud Jun 01 '15 at 20:04
  • You need to restart the Prolog system, too. Further there is `[A,B]` which should probably read `[A|B]` and much more... – false Jun 01 '15 at 20:50
  • 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 Jun 01 '15 at 21:09
  • 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? –  Jun 02 '15 at 06:09

2 Answers2

3

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.
Nicholas Carey
  • 71,308
  • 16
  • 93
  • 135
  • Thanks for your answer. However, it was just a syntax problem. I wanted to write reverse([A|B], ReversedList) insted of reverse([A,B], ReversedList). It still doesn't work but I knew the algorithm wasn't ok. – incud Jun 03 '15 at 14:32
2

It's possible there are other problems, but 

  1. reverse([], ReversedList).

    is almost surely not what you want here. The reverse of an empty list is an empty list, translates to

    reverse([], []).

  2. Additionally,

    reverse([A,B], ReversedList)

    is also probably not what you want. It is not a list with head A and tail B, but rather a 2-element list.

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185