Data.* collections maintenance

[Simon Marlow]

On 24 October 2005 11:17, Sebastian Sylvan wrote:

> On 10/24/05, Simon Marlow <simonmar at microsoft.com> wrote:
>> 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 :)
> 
> Wouldn't an Array (or DiffArray) based HashMap be even better?

DiffArray as it stands isn't very efficient.  It's an interesting idea,
though.  We should really have a DiffUArray, for one thing.

Cheers,
	Simon