It's easy enough to represent a tree or list in haskell using algebraic data types. But how would you go about typographically representing a graph? It seems that you need to have pointers. I'm guessing you could have something like
type Nodetag = String
type Neighbours = [Nodetag]
data Node a = Node a Nodetag Neighbours
And that would be workable. However it feels a bit decoupled; The links between different nodes in the structure don't really "feel" as solid as the links between the current previous and next elements in a list, or the parents and children of a node in a tree. I have a hunch that doing algebraic manipulations on the graph as I defined it would be somewhat hindered by the level of indirection introduced through the tag system.
It is primarily this feeling of doubt and perception of inelegance that causes me to ask this question. Is there a better/more mathematically elegant way of defining graphs in Haskell? Or have I stumbled upon something inherently hard/fundamental? Recursive data structures are sweet, but this seems to be something else. A self referential data structure in a different sense to how trees and lists are self referential. It's like lists and trees are self referential at the type level, but graphs are self referential at the value level.
So what's really going on?
I also find it awkward to try to represent data structures with cycles in a pure language. It's the cycles that are really the problem; because values can be shared any ADT that can contain a member of the type (including lists and trees) is really a DAG (Directed Acyclic Graph). The fundamental issue is that if you have values A and B, with A containing B and B containing A, then neither can be created before the other exists. Because Haskell is lazy you can use a trick known as Tying the Knot to get around this, but that makes my brain hurt (because I haven't done much of it yet). I've done more of my substantial programming in Mercury than Haskell so far, and Mercury is strict so knot-tying doesn't help.
Usually when I've run into this before I've just resorted to additional indirection, as you're suggesting; often by using a map from ids to the actual elements, and having elements contain references to the ids instead of to other elements. The main thing I didn't like about doing that (aside from the obvious inefficiency) is that it felt more fragile, introducing the possible errors of looking up an id that doesn't exist or trying to assign the same id to more than one element. You can write code so that these errors won't occur, of course, and even hide it behind abstractions so that the only places where such errors could occur are bounded. But it's still one more thing to get wrong.
However, a quick google for "Haskell graph" led me to http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling, which looks like a worthwhile read.