2 type contents = Num of num | Op of (num -> num) | Op2 of (num -> num -> num)
3 type tree = Leaf of contents | Branch of tree * tree | Error
5 let mid a = fun _ -> a;; (* K *)
7 let map2 f u v x = f (u x) (v x);; (* S *)
9 let rec eval (t:tree) = match t with
11 | Branch (Leaf (Op f), b2) -> (match (eval b2) with
12 | Leaf (Num n) -> Leaf (Num (f n))
14 | Branch (Leaf (Op2 f), b2) -> (match (eval b2) with
15 | Leaf (Num n) -> Leaf (Op (f n))
17 | Branch (b1, b2) -> eval (Branch (eval b1, eval b2))
21 (* to get an arithmetic function, type, e.g., "(+)".
22 to get times instead of comment, type "( * )". *)
24 (* Encoding of (+ 1 (* (/ 6 x) 4)) *)
25 let t1 = Branch ((Branch ((Leaf (Op2 (map2 (+)))),
26 (Leaf (Num (mid 1))))),
27 (Branch ((Branch ((Leaf (Op2 (map2 ( * ))),
28 (Branch ((Branch ((Leaf (Op2 (map2 (/)))),
29 (Leaf (Num (mid 6))))),
30 (Leaf (Num (fun x -> x)))))))),
31 (Leaf (Num (mid 4))))));;
36 match eval t1 with Leaf (Num f) -> f 2;;
38 The answer should be 13.