Prolog programming drills

Writing Prolog by hand on the exam

The exam lets you answer Q3 in Prolog (or Lisp). Assignments A1/A3 are pure Prolog: factorial, list indices, acyclic paths, min-cost paths. So this drill is about reproducing the shape of a recursive Prolog predicate cold: a base case plus a recursive step that decomposes a list as [H|T].

The recursion template

Every list predicate follows the same skeleton:

pred([], BaseValue).                 % base: empty list
pred([H|T], Result) :-               % recursive: split head/tail
    pred(T, Sub),                    % solve the tail
    combine(H, Sub, Result).         % fold the head back in

factorial (A3) is the integer analogue — base case 0, recursive step multiplies down:

fact(0, 1).
fact(N, F) :- N > 0, N1 is N - 1, fact(N1, F1), F is N * F1.

Worked example — Q3, product of a list

*"Read a list $Y$ and an integer $X$; test whether $X$ equals the product of $Y$."* The product is a fold with base value 1 (the multiplicative identity):

product([], 1).
product([H|T], P) :- product(T, PT), P is H * PT.

% query:  product([2,3,4], P), X =:= P.

Trace product([2,3,4], P): it recurses to product([], 1), then on the way back computes $4 \cdot 1 = 4$, $3 \cdot 4 = 12$, $2 \cdot 12 = 24$. So $P = 24$; the test X =:= 24 is true for $X = 24$ and false for $X = 10$.

Worked example — A1, minimum-cost path

With weighted edges edge(a,b,3), edge(b,c,1), edge(c,d,2), edge(b,d,5), collect every acyclic path's [Cost, Path] with findall/setof, then take the smallest. Sorting [Cost|_] lists puts the cheapest first:

min_path(S, G, Best) :-
    setof([C, P], path(S, G, P, C), [ [_,Best] | _ ]).

The cheapest $a \to d$ route is $a \to b \to c \to d$ at cost $3+1+2 = 6$, beating the direct $a \to b \to d$ at $3+5 = 8$.

We verify both logics in runnable Python below (our in-browser runtime is Python; the Prolog above is what you write on the exam).