AVL trees for Data.Map and Data.Set

[David Menendez]

John Meacham writes:

> On Thu, Mar 02, 2006 at 09:13:11PM +0000, Adrian Hey wrote:
> > I think what we should be aiming for in the long term is
> > automatically derived Generalised Tries (as discussed
> > recently).
> 
> Would it be possible to mock up an implementation of this using
> Data.Generics by chance? so we can use a generalized tree for anything
> in Data and Ord? I find the idea of a derived generalized trie quite
> intriguing. would associated types be the best way to express such a
> thing (so you can use 'Trie a' everywhere as a type rather than some
> complicated class predicate).

A while back, I put together an implementation of generic tries based on
Ralf Hinze's "Generics for the Masses". This particular technique allows
you to write M functions for N types with M+N instances, instead of M*N.

It's now on-line at <http://www.eyrie.org/~zednenem/2006/gentrie/>. It's
a darcs repository, so "darcs get" will work. There are two versions
(corresponding to associated type synonyms and associated data types),
plus an alternate interface that hides the map's type.

-- 
David Menendez <zednenem at psualum.com> | "In this house, we obey the laws
<http://www.eyrie.org/~zednenem>      |        of thermodynamics!"