Sample Exam II Solutions

Problem 1.

(a) these two terms unify with A = 2, B = 2, C = 3, D = g(2,3)

(b) these two terms fail to unify since unification does not perform arithmetic, so 2+3 does not match 5

Problem 2.

(a) 'not' and \+ behave differently for goals with unsolved variables, so if the third clause is used in a query, results will differ; for instance with the query intersect([A], [2], Bs), A>2 -- intersect1 outputs an error message, while intersect2 responds 'no'

(b) the presence of unsolved variables also differentiates these two in the same way; with same query as in (a), intersect3 responds 'no' while intersect1 gives the error.

(c) in intersect3, 'member' is used as the "if-goal" in the if-then-else and so is not backtracked, while in intersect2 it is backtracked, so queries that cause this backtracking differ; for instance intersect([A], [1,2], Bs), A>1 -- intersect2 responds A=2, Bs=[2], but intersect3 responds 'no'.

Problem 3.

A version blending recursion and iteration can be provided using 'findall' to add in the first item to each element of the recursive solution. This uses the familiar 'member' predicate.

cumulative([ ], [ ]).

cumulative([X|Xs], [X|Ys]) :- cumulative(Xs, Zs), % tail sums without X

findall(Y, (member(Z,Zs), Y is X+Z), Ys). % add X into tail sums

A neat tail-recursive solution adds an accumulator argument to hold the running sum of the numbers processed from the first list.

cumulative(Xs,Ys) :- accum(Xs,Ys,0). % initial sum = 0 -- nothing processed

accum([ ], [ ], _). % halt/succeed -- all numbers processed

accum([X|Xs], [Y|Ys], S) :- Y is S+X, % sum for X is previous sum + X

accum(Xs, Ys, Y). % rest of sums likewise with Y

A version using only recursion (also, tail-recursion) is based on the observation that by adding the first two items before continuing with the rest of the list, the addition of each item is propagated forward into the cumulative sums. This necessitates an additional stopping case for 1-item lists.

culumative([ ], [ ]).

cumulative([X], [X]).

cumulative([X,Y|Xs], [X|Zs]) :- Z is X+Y, cumulative([Z|Xs], Zs).