AVL trees for Data.Map and Data.Set

David Menendez zednenem at psualum.com
Fri Mar 3 01:44:21 EST 2006

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!"

More information about the Libraries mailing list