Week 13: Exercises

1. Lazy Multiplication

Consider this function:

square :: Int -> Int

square n = n * n

double_square :: Int -> Int
double_square n = square (square n)

How many multiplications will double_square perform? The answer may not be completely obvious due to Haskell's lazy evaluation. It will call the outer 'square' before it evaluates the inner 'square'. So it might evaluate double_square 3 like this:

   double_square 3
-> square (square 3)
-> (square 3) * (square 3)
-> (3 * 3) * (3 * 3)
-> 81

In the sequence above there appear to be 3 multiplication operations.

Design an experiment to determine how many multiplications actually occur.

2. To Let or Not To Let

Consider these two functions, which always produce the same value for any input:

sub :: [a] -> [a]
sub [] = []
sub (x : xs) = sub xs ++ map (x:) (sub xs)

sub' :: [a] -> [a]
sub' [] = []
sub' (x : xs) =
  let xss = sub' xs
  in xss ++ map (x:) xss

a) What do the functions do?

b) Now consider these functions:

count :: Int -> Int
count n = sum (concatMap sub [1 .. n]))

count' :: Int -> Int
count' n = sum (concatMap sub' [1 .. n]))

Do you think their time and memory usage will be identical, similar, or very different?