(* This code extends 'mini_prelude'. *) type ('a) times = Twice of ('a) times * ('a) times | Once of 'a ;; type ('a) digit = Two of ('a) times * ('a) times | One of ('a) times | Zero ;; type ('a) queue = Deep of ('a) digit * ('a) queue * ('a) digit | Shallow of ('a) digit ;; let empty = (Shallow (Zero)) ;; let is_empty = (fun v8 -> (match v8 with (Shallow (v4)) -> (match v4 with Zero -> true | (One (v1)) -> false | (Two (v3, v2)) -> false) | (Deep (v7, v6, v5)) -> false)) ;; let rec snoc x = (fun x1 -> (match x with (Shallow (v4)) -> (match v4 with Zero -> (Shallow ((One (x1)))) | (One (v1)) -> (Deep ((Two (v1, x1)), empty, Zero)) | (Two (v3, v2)) -> (raise (Match_failure (string_of_bool true, 0, 0)))) | (Deep (v10, v9, v8)) -> (match v8 with Zero -> (Deep (v10, v9, (One (x1)))) | (One (v5)) -> (Deep (v10, ((snoc v9) (Twice (v5, x1))), Zero)) | (Two (v7, v6)) -> (raise (Match_failure (string_of_bool true, 0, 0)))))) ;; let head = (fun x -> (match x with (Shallow (v4)) -> (match v4 with Zero -> (raise (Match_failure (string_of_bool true, 0, 0))) | (One (v1)) -> v1 | (Two (v3, v2)) -> (raise (Match_failure (string_of_bool true, 0, 0)))) | (Deep (v10, v9, v8)) -> (match v10 with Zero -> (raise (Match_failure (string_of_bool true, 0, 0))) | (One (v5)) -> v5 | (Two (v7, v6)) -> v7))) ;; let rec tail x = (match x with (Shallow (v4)) -> (match v4 with Zero -> (raise (Match_failure (string_of_bool true, 0, 0))) | (One (v1)) -> empty | (Two (v3, v2)) -> (raise (Match_failure (string_of_bool true, 0, 0)))) | (Deep (v13, v12, v11)) -> (match v13 with Zero -> (raise (Match_failure (string_of_bool true, 0, 0))) | (One (v8)) -> (if (is_empty v12) then (Shallow (v11)) else (match (head v12) with (Once (v5)) -> (raise (Match_failure (string_of_bool true, 0, 0))) | (Twice (v7, v6)) -> (Deep ((Two (v7, v6)), (tail v12), v11)))) | (Two (v10, v9)) -> (Deep ((One (v9)), v12, v11)))) ;;