Skip to content

Instantly share code, notes, and snippets.

@rgrinberg
Created June 7, 2013 16:08
Show Gist options
  • Save rgrinberg/5730407 to your computer and use it in GitHub Desktop.
Save rgrinberg/5730407 to your computer and use it in GitHub Desktop.
Bag vs Hash_set when used as a hashtable key. bag acts strange?
open Core.Std
module type Collection = sig
type 'a t
val create : unit -> 'a t
val add : 'a t -> 'a -> unit
val of_list : 'a list -> 'a t
val iter : 'a t -> f:('a -> unit) -> unit
end
module G (S : Collection) = struct
type graph = Node of (int * (graph S.t))
let nodes (Node (_, b)) = b
let value (Node (x, _)) = x
let copy_graph graph =
let q = Queue.create () in
let copied = Hashtbl.Poly.create () in
let new_graph = Node (value graph, S.create ()) in
Hashtbl.add_exn copied ~key:graph ~data:new_graph;
Queue.enqueue q graph;
let rec copy () =
match Queue.dequeue q with
| None -> ()
| Some (Node (label, neighbours) as node) ->
neighbours |> S.iter ~f:(fun n ->
match Hashtbl.find copied n with
| None ->
let new_node = Node (value n, S.create()) in
(* Hashtbl.find_exn fails here when S = Bag *)
S.add (nodes (Hashtbl.find_exn copied node)) new_node |> ignore;
Hashtbl.add_exn copied ~key:n ~data:new_node;
Queue.enqueue q n
| Some x ->
S.add (nodes (Hashtbl.find_exn copied node)) x |> ignore
); copy ()
in copy (); new_graph
let alone x = Node (x, S.create ())
let test () =
let gg =
Node (12, S.of_list [
Node (1, S.of_list [ alone 4; alone 2 ]);
Node (11, S.of_list [ ]);
alone 25; ]) in
copy_graph gg |> ignore
end
module HashSetG = G(struct
type 'a t = 'a Hash_set.Poly.t
let create () = Hash_set.Poly.create ()
let add b e = Hash_set.add b e
let of_list l = Hash_set.Poly.of_list l
let iter = Hash_set.iter
end)
module BagG = G(struct
type 'a t = 'a Bag.t
let create = Bag.create
let add b e = Bag.add b e |> ignore
let of_list = Bag.of_list
let iter = Bag.iter
end)
let () =
print_endline "testing hash";
HashSetG.test ();
print_endline "testing bag";
BagG.test () (* raises Not_found *)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment