The built-in higher-order predicate foldl can combine elements of a list using an arbitrary predicate. Let's see foldl in action:
add(I, J, K) :- I + J #= K. ?- foldl(add, [3, 4, 5], 0, S). S = 12
The code above adds the members of the list [3, 4, 5], starting with the value 0. In other words, it computes ((0 + 3) + 4) + 5. This is called a left fold because it combines values from the left, just like the accumulators that we wrote in last week's lecture.
In general, foldl takes four arguments: a predicate of three arguments, a list, a starting value for the accumulator and a final value for the accumulator. If we write
foldl(P, [a, b, c], A, R)
then foldl will make a series of calls to P, with this
effect:
P(a, A, A1) P(b, A1, A2) P(c, A2, R)
Here is an efficient implementation of reverse(), using foldl:
prepend(X, L, [X | L]). reverse(L, M) :- same_length(L, M), foldl(prepend, L, [], M).
We can easily implement fold() using call(). The implementation will look similar to the accumulator pattern that we saw in the previous lecture:
foldl(_, [], A, A). foldl(P, [X | L], A, R) :- call(P, X, A, A1), foldl(P, L, A1, R).
Another version of foldl takes five arguments: a predicate of four arguments, two lists, a starting value for the accumulator and a final value for the accumulator. If we write
foldl(P, [a, b, c], [d, e, f], A, R)
then foldl will make a series of calls to P, with this effect:
P(a, d, A, A1) P(b, d, A1, A2) P(c, f, A2, R)
In other words, each call to P receives two elements, one from each of the input lists, and uses them to compute the next accuulator value. For example, we can use this version of foldl to compute a dot product:
mul_add(X, Y, A, A1) :- A1 #= A + X * Y. ?- foldl(mul_add, [1, 2, 3], [4, 5, 6], 0, N). N = 32
We may implement sorting algorithms such as insertion sort, merge sort or quicksort easily in Prolog.
For example, let's implement insertion sort. As a first step, here's a predicate that can insert a value into a sorted list:
insert(X, [], [X]). insert(X, [Y | Z], [X, Y | Z]) :- X #=< Y. insert(X, [Y | Z], [Y | L]) :- X #> Y, insert(X, Z, L).
Let's try it:
?- insert(15, [10, 12, 14, 16], L). L = [10, 12, 14, 15, 16] ?- insert(A, [10, 12, 16], [10, 12, 14, 16]). A = 14
Now we can write insertion sort recursively:
isort([], []). isort([X | L], M) :- same_length([X | L], M), isort(L, LS), insert(X, LS, M).
It works both forwards and backwards:
?- isort([5, 2, 8, 1, 10, 3], L). L = [1, 2, 3, 5, 8, 10] ?- isort(L, [10, 15, 20]). L = [10, 15, 20] ; L = [15, 10, 20] ; L = [20, 10, 15] ; L = [10, 20, 15] ; L = [15, 20, 10] ; L = [20, 15, 10]. ?- isort(L, [10, 20, 15]). false.
How long will our predicate take to sort N numbers? In the best case, the input list will already be sorted. Then insert() will run in O(1) on each iteration, so the total time will be O(N). In the worst (and expected) case, insert() will take O(M) to insert into a sorted list of M numbers, so the total running time will be O(N + (N - 1) + ... + 1) = O(N2). These are the same best-case and worst-case times that we would expect from an implementation of insertion sort in a procedural language.
In Prolog we can build common data structures such as stacks, queues, and binary trees. However, since Prolog has no mutable state, the interfaces to these structures will look a bit different than in procedural languages. Every operation on a data structure S, such as pushing a value onto a stack or enqueuing into a queue, will return a new version of the data structure, since S itself cannot be modified.
As we will see, the implementations of functional data structures must also sometimes be different than in procedural languages.
A functional stack is trivial to implement in Prolog, since a Prolog list itself can act as a stack.
% S is an empty stack. empty_stack([]). % We can push X onto S to make the stack [X | S]. push(X, S, [X | S]). % We can pop X from [X | S] to make the stack S. pop(X, [X | S], S).
We can push N numbers onto an empty stack using recursion:
% S is the empty stack with the numbers 1 .. N pushed onto it. push_to_n(0, []). push_to_n(N, S) :- N #> 0, N1 #= N - 1, push_to_n(N1, S1), push(N, S1, S).
Or using foldl:
push_to_n2(N, S) :- numlist(1, N, NL), foldl(push, NL, [], S).
We may naively implement a functional queue using a list. When we enqueue values, we append them to the end fo the list. We dequeue values by removing them from the front:
% empty_queue(Q) - Q is an empty queue empty_queue([]). % enqueue(X, Q, R) - we can enqueue X onto Q to make R enqueue(X, Q, R) :- append(Q, [X], R). % dequeue(X, Q, R) - we can dequeue X from Q to make R dequeue(X, [X | R], R).
We may use foldl to enqueue a series of values:
?- numlist(1, 10, _L), foldl(enqueue, _L, [], Q). Q = [1, 2, 3, 4, 5, 6, 7, 8, 9|...].
In fact we may even use foldl to dequeue several values at once:
?- numlist(1, 10, _L), foldl(enqueue, _L, [], _Q), length(M, 3), foldl(dequeue, M, _Q, _). M = [1, 2, 3].
However our naive implementation is inefficient. enqueue() runs in O(N) when there are N values in the queue. Queueing N values successively onto an empty queue will take O(N2).
Alternatively, we may implement a functional queue using two lists, which we will call the front and back lists. For example, here is one such queue:
[a, b, c] / [f, e, d]
To enqueue a value, we prepend it to the back list. To dequeue a value, we remove it from the head of the front list. For example, we may enqueue 'g' and then dequeue 'a' and b' from the queue above, yielding this queue:
[c] / [g, f, e, d]
When dequeueing, if the front list is empty then we reverse the back list and move it to the front. For example, if we dequeue 'c' from the queue above, then the front list will become empty. The next time we dequeue, we will reverse the list [g, f, e, d] to form [d, e, f, g]. We will dequeue 'd', and the remaining items will now be at the front:
[e, f, g] / []
Here is a Prolog implementation:
empty_queue([] / []). enqueue(X, F / B, F / [X | B]). dequeue(X, [X | F] / B, F / B). dequeue(X, [] / B, F / []) :- reverse(B, [X | F]).
With this implementation, enqueue() runs in O(1).
How will dequeue() perform? Suppose that we start with an empty queue, and enqueue and dequeue N values via some series of enqueue and dequeue operations. There will be some number of flips, i.e. operations in which we move values from the back to the front. Each flip of K values will take O(K), since reverse() runs in linear time. The total number of values flipped will be N, since each enqueued value will move to the front exactly once. So the total cost of all the flip operations will be O(N). And so the total time for all N dequeue operations will be O(N) (for removing values from the front list) + O(N) (for all the flip operations) = O(N). And so dequeue() will run in O(1) on average.
It is straightforward to represent a binary tree in Prolog. We can represent an empty binary tree as the atom 'nil', and a non-empty tree as t(L, X, R), where X is the value in the root node and L and R are left and right subtrees. For example, consider this tree:
Here is a predicate defining its representation:
my_tree(T) :- T = t(t(nil, 2, nil),
5,
t(t(nil, 8, nil), 10, t(nil, 12, nil))).It's straightforward to write a recursive predicate to count the nodes in a tree:
count(nil, 0).
count(t(L, _, R), N) :- N #>= 1, LN #>= 0, RN #>= 0, N #= LN + RN + 1,
count(L, LN), count(R, RN).
?- my_tree(_T), count(_T, N).
N = 5.We may even generate all trees with a given number of nodes:
?- count(T, 3). T = t(nil, _, t(nil, _, t(nil, _, nil))) ; T = t(nil, _, t(t(nil, _, nil), _, nil)) ; T = t(t(nil, _, nil), _, t(nil, _, nil)) ; T = t(t(nil, _, t(nil, _, nil)), _, nil) ; T = t(t(t(nil, _, nil), _, nil), _, nil)
Let's write a predicate maptree(P, T) that succeeds if a predicate P is true for every value in a tree:
maptree(_, nil). maptree(P, t(L, X, R)) :- call(P, X), maptree(P, L), maptree(P, R). ?- count(T, 2), maptree(=(5), T). T = t(nil, 5, t(nil, 5, nil)) ; T = t(t(nil, 5, nil), 5, nil)