How do you represent a graph in Haskell?

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?

Solution 1:

In shang's answer you can see how to represent a graph using laziness. The problem with these representations is that they are very difficult to change. The knot-tying trick is useful only if you're going to build a graph once, and afterward it never changes.

In practice, should I actually want to do something with my graph, I use the more pedestrian representations:

• Edge list
• Adjacency list
• Give a unique label to each node, use the label instead of a pointer, and keep a finite map from labels to nodes

If you're going to be changing or editing the graph frequently, I recommend using a representation based on Huet's zipper. This is the representation used internally in GHC for control-flow graphs. You can read about it here:

• An Applicative Control-Flow Graph based on Huet's Zipper

• Hoopl: A Modular, Reusable Library for Dataflow Analysis and Transformation

Solution 2:

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.

Solution 3:

As Ben mentioned, cyclic data in Haskell is constructed by a mechanism called "tying the knot". In practice, it means that we write mutually recursive declarations using let or where clauses, which works because the mutually recursive parts are lazily evaluated.

Here's an example graph type:

import Data.Maybe (fromJust)

data Node a = Node
    { label    :: a
    , adjacent :: [Node a]
    }

data Graph a = Graph [Node a]

As you can see, we use actual Node references instead of indirection. Here's how to implement a function that constructs the graph from a list of label associations.

mkGraph :: Eq a => [(a, [a])] -> Graph a
mkGraph links = Graph $ map snd nodeLookupList where

    mkNode (lbl, adj) = (lbl, Node lbl $ map lookupNode adj)

    nodeLookupList = map mkNode links

    lookupNode lbl = fromJust $ lookup lbl nodeLookupList

We take in a list of (nodeLabel, [adjacentLabel]) pairs and construct the actual Node values via an intermediate lookup-list (which does the actual knot-tying). The trick is that nodeLookupList (which has the type [(a, Node a)]) is constructed using mkNode, which in turn refers back to the nodeLookupList to find the adjacent nodes.

Solution 4:

It's true, graphs are not algebraic. To deal with this problem, you have a couple of options:

1. Instead of graphs, consider infinite trees. Represent cycles in the graph as their infinite unfoldings. In some cases, you may use the trick known as "tying the knot" (explained well in some of the other answers here) to even represent these infinite trees in finite space by creating a cycle in the heap; however, you will not be able to observe or detect these cycles from within Haskell, which makes a variety of graph operations difficult or impossible.
2. There are a variety of graph algebras available in the literature. The one that comes to mind first is the collection of graph constructors described in section two of Bidirectionalizing Graph Transformations. The usual property guaranteed by these algebras is that any graph can be represented algebraically; however, critically, many graphs will not have a canonical representation. So checking equality structurally isn't enough; doing it correctly boils down to finding graph isomorphism -- known to be something of a hard problem.
3. Give up on algebraic datatypes; explicitly represent node identity by giving them each unique values (say, Ints) and referring to them indirectly rather than algebraically. This can be made significantly more convenient by making the type abstract and providing an interface that juggles the indirection for you. This is the approach taken by, e.g., fgl and other practical graph libraries on Hackage.
4. Come up with a brand new approach that fits your use case exactly. This is a very difficult thing to do. =)

So there are pros and cons to each of the above choices. Pick the one that seems best for you.