Benedikt writes:
I think a good general purpose graph library is tricky though:
- There are lot of variants of graphs (trees, bipartite, acyclic, undirected, simple, edge labeled etc.), hard to find adequate and easy to use abstraction.
- There is no single 'best' implementation (mutable vs. unmutable etc.).
- Its hard to find good traversal and zipper abstractions, though fgl has some nice ones.
- The complexity of algorithms varies greatly depending on the particular kind of graph.
Anyway, that's why it is challenging and interesting.

Hear, hear!

From what I can tell, fgl is the closest thing I've seen to a usable remotely-general-purpose graph library in any language. With all apologies to Siek, et al., the boost graph library is exceedingly complex, to the point of being unusable (one man's opinion) to all but the most ardent lovers of C++ template metaprogramming. That's no knock on its designers, it's just that the graph problem provides an exceptionally challenging tension between managing complexity and providing acceptable performance--on top of trying to achieve respectable generality.

It seems to me that anyone who aspires to author a Haskell graph library that can be regarded as canonical really ought to first know fgl inside and out, and probably ought to consider extending that library, vs. starting from scratch.

In fact, it was my current work with non-trivial graph problems that ultimately led me to justify switching to using Haskell for my day job a couple of months ago (after having investigated and abandoned other possible solutions in other languages that would have been a much easier sell to my higher-ups). So I have a pressing professional interest on hearing others weigh in on this topic, and particularly on the benefits/shortcomings of fgl.

I'd especially like to hear from Martin Erwig on this topic. Martin? You listening?

--Tracy