[SOLVED] CS Lambda Calculus CSE 130 Midterm Solution, Spring 2018

CSE 130 Midterm Solution, Spring 2018
Nadia Polikarpova May 4, 2018
Part I. Lambda Calculus [60 pts]
Q1: Reductions [20 pts]
1.1 [5 pts]
(x -> x (x -> x)) (f x)
(A) =b> f x (x -> x) valid
(B) =b>fx(x->fx)
(C) =b>fx(fx->fx)
(D) =a>(y->y(x->x))(fy)
(E) =a> (x -> x (y -> y)) (f x) valid
1.2 [5 pts]
x -> (y z -> x y) (x -> x)
(A) =a>x->(yx->xx)(x->x)
(B) =a>a->(yz->ay)(x->a)
(C) =*> a -> (y z -> a y) (a -> a) valid (D) =b> x z -> x (x -> x) valid
1

(E) =b>yz->(x->x)y 1.3 [5 pts]
(f g x -> f (g x)) (x -> g x) (z -> z)
(A) =b>(fgx->f(gx))(g(z->z))
(B) =b>(gx->(x->gx)(gx))(z->z) (C) =*> x -> g x valid
(D) =*> y -> g y valid
(E) =*>x->fx
1.4 [5 pts]
(x y -> b u v -> b v u) (x y -> y) (x y -> y) (x y -> x) (A) =b> (y -> b u v -> b v u) (x y -> y) (x y -> x) valid (B) =b>(y->buv->bvu)(xy->y)(xy->y)
(C) =*> (b u v -> b v u) (x y -> x) valid
(D) =*> x y -> y valid
(E) =b>y->(xy->y)(xy->y)(xy->x)
Q2: Lists [40 pts]
2.1 Repeat [10 pts]
let REPEAT =
x -> n (PAIR x) FALSE
2.2 Empty* [20 pts]
let EMPTY = xs -> xs (x y z -> FALSE) TRUE 2

Alternatively:
let EMPTY = xs -> xs (x y -> NOT) TRUE 2.3 Length [10 pts]
let LEN = FIX (rec l -> ITE (EMPTY l) ZERO (INC (rec (SND l)))) Part II. Datatypes and Recursion [50 pts]
Q3: Binary Search Trees [50 pts] 3.1 Size [5 pts]
size :: Tree -> Int
size Empty = 0
size (Node _ l r) = 1 + size l + size r
3.2 Insert [10 pts]
insert :: Int -> Tree -> Tree
insert x Empty = Node x Empty Empty
insert x (Node y l r)
|x==y =Nodeylr
|x [Int]
sort xs = toList (fromList xs)
where
fromList :: [Int] -> Tree
fromList [] = Empty
3

fromList (x:xs) = insert x (fromList xs)
toList :: Tree -> [Int]
toList Empty = []
toList (Node x l r) = toList l ++ [x] ++ toList r
3.4 Tail-recursive size* [20 pts]
size :: Tree -> Int
size t = loop 0 [] t
where
loop :: Int -> [Tree] -> Tree -> Int
loop acc [] Empty = acc
loop acc (t:ts) Empty = loop acc ts t loopaccts (Node_lr)=loop(acc+1)(r:ts)l
Alternatively:
size :: Tree -> Int
size t = loop 0 Empty t
where
loop :: Int -> Tree -> Tree -> Int
loop acc EmptyEmpty
loop acc (Node _ l r) Empty
loop acc t(Node x l r) = loop acc(Node x t r) l
4
= acc
= loop (acc + 1) l r