Here's a predicate that adds numbers in a list:
% sum(L, N): N is the sum of numbers in L sum([], 0). sum([I | L], N) :- sum(L, N1), N #= N1 + I.
Given a list such as [3, 4, 5], this computes the sum 3 + (4 + (5 + 0)) = 12. The partial sums are computed from right to left.
Here's the same predicate, rewritten to use an accumulator.
sum(L, S) :- sum(L, 0, S). % accumulator is initially 0 % helper predicate: second argument is an accumulator sum([], S, S). sum([I | L], A, R) :- A1 #= A + I, sum(L, A1, R).
This computes the sum ((0 + 3) + 4) + 5 = 12. Notice that with an accumulator the partial sums are computed in a different order, i.e. from left to right. Of course, the result will be the same in either case, because addition is associative: (a + b) + c = a + (b + c).
Here's a predicate that reverses a list, naively:
reverse([], []). reverse([X | L], N) :- reverse(L, M), append(M, [X], N).
This will run in time O(N2) on a list with N elements. We can dramatically improve its efficiency using an accumulator, which lets us combine elements in the opposite direction:
reverse(L, R) :- reverse(L, [], R). % accumulator is initially [] % helper predicate: second argument is an accumulator reverse([], R, R). reverse([X | L], A, R) :- reverse(L, [X | A], R).
There's only one problem: both of these implementations of reverse
(either without or with an accumulator) will fail
to terminate when their first argument is an unbound variable:
?- reverse(L, [a, b, c]). L = [c, b, a] ; ERROR: Out of global stack ?-
As usual, the
same_length trick helps:
reverse(L, R) :- same_length(L, R), reverse(L, [], R). % helper predicate is same as before
Now queries will terminate in both directions.
In the lecture we also introduced higher-order predicates. (These are similar to higher-order functions, which we will see when we study Haskell in a few weeks.)
Higher-order predicates are not discussed in the Bratko text, so let's review them here.
The maplist predicate applies a predicate P to
elements of one or more lists, and succeeds if P always succeeds. It
is a higher-order predicate because its argument P is itself a
predicate. Let's look at a
few examples.
When maplist has two arguments, it applies a
predicate P to every element of a single list. Suppose that we have a
predicate odd:
odd(I) :- I mod 2 #= 1.
Now we can use maplist to test whether all integers in a
list are odd:
?- maplist(odd, [3, 5, 7]). true. ?- maplist(odd, [3, 4, 7]). false.
Consider the
following predicate, which states that up and down
are directions:
dir(up). dir(down).
We can use maplist to test whether all elements of a
list are directions. But we can also run maplist
backwards to generate lists
of directions:
?- maplist(dir, [up, down]). true. ?- length(L, 2), maplist(dir, L). L = [up, up] ; L = [up, down] ; L = [down, up] ; L = [down, down].
When maplist has three arguments, it applies a
predicate P to corresponding pairs of elements from two lists.
For example, maplist(P, [1, 2, 3], [4, 5, 6])
will invoke P(1, 4), P(2, 5) and P(3, 6). maplist will
succeed if all of these invocations succeed.
You can use this to compare list elements, for example:
less(I, J) :- I #< J. ?- maplist(less, [1, 2, 3], [4, 5, 6]). true.
The preceding query succeeds because 1 < 4, 2 < 5, and 3 < 6.
Alternatively, you can pass maplist a predicate
representing a function that
you want to apply to every element of a list:
double(I, J) :- J #= I * 2. ?- maplist(double, [1, 2, 3], [2, 4, 6]). true. ?- maplist(double, [1, 2, 3], L). L = [2, 4, 6].
If the function works
in both directions then maplist will too:
?- maplist(length, [[10, 11], [12, 13, 14]], L). L = [2, 3]. ?- maplist(length, L, [2, 3]). L = [[_4144, _4150], [_4162, _4168, _4174]].
When maplist has four arguments, it applies a
predicate P to triples of arguments from three lists. You can
use this form if you have a three-argument predicate representing a
function of two arguments:
add(A, B, C) :- C #= A + B. ?- maplist(add, [1, 2, 3], [10, 11, 12], L). L = [11, 13, 15].
The first argument to maplist can be an atom naming a
predicate, as in the examples above. Or it can be a structure
containing a partially applied predicate, i.e. predicate name
plus one or more arguments. maplist will append any
additional arguments before applying the predicate. This is a
powerful and useful capability.
For example, we can add 5 to every element of a list like this:
?- maplist(add(5), [1, 2, 3], L). L = [6, 7, 8].
Another useful built-in higher-order function is foldl,
which 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 a section above.
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], V0, V)
then foldl will make a series of calls to P, with this effect:
P(a, V0, V1) P(b, V1, V2) P(c, V2, V)
Here are some more examples:
% Convert a list of digits (e.g. [4, 5, 6]) to an integer (e.g. 456). combine(I, J, K) :- K #= I + 10 * J. to_int(L, I) :- foldl(combine, L, 0, I). % An efficient implementation of reverse, using foldl. prepend(X, L, [X | L]). rev(L, M) :- same_length(L, M), foldl(prepend, L, [], M).
maplist and foldl are
actually built from a more primitive predicate call.
call is itself a higher-order predicate, and invokes the
predicate it is given, appending additional arguments:
?- call(add, 2, 3, X). X = 5. ?- call(length, [2, 4], N). N = 2. ?- call(length, L, 2). L = [_9364, _9370].
As with maplist, the first argument to call
can be a partially applied
predicate:
?- call(add(2), 3, N). N = 5.
We can easily implement
maplist and foldl using call.
Here are 2- and 3-argument versions: of maplist:
maplist(_, []). maplist(P, [X | L]) :- call(P, X), maplist(P, L). maplist(_, [], []). maplist(P, [X | L], [Y | M]) :- call(P, X, Y), maplist(P, L, M).
Here is foldl:
foldl(_, [], V0, V0). foldl(P, [X | L], V0, VR) :- call(P, X, V0, V1), foldl(P, L, V1, VR).