tree.ml

module Tree = struct
  
  type z = Z : z
  type 'a s = S : 'a s

  type (_,_,_) max =
  | MaxEq : 'a -> ('a,'a,'a) max
  | MaxSuc : ('a, 'b, 'a) max -> ('a s, 'b, 'a s) max
  | MaxFlip : ('a, 'b, 'c) max -> ('b, 'a, 'c) max

  let z =  (MaxEq Z) |> MaxSuc |> MaxSuc  |> MaxSuc |> MaxSuc |> MaxFlip 


  type ('a, _) tree =
  | Nil : ('a, z) tree
  | Node : 'a * ('a, 'num) tree * ('a, 'num) tree -> ('a, 'num s) tree


  let test1_ = Nil

  let test2 = Node ("xyz", Nil, Nil)

  let test3 = Node ("a", test2, Node ("b", Nil, Nil))

  let top : type a b. (b, a s) tree -> b = function
   | Node (k, _, _) -> k

  let rec len : type a. (_, a) tree -> int = function
   | Node (_, lhs, _) -> 1 + len lhs
   | Nil -> 0
end