Running Forwards and Backwards.

It is possible to do list processing in Prolog. The append predicate joins two lists together. The function c can stand for the list constructor. The result of appending nil and a list B is just B. The result of appending c(H,T) and B is c(H,TB) where TB is the result of appending T and B.

  c(H, T) + B
       ------
= c(H,  T+B  )

 --- Appending to a non-null List. ---

append(c(H,T), B, c(H,TB)) <= append(T, B, TB).
append(nil, B, B).

? append( c(1, c(2, nil)), c(3, c(4, nil)), X).

{\fB Append run Forwards. \fP}

The result of appending the lists c(1,c(2,nil)) and c(3,c(4,nil)) is c(1,c(2,c(3,c(4,nil)))). Note that most Prolog systems provide a nicer syntax for lists, eg. [1,2,3,4].

append(c(1, c(2, nil)), c(3, c(4, nil)), c(1, c(2, c(3, c(4, nil))))) yes

 --- Append two Lists. ---

A surprising feature of append is that it can be run backwards to take a list apart.

append(c(H,T), B, c(H,TB)) <= append(T, B, TB).
append(nil, B, B).

? append( X, Y, c(1, c(2, c(3, nil))) ).

{\fB Append run Backwards. \fP}

There are four ways in which the list c(1,c(2,c(3,nil)))) can be made up of two other lists.

append(c(1, c(2, c(3, nil))), nil, c(1, c(2, c(3, nil)))) yes
append(c(1, c(2, nil)), c(3, nil), c(1, c(2, c(3, nil)))) yes
append(c(1, nil), c(2, c(3, nil)), c(1, c(2, c(3, nil)))) yes
append(nil, c(1, c(2, c(3, nil))), c(1, c(2, c(3, nil)))) yes

 --- Dismantle a List. ---