val equal : t -> t -> bool
val nil : t
val node : t -> t node
- val cons : elt -> t -> t
+ val cons : ?sorted:bool -> elt -> t -> t
val hd : t -> elt
val tl : t -> t
val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
let nil = Node.make Nil
(* doing sorted insertion allows to make better use of hash consing *)
- let rec cons e l =
+ let rec sorted_cons e l =
match l.Node.node with
| Nil -> Node.make (Cons(e, l))
| Cons (x, ll) ->
if H.uid e < H.uid x
then Node.make (Cons(e, l))
- else Node.make (Cons(x, cons e ll))
+ else Node.make (Cons(x, sorted_cons e ll))
+
+ let cons e l =
+ Node.make(Cons(e, l))
+
+ let cons ?(sorted=true) e l =
+ if sorted then sorted_cons e l else cons e l
let hd = function { Node.node = Cons(a,_) } -> a | _ -> failwith "hd"
let tl = function { Node.node = Cons(_,a) } -> a | _ -> failwith "tl"