[Haskell-cafe] EnumSet and EnumMap

Yitzchak Gale gale at sefer.org
Sun Feb 25 14:36:38 EST 2007

Chris Kuklewicz wrote:
> There is a performance cost.  Each use of
> Data.List.map in that code is a performance
> cost.  And if toEnum/fromEnum is non-trivial
> there is a performance cost.

Are you sure? I am under the impression that
at least for GHC, toEnum/fromEnum on Int is
free. And every Data.List.map in your code is
mapping one of toEnum, fromEnum, or a newtype
constructor, so those should also be free,
or perhaps could be made free with a pragma.

Expert opinions on this?

On types other than Int, you'll incur a very small
cost. It should still be much better than generic
Map and Set. If the difference between that and
building something by hand for types other than
Int is important, you can still do that, as now.

>> The difference in interface been the Int and non-Int
>> versions of Set and Map forces you to make an
>> early decision about which to use. That decision
>> gets pervasively hard-wired into your code.

> This is true.  The solution for real application is to
> adopt a type class interface to collections, for which
> a few examples exist.

That is a far-reaching change. I hope it happens some

In the meantime, your module are usable now, with
very little change to existing code.

It should certainly be added to the standard
libraries. I personally would then stop using
IntMap/IntSet for new code. If there is any penalty
at all, it will certainly be insignificant to me.
(I am not currently writing any regexp libraries.)

If this is indeed free of performance cost for
most or all compilers, I would then expect the old
Int-specific implementations to disappear
in a few years.


More information about the Libraries mailing list