Arcane Abuses of append
First I should point out that the following predicates hardly qualify as arcane, and they’re not really that abusive either. But they do use append, and one out of three isn’t so bad after all? is one of Prolog’s most useful predicates and is often one of the list predicates first taught to students. Beginners, and especially those familiar with other programming languages, sometimes have a hard time recognizing the multiple usages of the predicate however. Just for reference and to make sure that we’re on the same page, the usual definition goes like this:
append(, Ys, Ys). append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).
Nothing fanciful. Just a standard recursive predicate which holds if is the list obtained when appending all the elements of with all the elements of . So when should we use this predicate? When we want to append two lists? No! Upon years of using Prolog I don’t think I’ve used for this purpose in a serious program even once. The reason being that difference lists are usually a much better choice in these instances since they can be appended in constant instead of linear time. So let’s try to figure out some other usages.
is true if is a member of the list . It’s of course not hard to write this as a recursive predicate as we did with , but why bother if there’s an easier way? So let’s solve it with instead. Upon a first inspection it might not look like they have anything to do with each other. How can we find an element in a list by appending two lists? The answer is actually pretty simple. We know that we take a list, , as argument. Can we find two other lists such that they give when appended? Of course. Just call with as the third argument. Remember that is a relation and not a function:
?- Xs = [a,b,c], append(A, B, Xs).
Xs = [a, b, c],
A = ,
B = [a, b, c] n
Xs = [a, b, c],
A = [a],
B = [b, c] n
Xs = [a, b, c],
A = [a, b],
B = [c] n
Xs = A, A = [a, b, c],
B =  n
That was the first step. Now let’s find an interpretation of membership that can be cast in terms of these three lists. How about this: is a member of if can be divided into two parts, and , such that comes between and . Put into code this is:
member(X, Xs) :- append(_A, [X|_B], Xs).
Very easy once you know the trick, but difficult if one is afraid of using as a relation instead of a function. A similar problem is the sublist problem: given a list , is a sublist of ? Again it’s not hard to imagine how a recursive version would look, but perhaps we can find an easier solution with the help of . A sublist is a continuous subsequence. This can be expressed in terms of three lists: is sublist of if there exists two lists, and , such that appended with and results in . That was quite a mouthful, but in essence it’s the same thing as we did with with the difference being that we’re looking for a list instead of a single element. Assume that we had the predicate . Then sublist could be solved as:
sublist(Xs, Ys) :- append(_A, Ys, _B, Xs).
Alas, since we don’t have such a predicate we’re going to use two times instead. First is divided into and . Then we find the sublist by saying that is a suffix of .
sublist(Xs, Ys) :- append(_A, B, Xs), append(_, Ys, B).
It should be noted that this solution gives rise to many duplicate answers. Why? Assume that . Then the answer can be found by first binding to and then to the prefix of this list. Or it can be found by binding to and then binding to the prefix of . This is a bummer since we’re only interested in one of these answers. The implementation of an optimized version is left as an exercise to the reader.
, and other basic list processing predicates can be implemented in essentially the same manner. As a last example we’re going to implement with and . is true if is the :th member of , starting from . One observation is enough to give us a solution: is the :th element of if the number of elements preceding is equal to . This is easy to check with :
nth(X, Xs, N) :- append(A, [X|_], Xs), length(A, N).
A question to the observant reader: why is the order of the two goals in the body not swapped? Also, as a concluding remark: I’ve been told that it’s not always a good idea to do something just because you can. That might well be true. This version of is rather inefficient and I would not recommend anyone to try it at home!