This is maybe just me but I find any kind of self referenced data structure a bit awkward to define in haskell. The thing mentioned in http://wiki.haskell.org/Tying_the_Knot .
I generally express graphs as a `Map k (Set k)` or similar, with extra data as desired. Using keys and lookups means you don't need self-references. I guess in a way this approach sacrifices some purity, but I find it works very well.