David Stone's Blog

CSE 130 Sample Final Answers

1. Ocaml Types
   1. ans:int = 804
   2. type error
   3. ans:int = 100
   4. ans:int = 20
2. Function Type / Write reverse
1. 'a -> 'a * 'a -> bool * 'a -> 'a
2. let reverse l =
1. let f (c,b) = match c with [] -> ([], b) | h::t -> (t, h::b) in
2. let g (l, acc) = match l with [] -> false | h::t -> true in
3. let base = (l, []) in
3. Semantic Equivalence
1. Semantically Equivalent because addition is transitive
2. Not Semantically Equivalent because g is not defined in e2
3. Semantically Equivalent because multiplication is transitive
4. OCaml Module
1. Part A
1. Signature B
2. Stack.top [];;
3. Because signature A says that 'a stack = 'a list, you can call any function on 'a stack on an 'a list instead. This allows Stack.top to be called on [], which will throw the EmptyStack exception. When using signature B, you must call Stack.make, and it will never give you back an empty list.
2. Part B
1. Signature A
2. Inferred Type: 'a stk -> 'a list
3. Part C
1. Doesn't work
5. Boolean Formulas
1. type boolexp = Var of int | Not of boolexp | Or of boolexp * boolexp | And of boolexp * boolexp
   And(Or(Var(0), Not(Var(1))), Or(Var(1), Not(Var(2))))
2. let rec eval(list, expr) =
       let rec find (list, index) =
           if(index = 0) then List.hd(list)
           else find(List.tl list, index - 1) in
       match expr with
           Var(i) -> find(list, i)
           |Not(v) -> !eval(list, v)
           |And(a1,a2) -> eval(list, a1) && eval(list, a2)
           |Or(a1,a2) -> eval(list,a1) || eval(list,a2)