4 type 'a node = Nil | Cons of elt * 'a
8 include Hcons.S with type data = Data.t
11 include Hashtbl.HashedType with type t = Node.t node
18 val equal : t -> t -> bool
20 val node : t -> t node
21 val cons : ?sorted:bool -> elt -> t -> t
24 val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
25 val map : (elt -> elt) -> t -> t
26 val iter : (elt -> 'a) -> t -> unit
28 val rev_map : (elt -> elt) -> t -> t
30 val mem : elt -> t -> bool
34 module Make (H : Hcons.SA) : S with type elt = H.t =
37 type 'a node = Nil | Cons of elt * 'a
38 module rec Node : Hcons.S with type data = Data.t = Hcons.Make (Data)
39 and Data : Hashtbl.HashedType with type t = Node.t node =
44 | _,_ when x==y -> true
45 | Cons (a,aa), Cons(b,bb) -> (aa==bb) && (H.equal a b)
49 | Cons(a,aa) -> HASHINT3(PRIME3,Uid.to_int (H.uid a),Uid.to_int( aa.Node.id))
54 let node x = x.Node.node
55 let hash x = x.Node.key
56 let equal = Node.equal
58 let nil = Node.make Nil
60 (* doing sorted insertion allows to make better use of hash consing *)
61 let rec sorted_cons e l =
62 match l.Node.node with
63 | Nil -> Node.make (Cons(e, l))
66 then Node.make (Cons(e, l))
67 else Node.make (Cons(x, sorted_cons e ll))
72 let cons ?(sorted=true) e l =
73 if sorted then sorted_cons e l else cons e l
75 let hd = function { Node.node = Cons(a,_) } -> a | _ -> failwith "hd"
76 let tl = function { Node.node = Cons(_,a) } -> a | _ -> failwith "tl"
79 let rec loop acc l = match l.Node.node with
81 | Cons (a, aa) -> loop (f a acc) aa
86 let rec loop l = match l.Node.node with
88 | Cons(a, aa) -> cons (f a) (loop aa)
93 let rec loop l = match l.Node.node with
95 | Cons(a,aa) -> (f a);(loop aa)
99 let rev l = fold cons l nil
100 let rev_map f l = fold (fun x acc -> cons (f x) acc) l nil
101 let length l = fold (fun _ c -> c+1) l 0
103 match l.Node.node with
105 | Cons (x, ll) -> x == e || mem e ll