G6021 Comparative Programming
Prolog questions
Prolog questions
G6021 Comparative Programming
1/5
Example: Last
Write Prolog clauses to find the last element of a list. Give a trace of your clauses for the query last([a,b,c],L), showing the substitutions at each step
Advice for most people following this module: always think of a Haskell solution first:
last [x] = x
last (x:y:t) = last (y:t)
We can now try to think of the Prolog:
last([X], X).
last([X,Y|Rest], E) :- last([Y|Rest], E).
Prolog questions
G6021 Comparative Programming
2/5
Example: Last
last([X], X).
last([X,Y|Rest], E) :- last([Y|Rest], E).
The trace of the query with substitutions (SLD tree):
last([a,b,c],L)
X=a, Y=b, Rest = [c], E = L
last([b,c],L)
X=b, Y =c, Rest = [], E = L
last([c],L)
c=X, X=L
So Prolog succeeds with: X=c
Prolog questions
G6021 Comparative Programming
3/5
Example: Swap
1 Write Prolog clauses that will swap adjacent pairs of elements as shown in the following examples:
swap([1,2],[2,1]).
swap([1,2,3],[2,1,3]).
swap([1,2,3,4],[2,1,4,3]).
swap([1],[1]).
swap([],[]).
and give SLD trees for the following four goals:
:- swap([1,2],X).
:- swap(X,[2,1]).
:- swap([1,2,3,4],X).
:- swap([1,2], [1,2]).
Prolog questions
G6021 Comparative Programming
4/5
Example: Swap
First, write the Haskell:
swap [] = []
swap [x] = [x]
swap (x:y:t) = y:x:(swap t)
Now we can write the Prolog:
swap([], []).
swap([H], [H]).
swap([H,S|T], [S,H|U]) :- swap(T,U).
We show just one case:
:- swap([1,2], [1,2]).
Fails because:
H=1, S=2, S=1 ….
1 and 2 will not unify!
Prolog questions
G6021 Comparative Programming
5/5