open Batteries

class virtual ['i] number = object(self : 'a)
  method virtual succ : 'a
  method virtual pred : 'a option
  method virtual get_data : 'i
end



type 'i lazy_number_data =
  | Number of 'i number
  | Zero
  | Succ of 'i lazy_number_data
  | Sum of 'i lazy_number_data * 'i lazy_number_data

class ['i] lazy_number data0 = object
  inherit (['i] number)
  val data = data0
  method succ = {< data = Succ data >}
  method pred =
    let rec aux = function
      | Number x -> x#pred |> Option.map (fun t -> Number t)
      | Zero -> None
      | Succ x -> Some x
      | Sum (x1, x2) -> begin
          match aux x1 with
          | None -> aux x2
          | Some x1' -> Some (Sum (x1', x2))
        end
    in
    match aux data with
    | None -> None
    | Some data' -> Some {< data = data' >}
  method get_data = `Lazy data
end

let lazy_number_data_of_number x =
  match x#get_data with
  | `Lazy x' -> x'
  | _ -> Number x

let lazy_sum x y =
  let lazy_x = lazy_number_data_of_number x in
  let lazy_y = lazy_number_data_of_number y in
  new lazy_number (Sum (lazy_x, lazy_y))



type unary_number_data =
  | O
  | S of unary_number_data

class ['i] unary_number data0 = object
  inherit (['i] number)
  val data = data0
  method succ = {< data = S data >}
  method pred =
    match data with
    | O -> None
    | S data' -> Some {< data = data' >}
  method get_data = `Unary data
end

let rec unary_number_data_of_number x =
  match x#get_data with
  | `Unary x' -> x'
  | _ -> begin
      let rec aux t =
        match t#pred with
        | None -> O
        | Some t' -> S (aux t')
      in
      aux x
    end

let unary_sum x y =
  let unary_sum_number_unary_number_data x0 y0 =
    let rec aux x =
      match x#pred with
      | None -> y0
      | Some x' -> S (aux x')
    in
    aux x0
  in
  match x#get_data, y#get_data with
  | `Unary x', _ -> unary_sum_number_unary_number_data y x'
  | _, `Unary y' -> unary_sum_number_unary_number_data x y'
  | _ -> unary_sum_number_unary_number_data x (unary_number_data_of_number y)

let _ =
  let one = new unary_number (S O) in
  let two = new lazy_number (Sum ((Succ Zero), (Succ Zero))) in
  let three = lazy_sum one two in
  ()