Add note about prolog's append/3

1 files changed, 65 insertions, 0 deletions

diff --git a/sites/pmikkelsen.com/prolog/generality-of-append.md b/sites/pmikkelsen.com/prolog/generality-of-append.md
new file mode 100644
index 0000000..bb50834
--- /dev/null
+++ b/sites/pmikkelsen.com/prolog/generality-of-append.md
@@ -0,0 +1,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?
\ No newline at end of file