Data.* collections maintenance

[Sebastian Sylvan]

On 10/24/05, Simon Marlow <simonmar at microsoft.com> wrote:
> 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.

Uh, isn't there already a DiffUArray?

type DiffUArray = IOToDiffArray IOUArray

It would be interesting to benchmark this against the various maps.
Some code isn't too heavy on insertions so a regular Array would work
fine there. Or if it contains primitive types, unboxed arrays works as
well.
At any rate there probably should be an immutable HashMap
implementation (parameterized over the array-type).

/S
--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862