Advertisement
Guest User

OCaml Binary Tree Catamorphism

a guest
Jun 22nd, 2019
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
OCaml 0.72 KB | None | 0 0
  1. type 'a tree = Br of 'a * 'a tree * 'a tree | Lf
  2.  
  3. let a_tree =
  4.     Br (
  5.         (3, "three"),
  6.  
  7.         Br (
  8.             (1, "one"), Lf, Br ((2, "two"), Lf, Lf)
  9.         ),
  10.  
  11.         Br ((4, "four"), Lf, Lf)
  12.     )
  13.  
  14. let rec cata f_lf f_br t =
  15.     match t with
  16.     | Lf -> f_lf ()
  17.     | Br (x, l, r) ->
  18.         f_br x (cata f_lf f_br l) (cata f_lf f_br r)
  19.        
  20. let fold_right op tree init = cata
  21.     (fun unit -> init)
  22.     (fun value l r -> op value l r)
  23.     tree
  24.  
  25. let size (t : 'a tree) : int = fold_right (fun x y z -> x+y+z) t 0
  26.  
  27. let count = size a_tree
  28. (* This expression has type (int * string) tree
  29.    but an expression was expected of type int tree
  30.    Type int * string is not compatible with type int *)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement