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 : 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 *)
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, cons e ll))
69 let hd = function { Node.node = Cons(a,_) } -> a | _ -> failwith "hd"
70 let tl = function { Node.node = Cons(_,a) } -> a | _ -> failwith "tl"
73 let rec loop acc l = match l.Node.node with
75 | Cons (a, aa) -> loop (f a acc) aa
80 let rec loop l = match l.Node.node with
82 | Cons(a, aa) -> cons (f a) (loop aa)
87 let rec loop l = match l.Node.node with
89 | Cons(a,aa) -> (f a);(loop aa)
93 let rev l = fold cons l nil
94 let rev_map f l = fold (fun x acc -> cons (f x) acc) l nil
95 let length l = fold (fun _ c -> c+1) l 0
97 match l.Node.node with
99 | Cons (x, ll) -> x == e || mem e ll