CSci 555: Functional Programming
Fall Semester 1998

Assignment #5
Due 16 November 1998

Proofs of Properties

• Do exercises 1, 2, 5, and 13 from section 11.7 of the Notes on Functional Programming with Gofer. (You may want to try some of the others in preparation for the examinations.)

Reduction Techniques

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.

Function definitions:

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

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

UP to CSCI 555 assignments document?