From dc5734cba676a827005c02bcc2deb1e84fad001c Mon Sep 17 00:00:00 2001 From: Peter Mikkelsen Date: Wed, 28 Jul 2021 22:46:22 +0000 Subject: Add note about prolog's append/3 --- .../pmikkelsen.com/prolog/generality-of-append.md | 65 ++++++++++++++++++++++ 1 file changed, 65 insertions(+) create mode 100644 sites/pmikkelsen.com/prolog/generality-of-append.md 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 -- cgit v1.2.3