[Haskell-cafe] Re: Graph library, was: Haskell.org GSoC

[Tracy Wadleigh]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090212/25205331/attachment.htm