CSci 555: Functional Programming
Spring Semester 1997

Assignment #6
Due Wednesday, 16 April

1. Show the requested reduction sequences for the following expression, counting the number of reduction steps in each case (if it terminates).

           cube (cube 3)
   

   1. Applicative order string reduction
   2. Normal order string reduction.
   3. Normal order graph reduction.

2. Show the requested reduction sequences for the following expression, counting the number of reduction steps in each case (if it terminates).

           map (1+) (map (2*) [1,2,3])
   

   1. Applicative order string reduction
   2. Normal order string reduction.

3. Show the requested reduction sequences for the following expression, counting the number of reduction steps in each case (if it terminates).

           head ([1,2,3] ++ loop 1)
   

   1. Applicative order string reduction
   2. Normal order string reduction.

4. Consider the expression foldr (||) False (copy n True)
   1. In terms of n (where n >= 0), what is the time and space required for the expression using normal order reduction?
   2. Replace foldr by foldl. What the time and space required now?
   3. Replace foldr by foldl'. What the time and space required now?

Function definitions:

    cube :: Int -> Int
    cube x = x * x * x                               -- cube

    loop :: Int -> [a]
    loop n = loop (n+1)                              -- loop

    copy Int -> a - > [a]
    copy 0 x         = []                            -- copy.1
    copy n x | n > 0 = x : copy (n-1) x              -- copy.2

    (++) :: [a] -> [a] -> [a]
    [] ++ ys     = ys                                -- append.1
    (x:xs) ++ ys = x:(xs ++ ys)                      -- append.2

    map :: (a -> b) -> [a] -> [b]
    map f []     = []                                -- map.1
    map f (x:xs) = f x : map f xs                    -- map.2

    foldr :: (a -> b -> b) -> b -> [a] -> b
    foldr f z []     = z                             -- foldr.1
    foldr f z (x:xs) = f x (foldr f z xs)            -- foldr.2

    foldl :: (a -> b -> a) -> a -> [b] -> a
    foldl f z []     = z                             -- foldl.1
    foldl f z (x:xs) = foldl f (f z x) xs            -- foldl.2

    foldl' :: (a -> b -> a) -> a -> [b] -> a
    foldl' f z []     = z                            -- foldl'.1
    foldl' f z (x:xs) = strict (foldl' f) (f z x) xs  -- foldl'.2

    head :: [a] -> a
    head (x:xs) = x

UP to CSCI 555 assignments document?