Advertisement
Guest User

OCaml Binary Tree Catamorphism

a guest
Jun 21st, 2019
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
OCaml 0.38 KB | None | 0 0
  1. type 'a tree = Br of 'a * 'a tree * 'a tree | Lf    
  2.  
  3. let rec cata map_lf map_br t =
  4.     match t with
  5.     | Lf -> map_lf ()
  6.     | Br (x, l, r) ->
  7.         let reduced = cata map_lf map_br (Br (x, l, r)) in
  8.         map_br reduced
  9.        
  10. let fold_right op tree init = cata
  11.     (fun unit -> init)
  12.     (fun value -> op value)
  13.     tree
  14.  
  15. let size t = fold_right (fun x -> 1 + x) t 0
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement