Reversing binary trees.

tree.sml

signature TREE =
sig
  type 'a tree
  type 'a many
  
  datatype 'a split = Pure of 'a | Many of 'a tree many
  
  val pure : 'a -> 'a tree
  val many : 'a tree many -> 'a tree
  val rev : 'a tree -> 'a tree
  val split : 'a tree -> 'a split
end

structure Tree2 : TREE =
struct
  datatype 'a tree = P of 'a | M of 'a tree many | R of 'a tree many
  withtype 'a many = 'a * 'a
  
  val pure = P
  val many = M
  fun rev (M xs) = R xs
    | rev (R xs) = M xs
    | rev xs = xs
  
  datatype 'a split = Pure of 'a | Many of 'a tree many
  
  fun split (P x) = Pure x
    | split (M xs) = Many xs
    | split (R (a, b)) = Many (rev b, rev a)
end