lookup.ml

let rec lookup: 'a. int -> 'a seq -> 'a =
  fun index digits -> match (index, digits) with
    | (index, Nil) -> raise IndexOutOfBoundsException
    (* Case 1 *)
    | (0, One (elem, restDigits)) -> elem
    (* Case 2 *)
    | (index, One (_, restDigits)) -> lookup (index - 1) (Zero restDigits)
    (* Case 3 *)
    | (index, Zero restDigits) ->
      let (left, right) = lookup (index / 2) restDigits
      in if index mod 2 == 0 then left else right