(Forgot to send to haskell-cafe- sorry Alistair!) Martin Erwig wrote a paper [1] that defines an inductive graph type and implements some common algorithms with it. Also, it isn't very Haskellish but if you can label your nodes with an instance of Ix you might be able to use an Array to get constant time access. I've never used Data.HashTable before, but that might also be useful. [1] - http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf<http://web.engr.oregonstate.edu/%7Eerwig/papers/InductiveGraphs_JFP01.pdf>