Data.IntMap.Strict.findWithDefault is too strict
johan.tibell at gmail.com
Sun Dec 16 10:10:09 CET 2012
I thought I'd share some of the subtle nuances in designing the
strictness properties of the containers API. I currently feel that we
lack a good guiding principle in making this decisions. There are
several different points along the lazy-to-strict spectrum. For
# Everything lazy (including the spine)
We don't use this. I think it's a bad idea. It can make an insert
finish in O(1) just to have a subsequent null check take O(n*log n)
# Spine strict
Quite inefficient as keys aren't unboxed in e.g. lookup and insert.
# Strict in keys inserted into the map
Also ineffecient as keys still can't be unboxed as there's usually a
base case in each loop where the key isn't used.
# Strict in key arguments
This is what that Lazy API uses. Makes it possible to unbox keys. Good
trade-off between performance and expressibility. Means that you can't
lookup undefined empty
which "Strict in keys inserted into the map" would have let you write.
# Strict in values inserted into the map
Minimum required to avoid space leaks for e.g. a map of Int values
that are modified in a loop.
# Strict in value arguments
This is what the Strict API uses. This allows you to not do any
external forcing of values passed to the containers API if you want to
make sure they are evaluated.
More information about the Libraries