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).