Data.IntMap.Strict.findWithDefault is too strict

[Johan Tibell]

Hi all,

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
example:

# 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)
time.

# 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
write:

    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.

Cheers,
Johan