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

Assignment 3


Family Name       First Name         Student ID         Signature





1) Consider the following functional definition for filtering the elements of a list according to an arbitrary unary predicate P, where “!&” cuts off the remaining clause(s) after the first success of P:



cns(First,Rest) :& [First|Rest].


filterlist[P]([]) :& [].

filterlist[P]([First|Rest]) :- P(First) !& cns(First,filterlist[P](Rest)).

filterlist[P]([First|Rest]) :& filterlist[P](Rest).



Functional Sample Calls:

filterlist[numberp]([1,a,b,4])      returns [1,4]

filterlist[atom]([a,[_],b,[c,d]])    returns [a,b]


Check (X) whether the filterlist operation is deterministic (  ) or non-deterministic (  ),

first-order (  ) or higher-order (  ).



Give the relational version of this definition (hints: “!&” becomes “!”;

no relation corresponding to the cns function is needed):








Relational Sample Calls:





2) Consider the following non-deterministic function definitions:


cns(First,Rest) :& [First|Rest].


color() :& blue.

color() :& green.


colorlist(0) :& [].

colorlist(N) :- >(N,0) & cns(color(),colorlist(-(N,1))).

Give short characterizations of the sets of
returned values of
color()  and of colorlist(3):






Explain why the premise >(N,0) is crucical (just in 1 or 2 sentences):




3) Define a (possibly non-deterministic) higher-order function mapf or relation mapr for
the ‘synchronized’ mapping of a binary function F or a ternary relation R over two
equal-length lists such that: mapf[F]([d1,…,dN],[e1,…,eN]) returns [a1,…,aN],
where a1 = F(d1,e1), …, aN = F(dN,eN)]; or mapr[R]([d1,…,dN],[e1,…,eN],A)
binds A to [a1,…,aN], where R(d1,e1,a1), …, R(dN,eN,aN):






Maintained by Harold Boley