Data.* collections maintenance

Simon Marlow simonmar at
Mon Oct 24 05:43:26 EDT 2005

On 22 October 2005 11:58, Adrian Hey wrote:

> One problem with AVL is the complexity of most of the code means
> producing specialised unboxed implementations manually is not an
> attractive proposition. Hopefully compilers will do this sort of
> thing for us one day.
> But in reality I expect this sort of thing to be more of an issue
> for benchmark style code using Ints. For more complex keys and
> comparisons the indirection cost will be relatively insignificant
> I think. For polymorpic implementations counting the actual number
> of comparisons required by some function is just as important IMO.

It's not just benchmark code - in GHC we use Int-based maps all over the
place for speed.  Given your promising results for polymorphic AVL
trees, it's a fair bet that you could beat Data.IntMap with a
specialised Int version.  If you did, we would be forced to use
Data.Tree.AVL in GHC :)


More information about the Libraries mailing list