=========================preview======================
(COMP251)07finalsol.pdf
Back to COMP251 Login to download
======================================================
Suggested Solutions for COMP251L2 Final Exam (Dec 17, 2007)

Problem 1

fun length []=0
| length (x::y) =length(y)+1;

fun sublist(list,0)=[]
| sublist(x::y,n)=x::sublist(y,n-1);

fun sym(x)= let val y = sublist(x, (length(x) div 2))
in y@y = x
end;

Problem 2:


append([],X,X).
append([X|Xs],Y,[X|Z]) :- append(Xs.Y,Z). %[library(lists)].

sym(X) :- append(Y,Y,X).

Problem 3:

<S> ::= <empty> | a<S>a

Problem 4.

1. roo1(X, [3, 1]).









2. roo1(2, [3,1]).


3. roo2(X,[3,1]).


Problem 5.

result

k: parameter

b: parameter

a: parameter

saved machine status

control-link

i: local variable

temporary storage







Problem 6.

1. 1+2\n = 2 (any answer other than 3 will be accepted)
2. 3-1\n = 2
3. 9-2*3 = 21

Problem 7.

fun member(x,[]) = false
| member(x,y::z) = if x=y then true else member(x,z);

fun conj [] y = []
| conj (x::y) z = if member(x,z) andalso not (member(x,y))
then (x::(conj y z))
else conj y z;
Or:

fun clean [] = []
| clean (x::y) = if member(x,y) then clean y
else (x::(clean y));
fun conj1 [] y = []
| conj1 (x::y) z = if member(x,z) then (x::(conj1 y z))
else (conj1 y z);
fun conj x y = conj1 (clean x) y;

Problem 8.

conj(X,Y,Z) :- conj1(X,Y,Z1), perm(Z1,Z).

conj1([],_,[]).
conj1([X|Xs],Y,[X|Zs]) :- member(X,Y), \+ member(X,Xs), !, conj1(Xs,Y,Zs).
conj1([_|Xs],Y,Zs) :- conj1(Xs,Y,Zs).

perm([],[]).
perm([X|Xs],Y) :- perm(Xs,Y1), append(Y2,Y3,Y1), append(Y2,[X|Y3],Y).

Or

clean([],[]).
clean([X|Xs],Ys) :- member(X,Xs), !, clean(Xs,Ys).
clean([X|Xs],[X|Ys]) :- clean(Xs,Ys).

conj(X,Y,Z) :- clean(X,X1), conj1(X1,Y,Z1), perm(Z1,Z).

conj1([],_,[]).
conj1([X|Xs],Y,[X|Zs]) :- member(X,Y), !, conj1(Xs,Y,Zs).
conj1([_|Xs],Y,Zs) :- conj1(Xs,Y,Zs).