We can represent a vector using a list of numbers, and a matrix using a list of row vectors.
% helper predicates add(I, J, K) :- K is I + J. mul(I, J, K) :- K is I * J. % multiply (scalar S) * (vector V) = (vector V1) mul_sv(S, V, V1) :- maplist(mul(S), V, V1). % multiply (scalar S) * (matrix M) = (matrix M1) mul_sm(S, M, M1) :- maplist(mul_sv(S), M, M1). % add (vector V1) + (vector V2) = (vector V) add_vv(V1, V2, V) :- maplist(add, V1, V2, V). % dot(V1, V2, S): S is the dot product of vectors V1 and V2 dot([], [], 0). dot([I | L], [J | M], S) :- dot(L, M, S1), S is S1 + I * J.
The higher-order predicate foldl looks like this:
foldl(+Goal,
?List, ?V0, ?V)
It folds List from the left, applying Goal to each
element and an accumulator argument that is initially V0. For
example, foldl(G, [a, b, c], V0, V) will apply in turn:
G(a, V0, V1) G(b, V1, V2) G(c, V2, V)
foldl is often a convenient alternative to writing a
recursive predicate using an accumulator.
% helper predicates add(I, J, K) :- K is I + J. max(I, J, K) :- K is max(I, J). % V is the sum of all numbers in L. sum(L, V) :- foldl(add, L, 0, V). % V is the maximum of all numbers in L. max(L, V) :- foldl(max, L, - inf, V). % Convert a list of digits (e.g. [4, 5, 6]) to an integer (e.g. 456). % This is a recursive implementation using an accumulator argument. to_int1(L, I) :- to_int1(L, 0, I). to_int1([], V, V). to_int1([I | L], J, R) :- K is I + 10 * J, to_int1(L, K, R). % Convert a list of digits to an integer, using foldl. combine(I, J, K) :- K is 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).
We can easily represent arithmetic expressions using structures in
Prolog. For example, we can use 2-argument functors plus
and times to represent addition and multiplication. Then
we can represent the expression x2 + 2x + 7 as
plus(plus(times(x,
x), times(2,
x)), 7)
Now we can write a predicate to evaluate expressions:
% eval(+E, +X, ?V) evaluates an arithmetic expression E of a single variable x. % X is the value of x. The result is V. eval(x, X, X). eval(N, _, N) :- integer(N). eval(plus(A, B), X, V) :- eval(A, X, V1), eval(B, X, V2), V is V1 + V2. eval(times(A, B), X, V) :- eval(A, X, V1), eval(B, X, V2), V is V1 * V2.
Lists are built into Prolog. But if they were not built in, we could easily define them using structures.
To demonstrate this, we'll use a two-element functor cons
to build our own lists. (The name cons comes from Lisp
and Scheme, which have a similar list representation). cons(H,
T) will combine H (the head of the list, i.e. the first
element) with T (the rest of the list). In other words, cons(H,
T) is like the built-in [H | T]. We will
represent the list [2, 3, 4] as
cons(2, cons(3, cons(4, nil)))
Now we can write list predicates just like with built-in lists:
member(X, cons(X, _)). member(X, cons(_, L)) :- member(X, L). length(nil, 0). length(cons(_, L), I) :- length(L, I1), I is I1 + 1.
In fact Prolog's built-in lists are implemented in exactly this way. In other words, lists are just a special case of structures.
Even if integers were not built into Prolog, we could define them
using structures. To demonstrate this, we'll use the atom z
to represent the number zero, and a single-argument functor s
to mean "successor". The number 3 is s(s(s(z))).
Now we can define arithmetic predicates, e.g.
% leq(A, B) is true if A <= B leq(z, _). leq(s(I), s(J)) :- leq(I, J). % add(A, B, C) is true if A + B = C add(z, I, I). add(s(I), J, s(K)) :- add(I, J, K).
Unlike Prolog's built-in arithmetic, these predicates will work in all directions. For example:
% Solve the equation 2 + K = 4. ?- add(s(s(z)), K, s(s(s(s(z))))). K = s(s(z)).
In Thursday's tutorial session we solved most of these exercises. Here are the solutions we saw:
sums(L, M) :- sums(L, 0, M). sums([], _, []). sums([X | L], A, [A1 | M]) :- A1 is A + X, sums(L, A1, M).
% helper predicate
add(I, J, K) :- K is I + J.
% add (vector V1) + (vector V2) = (vector V)
add_vv(V1, V2, V) :- maplist(add, V1, V2, V).
%%% (a) add matrix + matrix = matrix
add_mm(M1, M2, M) :- maplist(add_vv, M1, M2, M).
%%% (b) generate the N x N identity matrix
n_zeroes(L, N) :- length(L, N), maplist(=(0), L).
prep(X, L, [X | L]).
identity(1, [[1]]).
identity(N, [[1 | R] | RR]) :-
N > 1, N1 is N - 1, identity(N1, M),
n_zeroes(R, N1), maplist(prep(0), M, RR).% leq(I, J) is true if I <= J leq(z, _). leq(s(I), s(J)) :- leq(I, J). % add(I, J, K) is true if I + J = K add(z, I, I). add(s(I), J, s(K)) :- add(I, J, K). % mul(I, J, K) is true if I * J = K mul(z, _, z). mul(s(I), J, K) :- leq(s(I), K), leq(J, K), % guarantee termination mul(I, J, K1), add(J, K1, K).