graphs and trees again
ross at soi.city.ac.uk
Tue Jan 13 18:12:39 EST 2004
[moving to libraries]
On Tue, Jan 13, 2004 at 05:46:29PM +0100, Wolfgang Jeltsch wrote:
> for my studies I recently needed graph and tree handling code. Because
> nothing I found seemed to satisfy my needs, I finally started writing my own
> graph and tree module. I was especially disappointed with Data.Graph and
> Data.Tree. The reasons are:
> * The Implementation of the types is not hidden so that code using
> Data.Graph and Data.Tree can get very implementation-dependent.
> * Vertices are ints which is too low level in my opintion. I think it
> would be better to allow different types for vertices because this seems
> to closer reflect what applications demand.
> * I'd prefer to be able to use arbitrary sets of vertices instead of only
> continuous ranges.
> * There are only very few functions for trees and forests.
The Data.Tree module in base is certainly quite small. You've made two
* made the types abstract, but provided the equivalent constructor and
destructor functions. I'm not sure that gains anything.
* added upwards and downwards accumulators (except that your "upwards"
accumulator is actually a variant downwards accumulator, with quadratic
It might be worthwhile to add fold and accumulators. I was also thinking
of adding unfolds (pure, and monadic depth-first and breadth-first).
More information about the Libraries