David Stone's Blog

I'm open to suggestions for a subtitle here! (Really!)

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)

Comments

chinese-tea-supplier said:

thanks for your share.

# February 25, 2010 2:29 AM