- (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 => <> :: a -> b -> a
my_const "tuna" => <> :: a -> [Char]
my_map (my_const "tuna") => <> :: [a] -> [[Char]]
my_map double => <> :: [Int] -> [Int]
my_map double [1..] => [2, 4, 6, 8, 10, 12, 14, 16, ...] :: [Int]
my_map (my_const "tuna") [1..] => ["tuna", "tuna", "tuna", ...] :: [[Char]]
mystery => [2, 4, 16, 256, 65536, ...] :: [Int]
my_map2 (+) [1..] => <> :: [Int] -> [Int]
- (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 => val it = fn : 'a list -> bool
is_empty2 => val it = fn : ''a list -> bool
is_empty [fn x => 2*x] => val it = false : bool
is_empty2 [fn x => 2*x] => type error
- (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)?
((1 2 3) (200 5 6) 100 (200 5 6))
- (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)?
The result (unfortunately) is "error: the procedure takes one argument but
was given two". (test 100) evaluates to 110. (I threw this
question out.)
What is the result of evaluating (func 20)? => 130
Now
suppose we evaluate
(set! x 0)
(set! y 0)
Now what happens when we evaluate (func 20)? => 120
- (6 points) What is printed to the display when you evaluate the
following Scheme expressions?
(let ((x (write "hi there")))
x
x
(write "done"))
=>"hi there""done"
(let ((f (lambda () (write "hi there"))))
(f)
(f)
(write "done"))
=> "hi there""hi there""done"
(let ((f (lambda () (write "hi there"))))
f
f
(write "done"))
=> "done"
- (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.
A tail-recursive function is one in which the result of the recursive call
is also the result returned by the function call. Tail-recursive functions
can be compiled using jumps, so that they execute with the same efficiency
as a loop; they don't consume stack space with each recursive call. Part
of the language specification for Scheme is that implementations do tail
recursion optimization.
;; a tail recursive function
(define (member x s)
(cond ((null? s) #f)
((eqv? x (car s)) #t)
(else (member x (cdr s)))))
;; a function that isn't tail recursive
(define (factorial n)
(if (zero? n) 1 (* n (factorial (- n 1)))))
- (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.
test (1/0) 5 evaluates to 5 in Haskell, and gives a
divide-by-zero error in ML. Haskell uses lazy evaluation. Since the
formal parameter x is never used in test, (1/0) is never
evaluated and so the function returns successfully. ML uses call-by-value,
and so (1/0) is evaluated when the function is called, even
though the value wouldn't be used, and so there is an error.
- (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.
second x y = y
abstract x and y from each side:
second = [x] ([y] y)
= [x] (I)
= K I
Use this combinator code to evaluate
second (1/0) 5
K I (divide 1 0) 5 =>
I 5 (using definition of K) =>
5 (using definition of I)
Note that the function was evaluated using lazy evaluation, so the
divide-by-zero error did not occur.