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
32 module Make ( H : Hcons.SA ) : S with type elt = H.t =
35 type 'a node = Nil | Cons of elt * 'a
36 module rec Node : Hcons.S with type data = Data.t = Hcons.Make (Data)
37 and Data : Hashtbl.HashedType with type t = Node.t node =
42 | _,_ when x==y -> true
43 | Cons (a,aa), Cons(b,bb) -> (aa==bb) && (H.equal a b)
47 | Cons(a,aa) -> HASHINT3(PRIME3,H.uid a, aa.Node.id)
52 let node x = x.Node.node
53 let hash x = x.Node.key
54 let equal = Node.equal
56 let nil = Node.make Nil
57 let cons a b = Node.make (Cons(a,b))
58 let hd = function { Node.node = Cons(a,_) } -> a | _ -> failwith "hd"
59 let tl = function { Node.node = Cons(_,a) } -> a | _ -> failwith "tl"
62 let rec loop acc l = match l.Node.node with
64 | Cons(a,aa) -> loop (f a acc) aa
69 let rec loop l = match l.Node.node with
71 | Cons(a,aa) -> cons (f a) (loop aa)
76 let rec loop l = match l.Node.node with
78 | Cons(a,aa) -> (f a);(loop aa)
82 let rev l = fold cons l nil
83 let rev_map f l = fold (fun x acc -> cons (f x) acc) l nil
84 let length l = fold (fun _ c -> c+1) l 0