graphs and trees again

[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
changes:

* 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
  performance).

It might be worthwhile to add fold and accumulators.  I was also thinking
of adding unfolds (pure, and monadic depth-first and breadth-first).