The best representation for a graph depends a little on the use case. The Graph
type in containers uses an adjacency list and a few basic graph operations are provided.
One unique Haskell library, fgl
, for Functional Graph Library, takes a different approach to programming with graphs, by considering graph as an inductive data-type.
One of the core ideas in fgl
is contexts and decomposition. A context of a graph node is a triplet of the node's predecessors, successors, and the node itself. All graph manipulations can be expressed as inductive recursions over the contexts of a graph. Furthermore, it's surprisingly efficient.
For reference, here's a very, very small section of the fgl API:
-- module Data.Graph.Inductive.Graph type Adj b = [(b, Node)] type Context a b = (Adj b, Node, a, Adj b) type Decomp g a b = (Mcontext a b, g a b) empty :: Graph gr => gr a b match :: Graph gr => Node → gr a b → Decomp gr a b (&) :: DynGraph gr => Context a...