type num = int -> int type contents = Num of num | Op of (num -> num) | Op2 of (num -> num -> num) type tree = Leaf of contents | Branch of tree * tree | Error let mid x = fun _ -> x (* K combinator *) let map f xx = fun n -> f (xx n) (* function composition, that is the B combinator *) let mapply ff xx = fun n -> (ff n) (xx n) (* S combinator *) let map2 f xx yy = fun n -> f (xx n) (yy n) let rec eval (t : tree) = match t with | Leaf _ -> t | Branch (Leaf (Op f), right) -> (match (eval right) with | Leaf (Num n) -> Leaf (Num (f n)) | _ -> Error) | Branch (Leaf (Op2 f), right) -> (match (eval right) with | Leaf (Num n) -> Leaf (Op (f n)) | _ -> Error) | Branch (left, right) -> eval (Branch (eval left, eval right)) | _ -> Error (* To use infix operators in ordinary prefix position, use (+). Multiplication has to be handled a bit specially, because of how OCaml parses its comment indicators. To use it in prefix position, make sure there is space between it and the parentheses, like this: ( * ). *) (* Encoding of (+ 1 ( * (/ 6 n) 4)) *) let t1 = Branch ((Branch ((Leaf (Op2 (map2 (+)))), (Leaf (Num (mid 1))))), (Branch ((Branch ((Leaf (Op2 (map2 ( * ))), (Branch ((Branch ((Leaf (Op2 (map2 (/)))), (Leaf (Num (mid 6))))), (Leaf (Num (fun n -> n)))))))), (Leaf (Num (mid 4))))));; (* Now evaluate: match eval t1 with Leaf (Num f) -> f 2;; The answer should be 13. *)