CSci 555: Functional Programming
Spring Semester 2000

Assignment #6
Due Tuesday, 2 May, 2000

This is an individual assignment, which you must complete in accordance with the instructions given in the Professional Conduct and Assignments sections of the Syllabus .

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 are the time and space required now?
   3. Replace foldr by foldl'. What are 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?