Archive | October 2011

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? append/3 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 Zs is the list obtained when appending all the elements of Xs with all the elements of Ys. 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 append/3 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.

member(X, Xs) is true if X is a member of the list Xs. It’s of course not hard to write this as a recursive predicate as we did with append/3, but why bother if there’s an easier way? So let’s solve it with append/3 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, Xs, as argument. Can we find two other lists such that they give Xs when appended? Of course. Just call append/3 with Xs as the third argument. Remember that append/3 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
n
Xs = [a, b, c],
A = [a],
B = [b, c] n
n
Xs = [a, b, c],
A = [a, b],
B = [c] n
n
Xs = A, A = [a, b, c],
B = [] n
n
false.

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: X is a member of Xs if Xs can be divided into two parts, A and B, such that X comes between A and B. 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 append/3 as a relation instead of a function. A similar problem is the sublist problem: given a list Xs, is Ys a sublist of Xs? 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 append/3. A sublist is a continuous subsequence. This can be expressed in terms of three lists: Ys is sublist of Xs if there exists two lists, A and B, such that A appended with Ys and B results in Xs. That was quite a mouthful, but in essence it’s the same thing as we did with member/2 with the difference being that we’re looking for a list instead of a single element. Assume that we had the predicate append/4. 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 append/3 two times instead. First Xs is divided into A and B. Then we find the sublist Ys by saying that Ys is a suffix of B.

    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 Xs = [a,b]. Then the answer Ys = [b] can be found by first binding B to [a,b] and then Ys to the prefix [b] of this list. Or it can be found by binding B to [b] and then binding Ys to the prefix [b] of B. 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.

select/3, last/2 and other basic list processing predicates can be implemented in essentially the same manner. As a last example we’re going to implement nth/3 with append/3 and length/2. nth(X, Xs, N) is true if X is the N:th member of Xs, starting from 0. One observation is enough to give us a solution: X is the N:th element of Xs if the number of elements preceding Xs is equal to N. This is easy to check with length/2:

    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 nth/3 is rather inefficient and I would not recommend anyone to try it at home!

Advertisements