Evan Laforge qdunkan at
Thu Aug 30 21:01:59 CEST 2012

I just fixed a bug in my program that came about because the same
graph constructed in different orders compared inequal.  E.g.:

buildG (0, 2) [(0, 1), (0, 2)] /= buildG (0, 2) [(0, 2), (0, 1)]

It seems to me that these should compare equal.  This was easy for me
to do since I wrap Graph in a newtype, but it's hard to do for Graph
itself, since it's defined as a type synonym over Data.Array.

Do people agree that (==) is incorrect for Data.Graph, or is there a
legitimate difference between the two graphs?  If people agree, what
can be done to fix Data.Graph?  Should be add Data.Graph2 that is
defined as a real type and start anew from there?

In general, it seems to me Data.Graph is very basic and has not
received any love for a long time.  It's a thin wrapper over
Data.Array, which is one of the more error-prone ornery APIs out
there.  To use it I wound up writing lots of little utility functions
to do things like add or remove edges which were fiddly and error
prone.  I just noticed a package graph-wrapper, with the description
"A wrapper around the standard Data.Graph with a less awkward
interface", so I guess I'm not the only person to have felt that way.

Wouldn't it be nice to start taking steps toward having a graph
library in the stdlib that people actually like?

More information about the Libraries mailing list