Selected Solutions for the Sample Final Exam

Solutions for problems 2 and 4 can be obtained by using the computer systems.

Problem 3.

A Haskell solution just appends the appropriate fill items before and after xs.

center xs n f

| n< length xs = error "insufficient size"

| otherwise = replicate half f ++ xs ++ replicate (n–length xs–half) f

where -- n–length xs is fill count

half = quot (n–length xs) 2

A Prolog solution is similar, but not as concise; it fails rather than giving an error when there is insufficient space.

center(Xs,N,F,Result) :-

length(Xs,M), M=<N,

N1 is (N-M)//2, N2 is N-N1,

rep(N1,F,L), rep(N2,F,R),

append(L,Xs,Ys), append(Ys,R,Result).

rep(0, F,[ ]).

rep(N,F,[F|Xs]):- N>0, N1 is N-1, rep(N1,F,Xs),

Problem 5.

(a) Recursive solution checks each item to see if it is repeated using 'member'. If so, retain in answer, delete other occurrences, and continue; if not, just continue with next item.

repeats([ ],[ ]). % stopping case

repeats([X|Xs], [X|Ys]) :- member(X,Xs), delete(X,Xs,Zs), repeats(Zs,Ys).

repeats([X|Xs], Ys) :- \+member(X,Xs), repeats(Xs,Ys).

An alternative iterative solution using Prolog's 'findall' is

repeats(Xs,Ys) :- findall(X,

(append(As,[X|Bs],Xs), % for each X in Xs

\+member(X,As), % select first, reject others

member(X,Bs)), % and check repetition

Ys).

delete(X,[ ],[ ]).

delete(x,[X|Xs],Ys) :- delete(X,Xs,Ys).

delete(X.[Y|Xs],[Y|Ys]) :- X\==Y, delete(X,Xs,Ys).

(b) both versions give only the one solution A=a, Bs=[a].