Selected Solutions for the Sample Final Exam
Solutions for problems 2 and 4 can be obtained by using the computer systems.
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.
N1 is (N-M)//2, N2 is N-N1,
rep(0, F,[ ]).
rep(N,F,[F|Xs]):- N>0, N1 is N-1, rep(N1,F,Xs),
(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
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].