### 6.1.2 Using append

Now that we understand how `append` works, let's see how we can put it to work.

One important use of `append` is to split up a list into two consecutive lists. For example:

`append(X,Y,[a,b,c,d]). X = []  Y = [a,b,c,d] ; X = [a]  Y = [b,c,d] ; X = [a,b]  Y = [c,d] ; X = [a,b,c]  Y = [d] ; X = [a,b,c,d]  Y = [] ; no`

That is, we give the list we want to split up (here`[a,b,c,d]`) to `append` as the third argument, and we use variables for the first two arguments. Prolog then searches for ways of instantiating the variables to two lists that concatenate to give the third argument, thus splitting up the list in two. Moreover, as this example shows, by backtracking, Prolog can find all possible ways of splitting up a list into two consecutive lists.

This ability means it is easy to define some useful predicates with `append`. Let's consider some examples. First, we can define a program which finds prefixes of lists. For example, the prefixes of `[a,b,c,d]` are `[]`, `[a]`, `[a,b]`, `[a,b,c]`, and `[a,b,c,d]`. With the help of `append` it is straightforward to define a program `prefix/2`, whose arguments are both lists, such that `prefix(P,L)` will hold when `P` is a prefix of `L`. Here's how:

`prefix(P,L) :- append(P,_,L).`

This says that list `P` is a prefix of list `L` when there is some list such that `L` is the result of concatenating `P` with that list. (We use the anonymous variable since we don't care what that other list is: we only care that there some such list or other.) This predicate successfully finds prefixes of lists, and moreover, via backtracking, finds them all:

`prefix(X,[a,b,c,d]). X = [] ; X = [a] ; X = [a,b] ; X = [a,b,c] ; X = [a,b,c,d] ; no`

In a similar fashion, we can define a program which finds suffixes of lists. For example, the suffixes of `[a,b,c,d]` are `[]`, `[d]`, `[c,d]`, `[b,c,d]`, and `[a,b,c,d]`. Again, using `append` it is easy to define `suffix/2`, a predicate whose arguments are both lists, such that `suffix(S,L)` will hold when `S` is a suffix of `L`:

`suffix(S,L) :- append(_,S,L).`

That is, list `S` is a suffix of list `L` if there is some list such that `L` is the result of concatenating that list with `S`. This predicate successfully finds suffixes of lists, and moreover, via backtracking, finds them all:

`suffix(X,[a,b,c,d]). X = [a,b,c,d] ; X = [b,c,d] ; X = [c,d] ; X = [d] ; X = [] ; no`

Make sure you understand why the results come out in this order.

And now it's very easy to define a program that finds sublists of lists. The sublists of `[a,b,c,d]` are `[]`, `[a]`, `[b]`, `[c]`, `[d]`, `[a,b]`, `[b,c]`, `[c,d]`, `[d,e]`, `[a,b,c]`, `[b,c,d]`, and `[a,b,c,d]`. Now, a little thought reveals that the sublists of a list L are simply the prefixes of suffixes of L. Think about it pictorially:

And of course, we have both the predicates we need to pin this ideas down: we simply define

`sublist(SubL,L) :- suffix(S,L),prefix(SubL,S).`

That is, `SubL` is a sublist of `L` if there is some suffix `S` of `L` of which `SubL` is a prefix. This program doesn't explicitly use `append`, but of course, under the surface, that's what's doing the work for us, as both `prefix` and `suffix` are defined using `append`.

Patrick Blackburn, Johan Bos and Kristina Striegnitz
Version 1.2.5 (20030212)