CS 6905 Advanced Topics in Computer Science:
Functional and Logic Programming

Assignment 2

 Family Name       Given Name         Student ID         Signature

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.

FP version:

% 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].

LP version:

Does any version, or do both, work if you use your definition(s) on non-ground lists?

2) Consider the following operation definitions:

zap([],[],[]).

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.

zap:

zip:

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].

roman4arabic([i],1).

Type builtins into the Relfun interaction window to see which arithmetic functions are predefined. Use a new sheet to give your definitions.

Maintained by Harold Boley