Inserting binomial tree

insertTree.ml

(*
  Links two trees of same rank r. The resulting tree has rank r + 1
*)
let link (tree1: tree) (tree2: tree) = match (tree1, tree2) with
  (Node (node1, children1), Node (node2, children2)) ->
    if (Element.compare node1 node2) <= 0
      then Node (node1, tree2 :: children1)
      else Node (node2, tree1 :: children2)
;;

(*
  Insert a tree into a stream of digits. This assumes that
  the rank of the tree being inserted has the rank corresponding to the
  position of the current digits.

  This is analogous to the carrying over operation of adding a 1 to a binary
  number. For example, if we are to add 1 to 1011, then we'll have

  101(11) -> match One, link -> 10(11)0
  10(11)0 -> match One, link -> 1(1)00
  1(1)00 -> match Zero -> 1100
*)
let rec insertTree (tree: tree) (digits: digit stream): digit stream =
  match digits with
    | lazy Nil -> Stream.empty |> Stream.insert (One tree)
    | lazy (StreamCell (firstDigit, rest)) -> match firstDigit with
      | Zero -> Stream.insert (One tree) rest
      | One firstTree ->
        lazy (StreamCell (Zero, (insertTree (link tree firstTree) rest)))
;;