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
31 val with_id : Uid.t -> t
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
59 let cons a b = Node.make (Cons(a,b))
60 let hd = function { Node.node = Cons(a,_) } -> a | _ -> failwith "hd"
61 let tl = function { Node.node = Cons(_,a) } -> a | _ -> failwith "tl"
64 let rec loop acc l = match l.Node.node with
66 | Cons(a,aa) -> loop (f a acc) aa
71 let rec loop l = match l.Node.node with
73 | Cons(a,aa) -> cons (f a) (loop aa)
78 let rec loop l = match l.Node.node with
80 | Cons(a,aa) -> (f a);(loop aa)
84 let rev l = fold cons l nil
85 let rev_map f l = fold (fun x acc -> cons (f x) acc) l nil
86 let length l = fold (fun _ c -> c+1) l 0
89 let with_id = Node.with_id