Suppose that Prolog did not include built-in arithmetic. Could we define our own integers using structures, and implement arithmetic predicates on them?
Actually we could, and it would not be difficult. Let's choose the following representation: the atom z will represent zero, and the structure s(X) will represent the successor of X. So we will have
z = 0
s(z) = 1
s(s(z)) = 2
...
Now we may write a recursive predicate add(I, J, K) that adds two numbers in this representation:
add(z, I, I). add(s(I), J, s(K)) :- add(I, J, K).
It will work in any direction, so we may use it to either add or subtract:
?- Two = s(s(z)), Three = s(Two), add(Two, Three, N). Two = s(s(z)), Three = s(s(s(z))), N = s(s(s(s(s(z))))). ?- Two = s(s(z)), Three = s(Two), add(Two, N, Three). Two = s(s(z)), Three = s(s(s(z))), N = s(z). ?- Two = s(s(z)), Three = s(Two), add(Three, N, Two). false.
The syntax s(s(s(s(s(z))))) is a bit ugly. Instead of the s() functor, we may use a prefix operator, such as the built-in unary operator '+'. We will have
z = 0
+ z = 1
+ + z = 2
...
Let's rewrite our add() predicate using this syntax:
add(z, I, I). add(+ I, J, + K) :- add(I, J, K).
Now our queries will look a bit nicer. For example:
?- Two = + + z, Three = + + + z, add(Two, Three, N). Two = + +z, Three = + + +z, N = + + + + +z. ?- Two = + + z, Three = + + + z, add(Two, N, Three). Two = + +z, Three = + + +z, N = +z.
Suppose that Prolog did not have built-in lists. Could we define them using structures?
Actually we could, very easily. Let's use the atom 'nil' to represent the empty list. 'cons(X, L)' will represent the value X prepended to the list L. So, for example, the list containing 3, 4, and 5 will be represented as cons(3, cons(4, cons(5, nil))).
With this list representation, let's write member() and append():
member(X, cons(X, _)). member(X, cons(_, L)) :- member(X, L). append(nil, L, L). append(cons(X, L), M, cons(X, N)) :- append(L, M, N).
These predicates will work just as on ordinary lists, and in any direction:
?- member(5, cons(3, cons(5, cons(7, nil)))). true ?- member(5, cons(3, cons(X, cons(7, nil)))). X = 5 ?- append(cons(3, cons(5, nil)), cons(7, cons(9, nil)), L). L = cons(3, cons(5, cons(7, cons(9, nil)))).
The syntax with the 'cons' functor is unwieldy when lists have more than a couple of elements. As an alternative, let's use operator syntax instead. We will use the built-in infix operator ':' for prepending, so that 'X : L' will represent the value X prepended to the list L. With this syntax, our predicates will now look like this:
member(X, X : _). member(X, _ : L) :- member(X, L). append(nil, L, L). append(X : L, M, X : N) :- append(L, M, N).
Queries are now much easier to read:
?- member(X, 3 : 5 : 7 : nil). X = 3 ; X = 5 ; X = 7 ?- append(2 : 3 : 4 : nil, 5 : 6 : nil, L). L = 2:3:4:5:6:nil.
We have seen that Prolog's structures are quite general. We can use them to implement numbers, lists, and many other useful data types as well.
Suppose that we have a predicate pos(X) that succeeds if an integer X is positive. We may recursively write a predicate all_pos(L) that is true if all elements of a list are positive:
pos(X) :- X #> 0. all_pos([]). all_pos([X | L]) :- pos(X), all_pos(L).
Now suppose that we have a predicate even(X) that succeeds if an integer X is even. Similarly, we may write a predicate all_even(L):
even(X) :- X mod 2 #= 0. all_even([]). all_even([X | L]) :- even(X), all_even(L).
It's awkward that we have to write the same recursive pattern in each of the examples above. Instead, we can use the built-in predicate maplist(). We can write all_pos() and all_even() more simply as follows:
all_pos(L) :- maplist(pos, L). all_even(L) :- maplist(even, L).
maplist(P, L) applies a predicate P to every element of a list L, and succeeds if P succeeds on every element. It is a higher-order predicate because its argument P is itself a predicate.
As another example, suppose that we'd like to write a predicate all_dif(X, L) that is true if every element of L is different from X. We could write this predicate recursively:
all_dif(_, []). all_dif(X, [Y | L]) :- dif(X, Y), all_dif(X, L).
Alternatively, we can write it using maplist:
all_dif(X, L) :- maplist(dif(X), L).
In this rule, 'dif(X)' is a partially applied predicate. As we know, the 'dif' predicate takes two arguments; for example, dif(a, b) is true. The form 'dif(X)' gives 'dif' its first argument; 'maplist' will pass each member of L in turn as the second argument to 'dif'. If all of those calls succeed, i.e. every element of L is different from X, then 'maplist' itself will succeed.
We may even partially apply the built-in equality predicate '=':
?- length(L, 7), maplist(=(4), L). L = [4, 4, 4, 4, 4, 4, 4].
Sometimes when we use partially applied predicates, the order of arguments in an existing predicate is inconvenient. For example, suppose that we'd like to write a predicate subset(L, M) which is true if L is a subset of M, i.e. every member of L is a member of M. We already have the built-in predicate member(X, L), which succeeds if X is a member of L. We might try to write subset() like this:
subset(L, M) :- maplist(member(M), L). % WRONG
However this is wrong. The problem is that the first argument of member() is not a list; it is the member element.
As a workaround, we can write a predicate member_of() that is like member, but with its arguments swapped:
% member_of(L, X) - true if X is a member of L member_of(L, X) :- member(X, L).
And now we can write subset() using maplist:
subset(L, M) :- maplist(member_of(M), L).
The order of arguments may also be inconvenient if we use partially applied comparison operators. For example, consider the following query:
?- maplist(#>(5), [8, 9, 10]). false.
At first glance, the result above may be surprising, since it looks like the query is testing whether all list elements are greater than 5. However, the query is actally testing whether 5 is greater than each of the list elements! In other words, its first test will be 5 #> 8. That's because the first argument to the #> operator is 5, since it's supplied by the partial application.
If we like, we may define our own comparison operators that take the arguments in the other order! For example, let's use the built-in op() predicate to define operators ':<' and ':>':
:- op(650, xfx, :<). :- op(650, xfx, :>). X :< Y :- X #> Y. X :> Y :- X #< Y.
Above, 650 is an operator precedence level, and 'xfx' means that the operator is binary and is neither left- nor right-associative.
Now we may write
?- maplist(:>(5), [8, 9, 10]). true
This is a somewhat advanced trick. If you like it, use it; otherwise, you don't have to.
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 form 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 = [[_, _], [_, _, _]].
Suppose that we have a mapping between numbers and words:
num(1, one). num(2, two). num(3, three). num(4, four).
We may use maplist() to apply the mapping to an entire list:
?- maplist(num, [2, 2, 3, 4], L). L = [two, two, three, four]. ?- maplist(num, L, [two, two, three, four]). L = [2, 2, 3, 4].
Let's write a predicate that will add an integer N to every element of a list, using a partially applied predicate:
add(I, J, K) :- I + J #= K. add_n(N, L, M) :- maplist(add(N), L, M). ?- add_n(7, [10, 20, 30], L). L = [17, 27, 37].
Similarlly, let's write a predicate that will multiply a scalar X times a vector V of floating-point numbers, producing a vector W:
mul(X, Y, Z) :- { X * Y = Z }.
mul_sv(X, V, W) :- maplist(mul(X), V, W).When maplist() has four arguments, it applies a predicate P to triples of arguments from three lists. For example, we may use this form to add two vectors:
add(A, B, C) :- A + B #= C. ?- maplist(add, [1, 2, 3], [10, 11, 12], L). L = [11, 13, 15].
Suppose that we represent pairs of values using the infix operator ':'. Let's write a predicate zip() that can zip two lists together, producing a list of pairs:
pair(A, B, A : B). zip(L, M, N) :- maplist(pair, L, M, N).
For example:
?- zip([1, 2, 3], [10, 20, 30], L). L = [1:10, 2:20, 3:30].
We may even run the predicate backwards to unzip a list of pairs into a pair of lists:
?- zip(L, M, [1:10, 2:20, 3:30]). L = [1, 2, 3], M = [10, 20, 30].
maplist() is 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:
add(A, B, C) :- A + B #= C. ?- call(add, 2, 3, X). X = 5. ?- call(length, [2, 4], N). N = 2. ?- call(length, L, 2). L = [_, _].
The first argument to call() can be a partially applied predicate:
?- call(add(2), 3, N). N = 5. ?- call(add(2, 3), N). N = 5.
We can easily implement maplist() 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).
We can represent a vector using a list of floating-point numbers, and a matrix using a list of row vectors. maplist() is especially helpful for implementing vector and matrix operations. If we use new-style real arithmetic, then all our predicates will work in any direction. Some examples:
% helper predicates
add(X, Y, Z) :- { Z = X + Y }.
mul(X, Y, Z) :- { Z = X * Y }.
% multiply (scalar S) * (vector V) = (vector W)
mul_sv(S, V, W) :- maplist(mul(S), V, W).
% multiply (scalar S) * (matrix M) = (matrix N)
mul_sm(S, M, N) :- maplist(mul_sv(S), M, N).
% add (vector V) + (vector W) = (vector Y)
add_vv(V, W, Y) :- maplist(add, V, W, Y).
% add (matrix M) + (matrix N) = (matrix O)
add_mm(M, N, O) :- maplist(add_vv, M, N, O).Suppose that we'd like to write a predicate that computes the sum of all integers from 1 through N. Here's a direct recursive solution:
sum_n(0, 0). sum_n(N, S) :- N #> 0, N1 #= N - 1, sum_n(N1, S1), S #= S1 + N.
Let's try it:
?- sum_n(1000, N). N = 500500
It seems to work. Let's try to compute some large sums:
?- sum_n(1_000_000, N). N = 500000500000 ?- sum_n(5_000_000, N). ERROR: Stack limit (1.0Gb) exceeded
Unfortunately this last call fails. The problem is that the predicate has recursed very deeply, exceeding available memory. This is disappointing, since in an imperative language such as C we could easily compute this sum using a small constant amount of memory.
As an alternative, we may rewrite the predicate using an accumulator:
sum_acc(0, A, A). sum_acc(N, A, S) :- N #>0, N1 #= N - 1, A1 #= A + N, sum_acc(N1, A1, S). sum_acc(N, S) :- sum_acc(N, 0, S).
In this version, the top-level predicate sum_acc(N, S) calls the recursive predicate sum_acc(N, A, S), passing 0 as the initial value for the accumulator argument A. Each time that sum_acc recurses, it computes a new value of the accumulator and passes it to the next recursive call. When we reach the base of the recursion, we return the final value of the accumulator.
The rewritten predicate runs more quickly, and can compute larger sums:
?- sum_acc(1_000_000, N). N = 500000500000 ?- sum_acc(5_000_000, N). N = 12500002500000
As we can see, using an accumulator can make a program more efficient. On the other hand, the code with the accumulator is a bit more complex than the original version.
In the original predicate sum_n() without the accumulator, the sum is computed from right to left. For example, sum_n(4, S) will compute
1 + (2 + (3 + 4))
On the other hand, the predicate sum_acc() computes the sum from left to right. For example, sum_acc(4, S) will compute
((1 + 2) + 3) + 4
Of course, the result will be the same in either case, because addition is associative: (a + b) + c = a + (b + c).
An accumulator is a natural fit for some problems in which we want to process list values from left to right. For example, suppose that we want to convert a list of digits such as [3, 5, 6] to an integer such as 356. We may traverse the digits from left to right; each time we see a digit D, we multiply by 10 and add D:
0 * 10 + 3 = 3
3 * 10 + 5 = 35
35 * 10 + 6 = 356
Let's write a predicate that performs this computation, using an accumulator:
digits([], A, A). digits([D | L], A, N) :- 0 #=< D, D #=< 9, A1 #= A * 10 + D, digits(L, A1, N). digits(L, N) :- digits(L, 0, N).
It will work in any direction:
?- digits([3, 5, 6], N). N = 356. ?- digits([3, D, 6], 356). D = 5. ?- digits(L, 356). L = [3, 5, 6] ; L = [0, 3, 5, 6] ...
As another example, 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 improve its efficiency using an accumulator. On each iteration, the predicate will remove an element from the list on the left, and prepend it to the accumulator:
reverse([], A, A). reverse([X | L], A, R) :- reverse(L, [X | A], R). reverse(L, R) :- same_length(L, R), reverse(L, [], R). % accumulator is initially []
As usual, we must call same_length() to ensure that the predicate will terminate in either direction. This predicate will reverse a list of length N in time O(N), since each prepend operation takes constant time.
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 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], 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 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).