2011/3/30 Daniel Fischer <daniel.is.fischer@googlemail.com>

On Wednesday 30 March 2011 20:47:37, Wolfgang Jeltsch wrote:
> Can’t Integer be implemented in a more efficient way that it’s done
> currently?

Theoretically, sure. Practically, everything above a minor speedup would be
very hard, I think.
And, as Johan mentioned, Integers can't be unpacked, I don't see how that
could be achieved, so for IntMap and the like, performance would be
drastically worse even if Integer manipulation itself got significantly
faster.

I'm not sure, if an IntegerMap would be that much slower for Int-sized Integers. An optimized variant of the following trie-like data structure

data IntegerMap v = IntegerMap (IntMap v) (M.Map Integer v) -- better: also use a trie-based impl. for M.Map Integer v

should do the trick with a small constant overhead for Int-sized Integers.

-Simon