generalized IntMap - IntegerMap or IntegralMap

[David Feuer]

There has been some discussion in the past, but it hasn't gone far. A
few points:

1. Integer is a bit tough to deal with. It might make sense to use
some sort of trie for Integer keys.

2. I would very much like to add Data.Int64{Map,Set} and perhaps also
Data.Int32{Map,Set} to containers. Unfortunately, I don't have the
time to consider such a thing at the moment. Jonathan S. has been
working (on and off) on a wholesale replacement for IntMap. Perhaps he
has ideas for this extension as well. IntMap itself could become a
wrapper around one of those two, or could perhaps be implemented
separately (although I doubt it's worth the trouble).

3. I don't think any existing classes really get the point across. To
fit in an IntMap, a type must *actually* satisfy the law that   toEnum
. fromEnum = id. Furthermore, some operations will only make sense if
toEnum is strictly order-preserving. One option would be to add an ad
hoc class for just this purpose:

class SmallKey k where
  -- Laws:
  -- fromInt . toInt = id
  -- If k has an Ord instance, then toInt is strictly order-preserving.
  toInt :: k -> Int
  fromInt :: Int -> k

Of course, if (2) should happen, then we'll need SmallKey32 and
SmallKey64 classes.

On Mon, Jan 22, 2018 at 3:44 AM, Henning Thielemann
<lemming at henning-thielemann.de> wrote:
>
> I want to use Word32 or Word64 bit patterns as indices for a Map. I have
> checked that IntMap is more efficient than Map in my application. However,
> the Haskell 98 report warrants only 30 bits for Int including the sign bit.
> Is there a generalization of IntMap for Map Integer or (Integral k, Bits k)
> => Map k or would there be general interest in such a data structure?
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries