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 ‘filter-mapping’ the elements of a list according to an arbitrary unary predicate P, applying an arbitrary unary function F to the qualifying elements, where “!&” cuts off the remaining clause(s) after the first success of P:



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


filtermap[P,F]([]) :& [].

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

filtermap[P,F]([First|Rest]) :& filtermap[P,F](Rest).



Functional Sample Calls:

filtermap[numberp,1+]([1,a,b,4,c])      returns [2,5]

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


Check (X) whether the filtermap 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].


sound() :& tweet.

sound() :& meow.

sound() :& bark.


soundlist(0) :& [].

soundlist(N) :- >(N,0) & cns(sound(),soundlist(-(N,1))).

Give short characterizations of the sets of
returned values of
sound()  and of soundlist(2):






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 mapping of a binary function F or a ternary relation R over two equal-length lists of
numbers 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