CS 6905 Advanced
Topics in Computer Science:
1) Define a recursive operation remequals for removing repeated equal elements (found for the second time or any further times in left-to-right passes) on each level of a list that only contains simple terms and lists. Start with an FP version by filling in the 6 blanks in the template for a small function library below. Then define a corresponding LP version. As a function, e.g., remequals([b,c,b]) as well as remequals([b,c,c]) should return [b,c], hence remequals([a,c,[b,c,b],c,[b,c,c],d,[c],c]) should return [a,c,[b,c],d,[c]]. Test further calls (extreme cases). As a relation, e.g., remequals([,a,[b,[c],b,[c],a],d,],Res) should bind Res to [,a,[b,[c],a],d]. Test it or prove it.
% remequals is main function removing equals in a list
% that only contains simple terms and lists
remequals() :& .
remequals(X) :- atom(X) & X.
remequals([F|R]) :& remequaflat(remequalsmap([F|R])).
% remequalsmap applies remequals to each element of a list
% (we assumed no higher-order mapping function is available)
remequalsmap() :& .
remequalsmap([F|R]) :& cns(________________,remequalsmap(R)).
% remequaflat removes equals on top-level of a list
remequaflat() :& ___.
remequaflat([F|R]) :& __________________________________________.
% remone removes first occurrence of element in list
remone(E,) :& ___.
remone(E,[E|R]) :& ___.
remone(E,[X|R]) :& ______________________________.
% cns permits call-by-value arguments (in Lisp called cons)
cns(First,Rest) :& [First|Rest].
Does any version, or do both, work if you use your definition(s) on non-ground lists?
2) Consider the following operation definitions:
zap([X|T1],[_|T2],[X|T3]) :- zap(T1,T2,T3).
zip(,,) :& .
zip([H1|T1],[H2|T2],[H3|T3]) :& cns([H1,H2,H3],zip(T1,T2,T3)).
Find out which, if any, operations are functions (_______________________) and which, if any, relations (_______________________).
Describe in concise English (maximal 3 sentences each) what zap and zip are computing.
3) Define Relfun functions roman2arabic and arabic2roman converting between the (lower-cased, listified) roman and arabic natural numbers [i]-[x,x,x] and 1-30 using a reasonably small number of clauses. Merge both functions into a single relation roman4arabic. The following illustrates the three definition patterns:
roman2arabic([i]) :& 1.
arabic2roman(1) :& [i].
Type builtins into the Relfun interaction window to see which arithmetic functions are predefined. Use a new sheet to give your definitions.