1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
# 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?
|