CMSC 22300
Homework 4, Due Friday 4/30/2010

1. [15] type checking

Derive the typing of the following definition:

  fun f x =
      let fun g (y,z) = (x y, z x)
       in (g(3, (fn u => u 1)), g(2, fn v => hd(v 0)))
      end

[As you can tell by having the compiler typecheck the definition,
the final result is that f has the type 

  f : (int -> 'a list) -> ('a list * 'a list) * ('a list * 'a)

but you should give a detailed manual derivation of this
type.]


2. [15] tail recursive foldr

(a) [10] The foldl function has the naturally tail-recursive definition:

    fun foldl f init nil = init
      | foldl f init (x::xs) = foldl f (f(x,init)) xs

The obvious definition of foldr, which operates on the elements
of a list from right to left, is 

    fun foldr f init nil = init
      | foldr f init (x::xs) = f(x, foldr f init xs)

which is not tail recursive.  Give a tail-recursive definition
of foldr, and discuss whether or not it is better than this
non-tail-recursive one.  [Hint, foldl is tail recursive, and
it differs from foldr only in the order in which the elements
of the list are folded. You may have to make some assumptions
about costs of the operations involved and the overhead of lazy
function calls. If so, state any such assumptions.]

(b) [5] In SML, foldl and foldr have the same type:

   foldl, foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

But in Haskell, foldl and foldr have different types:

   foldl :: (a -> b -> a) -> a -> [b] -> a
   foldr :: (a -> b -> b) -> b -> [a] -> b

Explain the difference (try experimenting with a noncommutative
folding function like list cons (:: in ML, : in Haskell)).
[Definitions of foldl and foldr are found on pages 92 and 94
of Real World Haskell.]


3. (a) [5] Choose or define functions f1 and f2 such that:

    f1 (f2 (*) [1,2,3,4]) 5  ==>  [5,10,15,20]

(b) [5] What is the type of ys in

    xs = [1,2,3] :: [Float]
    ys = map (+) xs

(c) [10] Define a function that computes the "dot product"
of a pair of lists of numbers.  I.e.

   dotProduct [1,2,3] [4,5,6] = 1*4 + 2*5 + 3*6

Try to define your dotProduct function without using recursion
by using library functionals defined in the Haskell Prelude.

In this example, we are thinking of the lists as representing
vectors, and we are computing the normal dot product of
two vectors.  What does your function do if the lists are
not of the same length? Justify your handling of this situation.
[Note that Haskell has its own version of ML's option type, which
is called Maybe:

   data Maybe = Nothing | Just a
]

(d) [10] Define

   flip :: (a -> b -> c) -> (b -> a -> c)
   flip f x y = f y x

Which of the following functions is more efficient, and why?

   appendr, appendl :: [[a]] -> [a]
   appendr = foldr (flip (++)) []
   appendl = foldl (flip (++)) []

(Hint. Be careful about the definition of foldl and foldr
in Haskell and consider the implications of your answer to
question 2(b) above.)


4. Lazy evaluation

(a) [5] Consider the program consisting of these three definitions:

    f () = f ()

    x = [f(), 3, 4]

    y = head x

Explain what happens when this program is evaluated.  Now
what happens if we add the following additional definition?

    z = y + 1


(b) [5] How many list cons operations are executed when
computing the value of the following expression:

    head([1,2,3,4,5,6,7,8,9,10]++[11,12])


(c) [10] Consider the program:

    x = [1,2,3,4,5,6,7,8,9,10]++[11,12]

    y = length(take 7 x)

    z = x !! 5

(xs !! n  returns the nth element of xs, starting with 0,
see page 196 of R.W.H.)

How many cons operations are performed in the execution
of this program?  How many would be performed if we
replaced 5 with 10 in the definition of z?

(d) [5] What happens in the following program?

    ones = 1 : ones

    x = head (reverse ones)


(d) [10] Describe the following infinite lists:

   xs = 1 : map (*2) xs

   ys = [1]:[zipWith (+) (0:q) (q++[0]) | q <- ys]

(you can test your understanding by taking the first
few elements of the lists).


(e) [10] Give a recursive definition of the sequence of Fibonacci
numbers using a list comprehension.