Computer Science 3675
Fall 2015
Practice Questions for Quiz 4

1. Given definition

      f x y = (x+1)::y.
   

   1. What kind of thing is x (a number, a list or a function)? Answer
   2. What kind of thing is y (a number, a list or a function)? Answer
   3. What kind of thing is f x y (a number, a list or a function)? Answer
   4. What kind of thing is f x (a number, a list or a function)? Answer

2. You are given the following function definition.

       f x y z = y x (x::z)
   

   1. What kind of thing is parameter z? (A number, a list, a function, or something else)? Answer
   2. What kind of thing is parameter y? (A number, a list, a function, or something else)? Answer
   3. What kind of thing does expression f (2) yield? (A number, a list, a function, or something else? Is this expression allowed?) Answer

3. Consider the following definition written in Cinnameg.

       Define f(n) = (:n*n :: f(n+1):).
   

   What value does expression f(2) compute? Give the full value, as it would be if it were examined. (It suffices to give a clear description of the full value.) Evaluating a promise does not change the value that is represented, it only changes the representation of the value.

   Answer

4. Consider the following definition written in Cinnameg.

       Define f(n) = (: n :: f(n*n) :).
   

   What value does expression f(2) compute? Give the full value, as it would be if it were examined.

   Answer

5. Write a Scheme function (filter f  L) that returns a list of all members x of list L such that (f  x) is not #f. (Notice that f  is a function.) Be careful to use Scheme syntax correctly.

   Answer

6. Write an equational definition of rfold(i, f, L) so that rfold(i, f, [a,b,c]) = f (a, f (b, f (c, i))). Generalize to an arbitrarily long list.

   To get a better understanding of this, suppose that the function (f ) is a binary operator * (whose meaning could be anything), where operator * is right-associative. That is, a*b*c means a*(b*c). Then rfold(i, *, [a,b,c]) = a*b*c*i and rfold(x, *, [a,b,c,d]) = a*b*c*d*x.

   By definition, rfold(i, f, [ ]) = i.

   Answer