# 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!

### One response to “Arcane Abuses of append”

1. Martisch says :

hi, nice blog!

the sublist code has an error and i think you should switch some arguments:

?- X=[1,2],findall(Y,(append(_,B,X),append(_,Y,B)),A).
X = [1, 2],
A = [[1, 2], , [], , [], []].

note that the sublist  is not produced.

?- X=[1,2],findall(Y,(append(_,B,X),append(Y,_,B)),A).
X = [1, 2],
A = [[], , [1, 2], [], , []].

the first append should split a list B that is a suffix of X ( _ + B ) and the second append should be the prefix of B ( Y + _ ) so we have X = _ + (Y + _).