Stuck with Prolog

Question

I just started learning Prolog. One of the exercise wants me to write backwards/2, a predicate that is true when the second list argument is the reverse of the first list argument. And I have to use a paste predicate to write backwards.

paste([], L, L).
paste([X|L1], L2, [X|L3]) :- paste(L1,L2,L3).

I worked on it for hours but still haven't gotten the answer.

Here's what I have:

backwards([H|T], Lrev) :- paste([X|T], X, Lrev).
backwards([],[]).

Nicholas Carey Nicholas Carey · Accepted Answer · 2014-10-08T17:36:08

Prolog lists are a very simple data structure.

An empty list is denoted by the atom [].
A non-empty list is denoted by the structure '.'/2, where the first argument is the list's head and the second argument is the list's tail, another list, empty or non-empty.

The Prolog list notation is syntactic sugar over that data structure:

[] is the empty list in both notations.

For non-empty lists,

[a] is the structure '.'(a,[]).
[a,b] is the structure '.'(a,'.'(b,[]))
[a,b,c] is the structure '.'(a,'.'(b,'.'(c,[])))
[Head|Tail] is exactly equivalent to '.'(Head,Tail).
[a|[b,c]] is exactly equivalent to [a,b,c] and to '.'(a,'.'(b,'.'(c,[])))

It is easy to see why one might prefer a little syntactic sugar.

The structure of a list then, like a classic singly linked list in more ... conventional ... languages, makes it trivial to add and remove items from the head (left) end of an existing list.

One should note that if, one at a time you remove items from one list and add items to another, you produce the first list in reverse order.

A common Prolog idiom is the use of a helper or accumulator argument that carries state through the recursion. Often this helper will be seeded with an initial value. One might also note that most recursive problems have one or two special cases and the broader general case.

Such a predicate that reverses a list might look something like this:

paste( []     , Rs , Rs ) .  % Special Case: if the source list is empty, unify the accumulator with the result.
paste( [X|Xs] , T  , Rs ) :- % General Case:
  T1 = [X|T] ,               % - prepend the current list head to the temporary, creating a new temporary, and
  paste(Xs,T1,Rs)            % - recurse down.
  .

One might note that the second clause above could be refactored for simplicity to remove the explicit creation of the new temporary:

paste( []     , Rs , Rs ) .  % Special Case: if the source list is empty, unify the accumulator with the result.
paste( [X|Xs] , T  , Rs ) :- % General Case:
  paste(Xs,[X|T],Rs)            % - prepend the current head to the temporary and recurse down.
  .

Either way, this predicate REQUIRES that the temporary be seeded with an initial empty list ([]).

Calling it thusly, then:

paste( [a,b,c] , [] , R ).

produces

R = [c,b,a]

Once you have your paste/3 predicate, creating your backwards/2 predicate is simplicity itself:

backwards( L , R ) :- paste( L , [] , R ) .

This exposes another common Prolog idiom: a trivial "public" predicate that invokes a "private" worker predicate that actually does all the work.

Stuck with Prolog

1 Answers