graphs and trees again
wolfgang at jeltsch.net
Tue Jan 13 21:36:58 EST 2004
Am Dienstag, 13. Januar 2004 19:12 schrieb Ross Paterson:
> [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.
Well, I did this to be consistent with the Graph module where abstract types
are crucial. Yes, it doesn't make much sense. But declaring Forest via
newtype instead of type surely makes sense because this way you're able to
define a meaningful Functor instance.
> * added upwards and downwards accumulators (except that your "upwards"
> accumulator is actually a variant downwards accumulator, with quadratic
What do you mean with "a variant"? Is foldl a variant foldr?
> 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