CSE 505 Midterm

1. (16 points) Suppose the following Haskell code has been loaded. my_const k x = k my_map f [] = [] my_map f (x:xs) = f x : my_map f xs my_map2 f [] [] = [] my_map2 f (x:xs) (y:ys) = f x y : my_map2 f xs ys double x = 2*x mystery = 2 : my_map2 (*) mystery mystery What is the result of evaluting the following Haskell expressions? Give both the value and its type. If there is a compile-time type error, or a non-terminating computation, say so. If the result is an infinite data structure, give some initial parts of it. If Haskell would give an error of some sort rather than producing output, say so. my_const my_const "tuna" my_map (my_const "tuna") my_map double my_map double [1..] my_map (my_const "tuna") [1..] mystery my_map2 (+) [1..]

2. (8 points) Suppose the following ML functions have been defined. fun is_empty [] = true | is_empty (x::xs) = false; fun is_empty2 x = (x=[]); What is the result and type of evaluating the following expressions? If there is a type error say so. is_empty is_empty2 is_empty [fn x => 2*x] is_empty2 [fn x => 2*x]

3. (9 points) Suppose the following Scheme code has been loaded: (define x '(1 2 3)) (define y '(4 5 6)) (define (test a b) (set! a 100) (set-car! b 200) (list x y a b)) What is the result of evaluating (test x y)?

4. (9 points) Suppose the following Scheme code has been loaded: (define x 5) (define y 10) (define (test x) (+ x y)) (define (squid x) (lambda (z) (+ x y z))) (define func (squid 100)) What is the result of evaluating (test 100 200)?

   What is the result of evaluating (func 20)? Now suppose we evaluate

   (set! x 0) (set! y 0) Now what happens when we evaluate (func 20)?

5. (6 points) What is printed to the display when you evaluate the following Scheme expressions? (let ((x (write "hi there"))) x x (write "done")) (let ((f (lambda () (write "hi there")))) (f) (f) (write "done")) (let ((f (lambda () (write "hi there")))) f f (write "done"))

6. (10 points) Why do we care whether a Scheme function is tail-recursive? Give an example of a tail-recursive function, and a recursive function that is not tail recursive.

7. (10 points) Consider the following ML and Haskell functions. ML version: fun test x y = 2*y; Haskell version: test x y = 2*y Give an example expression that evaluates differently in ML and Haskell. Explain what happens in each case.

8. (12 points)Consider the following Haskell function: second x y = y Give a variable-free form of this function using Turner's algorithm and the S, K, and I combinators.

   Use this combinator code to evaluate

   second (1/0) 5