Heirarchical name space allocation /Trees

[Ross Paterson]

On Wed, Mar 31, 2004 at 04:42:29PM +0200, Christian Maeder wrote:
> Ross Paterson wrote:
> >I'd like to suggest (again) treating sequences differently from the rest,
> >and that they should be defined by a class:
> >* the class fits within Haskell 98, because sequences have only one
> >  parameter, and it's unconstrained.
> >* polymorphism is likely to be more useful with sequences because of
> >  the wide range of implementations suited to different purposes.
> >* polymorphism lets you do general adaptors, like Edison's SizedSeq
> >  (adding a size) and RevSeq (presenting a reversed view).
> 
> I admit, that supplying further modules for SizedSeq and RevSeq would 
> involve some code duplication. (If several implementations of sequences 
> are used simultaneously qualification is required.)

Just defining a standard set of operations (filter, dropWhile, etc, etc)
will involve lots of duplication.  Most of these will involve converting
to lists, doing the list thing and converting back.  But in a class you
supply a default definition.

> But maybe you could elaborate the advantages of a class that you suggest 
> in more detail. For generic algorithms with sequences, I would suspect 
> smaller classes, e.g. like Monoid, to be more appropriate.

All the usual advantages of abstraction.
I thought SizedSeq was pretty compelling:

	data Sized s a = N !Int (s a)
	instance Sequence s => Sequence (Sized s) where ...

One instance gets you N new sequences.

Monoid isn't quite enough (no way to add elements, for one thing).

> where can I download the actual code of edison?
> http://www.haskell.org/ghc/docs/edison/

The original is in the fptools CVS repository at hslibs/data/edison
and also in a GHC source tarball.  There's a slightly changed version at
	:pserver:anonymous at cvs.hfl.sourceforge.net:/cvsroot/hfl