Skip to content

Instantly share code, notes, and snippets.

@voila voila/okasaki2.4.ml
Created Dec 18, 2013

Embed
What would you like to do?
open Printf
module type Ord =
sig
type t
val lt : t -> t -> bool
val lte : t -> t -> bool
val eq : t -> t -> bool
val succ : t -> t
end
module IntOrd : Ord with type t = int =
struct
type t = int
let lt = (<)
let lte = (<=)
let eq = (=)
let succ x = (* 1001 *) x + 1
end
module type Set =
sig
type elem
type set
val empty : set
val insert : elem -> set -> set
val member : elem -> set -> bool
end
module UnbalSet(Elt : Ord) : Set with type elem = Elt.t =
struct
type elem = Elt.t
type 'a tree =
Leaf
| Node of 'a tree * 'a * 'a tree
type set = elem tree
exception Error of string
let empty = Leaf
(* if the x exists in t, we raise an exception and return t *)
let insert x t =
(* 1001 *) let rec insert_exn x z = function
| Leaf ->
(* 1001 *) if x = z then raise (Error "already inserted")
else Node (Leaf, x, Leaf)
| Node (a, y, b) ->
(* 500500 *) if Elt.lt x y then Node (insert_exn x z a, y, b)
else Node (a, y, insert_exn x y b)
in try insert_exn x (Elt.succ x) t (* so we're sure x <> z *)
with Error s -> print_endline s; t
(* we assume x is strictly < or > to any node value
when we reach a leaf we check x equality with the last node
x was superior to, z *)
let member x s =
(* 1 *) let rec member_aux x s z =
(* 1001 *) match s with
| Leaf -> x = z
| Node(a, y, b) ->
if Elt.lt x y then
member_aux x a z
(* could be x = y, but we assume x > y, and pass down y
so we can do check if x = y, when we reach a Leaf *)
else
member_aux x b y
in
match s with
| Leaf -> false
| Node(_, y, _) -> member_aux x s y
end
module IntSet = UnbalSet (IntOrd)
let insert_ordered n s =
(* 1 *) for i = 1 to n do
(* print_int i; *)
s := (IntSet.insert i !s)
done
let insert_random n max s =
(* 1 *) for i = 1 to n do
(* print_int i; *)
s := (IntSet.insert (Random.int max) !s)
done
(*
ocamlcp -p f chap2_4.ml -o chap2_4
ocamlrun chap2_4
ocamlprof chap2_4.ml > chap2_4_prof.ml
*)
let main () =
(* 1 *) let s = (ref IntSet.empty) in
insert_random 10000 100000 s
(*
let res = IntSet.member 1001 !s in
print_endline (string_of_bool res);
IntSet.insert 1000 !s
*)
let _ = main ()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.