Skip to content

Instantly share code, notes, and snippets.

@voila voila/okasaki2.3.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
end
module IntOrd : Ord with type t = int =
struct
type t = int
let lt = (<)
let lte = (<=)
let eq = (=)
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 =
let rec insert_exc x = function
| Leaf -> Node (Leaf, x, Leaf)
| Node (a, y, b) ->
if Elt.lt x y then Node (insert_exc x a, y, b)
else if Elt.lt y x then Node (a, y, insert_exc x b)
else raise (Error "already inserted")
in try insert_exc x t
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 =
let rec member_aux x s z =
match s with
Leaf -> x = z
| Node(a, y, b) ->
if Elt.lt x y then member_aux x a z
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 =
for i = 1 to n do
(* print_int i; *)
s := (IntSet.insert i !s)
done
(*
let _ =
let s = (ref IntSet.empty) in
insert_ordered 1000 s;
let res =IntSet.member 1001 !s in
print_endline (string_of_bool res);
IntSet.insert 1000 !s
*)
let insert_random n max s =
(* 1 *) (* 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
ocamlprof chap2_4.ml > chap2_4_prof.ml
*)
let main () =
(* 1 *) (* 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.