In the lecture we introduced more built-in predicates on lists. You should become familiar with all of the list predicates listed in our quick reference. You should also be able to implement any of these predicates in Prolog. Here are some implementations that we saw in the lecture:
% member(?X, ?L) is true if X is a member of L member(X, [X | _]). member(X, [_ | L]) :- member(X, L). % append(?L1, ?L2, ?M) is true if M is the concatenation of L1 and L2 append([], L, L). append([X | L], M, [X | N]) :- append(L, M, N). % same_len(?L, ?M) is true if L and M are lists of the same length same_len([], []). same_len([_ | L], [_ | M]) :- same_len(L, M). % select(?X, ?L, ?M) is true if we can remove X from L to make M. % Equivalently, it is true if we can insert X anywhere in M to make L. select(X, [X | L], L). select(X, [Y | L], [Y | L2]) :- select(X, L, L2).
Ideally a Prolog predicate will run in all directions and will always terminate if the result set is finite. Unfortunately it's not always so easy to tell whether the predicate will terminate just by looking at it. Often in practice you will need to run it to see what happens.
The select implementation above works in more than
one direction:
?- select(X, [3, 4, 5], L). X = 3, L = [4, 5] ; X = 4, L = [3, 5] ; X = 5, L = [3, 4] ; false. ?- select(2, L, [3, 4]). L = [2, 3, 4] ; L = [3, 2, 4] ; L = [3, 4, 2] ; false.
Let's cleverly reimplement select using append:
select(X, L1, L2) :- append(A, [X | B], L1), append(A, B, L2).
Now the first query above still works, but the second hangs after finding all solutions:
?- select(2, L, [3, 4]). L = [2, 3, 4] ; L = [3, 2, 4] ; L = [3, 4, 2] ; (hang) ^CAction (h for help) ? abort % Execution Aborted ?-
Here is a trick that can often help a predicate terminate: add a goal
that uses the same_length predicate to express the
relationship between two list lengths. For example:
select(X, L1, L2) :- same_length(L1, [_ | L2]),
append(A, [X | B], L1), append(A, B, L2).
Now the query select(2,
L, [3,
4])
correctly finds all solutions and terminates.
The same_length
trick works because it adds a logically valid constraint that helps
limit Prolog's search. If you want to understand it in more detail,
turn on tracing and study how Prolog resolves the above query with
and without the same_length
goal.
In the lecture we discussed how to use accumulators to make certain predicates more efficient. 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 is N1 + I.
Here's the same predicate, rewritten to use an accumulator. The running time is still linear, but this version may be more efficient because it is tail recursive:
sum(L, S) :- sum(L, 0, S). % helper predicate: second argument is an accumulator sum([], S, S). sum([I | L], S, R) :- S1 is S + I, sum(L, S1, R).
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). % helper predicate: second argument is an accumulator reverse([], R, R). reverse([X | L], S, R) :- reverse(L, [X | S], R).
There's only one problem: both of these implementations (either without or with an accumulator) will hang when their first argument is an unbound variable:
?- reverse(L, [a, b, c]). L = [c, b, a] ; ERROR: Out of global stack ?-
Once again, the same_length trick can save us:
reverse(L, R) :- same_length(L, R), reverse(L, [], R). % helper predicate is same as before
Now queries will terminate in both directions.
You can read more about accumulators in section 8.5.3 (Last call optimizations and accumulators) in Bratko, 4th edition (or section 8.5.4 in the 3rd edition).
In the lecture we also introduced higher-order predicates. (These are similar to higher-order functions, which we will see when we study Haskell later.)
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 several examples of using maplist.
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.
Now 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. This is probably the way in which you will use
maplist most often:
double(I, J) :- J is I * 2. ?- maplist(double, [1, 2, 3], [2, 4, 6]). true. ?- maplist(double, [1, 2, 3], L). L = [2, 4, 6].
Remarkably, 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 is 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 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].
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:
?- 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 structure containing a predicate name plus one or more
arguments:
?- call(add(2), 3, N). N = 5.
It is actually easy to implement maplist using call.
Here are 2- and 3-argument versions:
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).