CSE 130 Final Solution, Spring 2018
Nadia Polikarpova June 11, 2018
Q1: Lambda Calculus: Sets [20 pts] 1.1 Empty set [5 pts]
let EMPTY = \x -> FALSE
1.2 Insert an element [5 pts]
let INSERT = \n s x -> ITE (EQL n x) TRUE (s x) Alternatively:
let INSERT = \n s x -> OR (EQL n x) (s x)
1.3 Membership [5 pts]
let HAS = \s x -> s x 1.4 Set intersection [5 pts]
let INTERSECT = \s1 s2 x -> AND (s1 x) (s2 x)
1
Q2: Datatypes and Recursion: Decision Trees [60 pts] 2.1 Evaluation [10 pts]
eval :: Env -> BDT -> Bool
eval _ (Leaf b) = b
eval env (Node x tt tf) =
if lookup x env then eval env tt else eval env tf
2.2 Negation [15 pts]
tNot :: BDT -> BDT
tNot (Leaf b) = Leaf (not b)
tNot (Node x tt tf) = Node x (tNot tt) (tNot tf)
2.3 Conjunction [15 pts]
tAnd :: BDT -> BDT -> BDT
tAnd (Leaf False) _ = Leaf False
tAnd (Leaf True) t = t
tAnd (Node x tt tf) t = Node x (tAnd tt t) (tAnd tf t)
2.4 Ordered BDTs* [20 pts]
tAndOrd :: BDT -> BDT -> BDT
tAndOrd (Leaf False) _ = Leaf False
tAndOrd (Leaf True) t = t
tAndOrd _
tAndOrd t
tAndOrd l@(Node x lt lf) r@(Node y rt rf)
| x < y
| x > y
| x == y
= Node x (tAndOrd lt r) (tAndOrd lf r)
= Node y (tAndOrd tr l) (tAndOrd rf l)
= Node x (tAndOrd lt rt) (tAndOrd lf rf)
2
(Leaf False) = Leaf False
(Leaf True) = t
Q3: Higher-Order Functions [20 pts] 3.1 List reversal [5 pts]
reverse :: [a] -> [a]
reverse xs = foldl (\res x -> x : res) [] xs
3.2 Absolute values [10 pts]
absValues :: [Int] -> [Int]
absValues = map (\x -> if x < 0 then -x else x)
3.3 Remove duplicates [15 pts]
dedup :: [Int] -> [Int]
dedup = foldr insert []
where
insert x ys = x : (filter (/= x) ys) 3.4 Insertion Sort* [20 pts]
sort :: [Int] -> [Int]
sort xs = foldl insert [] xs
where
insert ys x = append (filter (< x) ys) (x : filter (>= x) ys)
append xs ys = foldr (:) ys xs
3
Q4: Semantics and Type Systems [30 pts]
4.1 Reduction 1 [10 points]
E = [f -> <[], \x y -> x + y>]
[Var] ————————
E, f => E, <[], \x y -> x + y>
[App-L] ——————————– E,f1 => E,<[],\xy->x+y>1 [App-L] ————————————
E,f12 => E,<[],\xy->x+y>12 4.2 Reduction 2 [10 points]
E = [f -> <[], \x y -> x + y>]
[App] ————————————————— E,<[],\xy->x+y>1 => [x->1],\y->x+y
[App-L] ——————————————————— E,<[],\xy->x+y>12 => [x->1],(\y->x+y)2
4.3 Typing 1 [10 points]
[T-Var] ——————- ——————-[T-Num]
[x:Int] |- x :: Int [x:Int] |- 5 :: Int
[T-Add] ———————————————
[x:Int] |- x + 5 :: Int
[T-Abs] ——————————-
[] |- \x -> x + 5 :: Int -> Int
4.4 Typing 2 [10 points]
G = [id -> forall a. a -> a, f -> Int -> Int]
4
[T-Var] ———————————–
G |- id :: forall a . a -> a
[T-Inst] ————————————- ——————-[T-Var]
G |- id :: (Int -> Int) -> Int -> Int G |- f :: Int -> Int
[T-App] ———————————————–
G |- id f :: Int -> Int
5
Q5: Prolog: Selection sort [30 pts] 5.1 Insert [10 points]
insert(X, Ys, [X|Ys]).
insert(X, [Y|Ys], [Y|Zs]) :- insert(X, Ys, Zs).
5.2 Minimum element [10 points]
list_min(A, [], A). list_min(A, [X|Xs], Min) :-
A1 is min(A, X), list_min(A1, Xs, Min).
5.3 Selection Sort [10 points]
selection_sort([],[]). selection_sort([X|Xs],[Y|Ys]) :- list_min(X, Xs, Y)
, insert(Y,Zs,[X|Xs])
, selection_sort(Zs,Ys).
6