(* This code extends 'mini_prelude'. *)

let empty = Nil ;;

let is_empty = 
  (fun v3 -> 
    (match v3 with 
        Nil -> true 
      | (Cons (v2, v1)) -> false)) ;;

type ('a) tree = 
    Node of int * ('a) tree * ('a) tree 
  | Leaf of 'a ;;

let size = 
  (fun v5 -> 
    (match v5 with 
        (Leaf (v1)) -> 1 
      | (Node (v4, v3, v2)) -> v4)) ;;

let link = 
  (fun v1 -> 
    (fun v2 -> (Node (((size v1) + (size v2)), v1, v2)))) ;;

type ('a) digit = 
    One of ('a) tree 
  | Zero ;;

let rec cons_tree v4 = 
  (fun v5 -> 
    (match v5 with 
        Nil -> (Cons ((One (v4)), Nil)) 
      | (Cons (v3, v2)) -> 
          (match v3 with 
              Zero -> (Cons ((One (v4)), v2)) 
            | (One (v1)) -> (Cons (Zero, ((cons_tree ((link v4) v1)) v2)))))) ;;

let rec uncons_tree x = 
  (match x with 
      Nil -> (raise (Match_failure (string_of_bool true, 0, 0))) 
    | (Cons (v11, v10)) -> 
        (match v11 with 
            Zero -> 
              (match (uncons_tree v10) with 
                  (Pair (v6, v5)) -> 
                    (match v6 with 
                        (Leaf (v1)) -> (raise (Match_failure (string_of_bool true, 0, 0))) 
                      | (Node (v4, v3, v2)) -> (Pair (v3, (Cons ((One (v2)), v5)))))) 
          | (One (v9)) -> 
              (match v10 with 
                  Nil -> (Pair (v9, Nil)) 
                | (Cons (v8, v7)) -> (Pair (v9, (Cons (Zero, (Cons (v8, v7))))))))) ;;

let cons = 
  (fun v2 -> 
    (fun v1 -> ((cons_tree (Leaf (v2))) v1))) ;;

let head = 
  (fun v7 -> 
    (match (uncons_tree v7) with 
        (Pair (v6, v5)) -> 
          (match v6 with 
              (Leaf (v1)) -> v1 
            | (Node (v4, v3, v2)) -> (raise (Match_failure (string_of_bool true, 0, 0)))))) ;;

let tail = 
  (fun v4 -> 
    (let v3 = (uncons_tree v4) 
    in 
      (match v3 with 
          (Pair (v2, v1)) -> v1))) ;;

let rec lookup_tree x1 = 
  (fun x2 -> 
    (match x2 with 
        (Leaf (v1)) -> 
          (if (x1 <= 0) 
          then v1 
          else (raise (Match_failure (string_of_bool true, 0, 0)))) 
      | (Node (v4, v3, v2)) -> 
          (if (x1 < (v4 / 2)) 
          then ((lookup_tree x1) v3) 
          else ((lookup_tree 
            (let k = (x1 - (v4 / 2)) 
            in 
              (if (k < 0) 
              then 0 
              else k))) v2)))) ;;

let rec update_tree x1 = 
  (fun x2 -> 
    (fun x3 -> 
      (match x3 with 
          (Leaf (v1)) -> 
            (if (x1 <= 0) 
            then (Leaf (x2)) 
            else (raise (Match_failure (string_of_bool true, 0, 0)))) 
        | (Node (v4, v3, v2)) -> 
            (if (x1 < (v4 / 2)) 
            then (Node (v4, (((update_tree x1) x2) v3), v2)) 
            else (Node (v4, v3, (((update_tree 
              (let k = (x1 - (v4 / 2)) 
              in 
                (if (k < 0) 
                then 0 
                else k))) x2) v2))))))) ;;

let rec lookup x = 
  (fun x1 -> 
    (match x1 with 
        Nil -> (raise (Match_failure (string_of_bool true, 0, 0))) 
      | (Cons (v3, v2)) -> 
          (match v3 with 
              Zero -> ((lookup x) v2) 
            | (One (v1)) -> 
                (if (x < (size v1)) 
                then ((lookup_tree x) v1) 
                else ((lookup 
                  (let k = (x - (size v1)) 
                  in 
                    (if (k < 0) 
                    then 0 
                    else k))) v2))))) ;;

let rec update x = 
  (fun x1 -> 
    (fun x2 -> 
      (match x2 with 
          Nil -> (raise (Match_failure (string_of_bool true, 0, 0))) 
        | (Cons (v3, v2)) -> 
            (match v3 with 
                Zero -> (Cons (Zero, (((update x) x1) v2))) 
              | (One (v1)) -> 
                  (if (x < (size v1)) 
                  then (Cons ((One ((((update_tree x) x1) v1))), v2)) 
                  else (Cons ((One (v1)), (((update 
                    (let k = (x - (size v1)) 
                    in 
                      (if (k < 0) 
                      then 0 
                      else k))) x1) v2)))))))) ;;