参照的な構造（動的に変更される有向グラフ）を表すにはどうしたらいい？

グラフの形状は、環状構造とか、分断されてるとか、そういうのもあって仮定できないとして

addNode :: a -> Graph a -> (Graph a, Node a)
deleteNode :: Node a -> Graph a -> Graph a
getValue :: Node a -> Graph a -> a
putValue :: Node a -> a -> Graph a -> Graph a
connect :: Node a -> Node a -> Graph a -> Graph a
disconnect :: Node a -> Node a -> Graph a -> Graph a
connections :: Node a -> Graph a -> [Node a]

こういう関数を純粋に定義するにはどうしたらいい？
特に、ノードやエッジ、グラフを表す型はどういうものにすべき？
「純粋に」というのは、関数の引数や返り値にIOやSTの類が現れないということ unsafePerformIO みたいな「抜け穴」の使用はナシで