The generality of the append predicate

In prolog we don't write functions which maps some input to an output. Instead, we write relations which states what must be true for the relation to hold. This gives a lot of power, in that those relations are often usable in many more ways than a function in another programming language would be.

To show an example of this, here is the append predicate which states that if append(A, B, C) then C is the list which contains the contents of list A followed by the contents of list B:

append([], ListB, ListB).
append([A|ListA], ListB, [A|Rest]) :-
	append(ListA, ListB, Rest).

It is only two clauses. The first clause states that an empty list followed by some list B is just B, and the second clause states that if the first list consists of head A and tail ListA, then the appended list consists of head A and tail Rest as long as appending ListA to ListB gives Rest.

Usage 1: appending two lists.

?- append([a,b,c], [d,e,f], Result).
   Result = [a, b, c, d, e, f].

Works as expected, and this is probably what most people want from an append function in another programming language.

Usage 2: What is the prefix?

?- append(Prefix, [d,e,f], [a,b,c,d,e,f]).
   Prefix = [a, b, c].

Here we ask the question "What list, when appended with [d,e,f], gives us [a,b,c,d,e,f]?" and prolog answers with [a,b,c] as we expected.

Usage 3: What is the suffix?

?- append([a,b,c], Suffix, [a,b,c,d,e,f]).
   Suffix = [d, e, f].

This is almost like before, but it asks for the suffix instead.

Usage 4: How about both the prefix and suffix

?- append(Prefix, Suffix, [a,b,c,d,e,f]).
   Prefix = [],
   Suffix = [a, b, c, d, e, f]
;  Prefix = [a],
   Suffix = [b, c, d, e, f]
;  Prefix = [a, b],
   Suffix = [c, d, e, f]
;  Prefix = [a, b, c],
   Suffix = [d, e, f]
;  Prefix = [a, b, c, d],
   Suffix = [e, f]
;  Prefix = [a, b, c, d, e],
   Suffix = [f]
;  Prefix = [a, b, c, d, e, f],
   Suffix = [].

Here we see that prolog is actually able to show us what prefix and suffix combined gives [a,b,c,d,e,f]! Since there are more than one solution here, each solution is seperated by the semicolon.

Conclusion

When you think about it, what the simple 2 clause append predicate does is pretty amazing compared to how little code is needed. It clearly describes a relationship between three lists in a way that allows us to use it to get answers to all sorts of questions, not just appending. How much code would be required to cover all the four use cases shown here if implemented in your favourite programming language?