Suppose that Prolog did not include built-in arithmetic. Could we define our own numbers using structures?
Actually we could, and it would not be difficult. Consider the natural numbers ℕ = 0, 1, 2, ..., and choose the following representation: the atom z will represent zero, and the structure s(X) will represent the successor of X. So we have
z = 0
s(z) = 1
s(s(z)) = 2
...
We may write a recursive predicate add(A, B, C) that adds two natural numbers in this representation:
add(A, z, A). add(A, s(B), s(C)) :- add(A, B, C).
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.
Now let's write a predicate le(A, B) that is true if A ≤ B, where A and B are natural numbers in this representation. Here is a recursive implementation:
le(z, _). le(s(A), s(B)) :- le(A, B).
Alternatively, we may just call add():
le(A, B) :- add(A, _, B).
This predicate will also work bidirectionally:
?- le(s(s(z)), N). N = s(s(z)) ; N = s(s(s(z))) ; N = s(s(s(s(z)))) ; ... ?- le(N, s(s(z))). N = s(s(z)) ; N = s(z) ; N = z
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.
It's nice that we can define our own numbers. However, internally Prolog does not store its own integers using this representation, which would be extremely inefficient for performing arithmetic on numbers that are not small. (Instead it uses machine words that it can manipulate using CPU instructions, just like other languages.)
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 awkward 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.
In fact this syntax is arguably easier to read than Prolog's own list syntax, since A : B looks simpler than [A | B].
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.
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].
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].
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 is the 2-argument version:
maplist(_, []). maplist(P, [X | L]) :- call(P, X), maplist(P, L).
Earlier we wrote a predicate that can reverse a list:
reverse([], []).
reverse([X | L], N) :- same_length([X | L], N),
append(M, [X], N), reverse(L, M).The call to same_length() allows the predicate to terminate in both directions.
Let's try to use this predicate to reverse a list with 10,000 elements:
?- numlist(1, 10_000, L), reverse(L, M). ERROR: Stack limit (1.0Gb) exceeded
The predicate runs for a number of seconds, then runs out of stack space. Fundamentally the problem is that it runs in time O(N2) on a list with N elements. That's because appending an element to the end of a list takes O(N), so the total running time is O(1 + 2 + ... + N) = O(N2).
This inefficiency is disappointing. After all, in a procedural language we could easily write a function to reverse a linked list in time O(N), using a simple loop. On each iteration, we can remove an element from the head of the original list, and prepend it to the list that we are building.
To imitate this process in Prolog, we may rewrite the predicate using an accumulator:
rev_acc([], A, A). rev_acc([X | L], A, R) :- rev_acc(L, [X | A], R). rev_acc(L, R) :- same_length(L, R), rev_acc(L, [], R).
In this version, the top-level predicate rev_acc(L, R) calls the recursive helper predicate rev_acc(L, A, R), passing the empty list [] as the initial value for the accumulator argument A. Each time that rev_acc() recurses, it removes an element from the list L and prepends it to the accumulator A. When we reach the base of the recursion, we return the final value of the accumulator.
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.
As another example, 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, S #= S1 + N, sum_n(N1, S1).
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
This last call fails. The problem is that the predicate has recursed very deeply, exceeding available memory. This is unfortunate, 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 use 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).
As in the previous example, the top-level predicate calls a recursive helper predicate, passing an initial value for the accumulator argument A. Each time that sum_acc recurses, it computes a new accumulator value and passes it to the next recursive call. At the base of the recursion we return the final accumulator value.
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
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).
As we can see, using an accumulator may make a program more efficient. On the other hand, our predicates rev_acc() and sum_acc() are slightly more complicated than their non-accumulator versions. Furthermore, in some Prolog programs an accumulator may actually hurt performance. For this reason, I recommend that you use an accumulator only when it provides a significant performance gain.