I think we need a strictness audit

[treeowl]

The invariant I'd like to maintain is that any value in a structure produced by an exposed function in Data.{Map,IntMap}.Strict that was not present in a map passed to that function should be in WHNF. I'd also like to consider "really strict" versions of these types, presumably in separate modules. If we can make them perform well, these could be genuine strict datatypes. If not, we can use newtype to hide away the inner laziness.

[meooow25]

The invariant I'd like to maintain is that any value in a structure produced by an exposed function in Data.{Map,IntMap}.Strict that was not present in a map passed to that function should be in WHNF.

This was done in #1019. Well, not exactly—the tests checks that any attempt to insert a bottom value results in a bottom map, which is equivalent and easier to test.

I'd also like to consider "really strict" versions of these types, presumably in separate modules. If we can make them perform well, these could be genuine strict datatypes. If not, we can use newtype to hide away the inner laziness.

I suppose we could do this if we put an NFData a => and force the values. But I don't know if users want this enough to make maintaining another copy of the API worth it.

[treeowl]

What I meant had nothing to do with NFData. I just meant entirely strict constructors, but honestly that doesn't seem worth the trouble. We can probably close this ticket if you don't think we have any remaining accidental laziness. The newtype wrapper idea might deserve its own ticket though. People often like to imagine that there's such a thing as a "strict map" that holds all its values in WHNF, but we don't actually have such a thing; it's always possible to accidentally use a function from Data.Map.Lazy to introduce a thunk, or, more subtly, to do so using the Functor or Traversable instances, or similar things from indexed-traversable or lens. The newtype wrapper would act as a barrier to such things. The controversial bit would be figuring out whether to have strict fmap (which is useful but isn't strictly law abiding) or whether to omit the Functor instance.

[meooow25]

Oh I see what you mean.

I definitely agree that a newtype would have been a good idea to avoid this pitfall. And it would still allow the user to explicitly change from strict to lazy in constant time (or vice versa unsafely) if they want.

I expect this will break a lot of stuff if we were to try this today. I don't know if that's worth it.

[treeowl]

Adding modules to use such a newtype wouldn't break anything.

[meooow25]

So we add, say, Data.Map.NewStrict and also keep around Data.Map.Strict? That might be confusing...

[treeowl]

Not by that name, certainly!

[TeofilC]

FWIW I would be very happy if we introduced a guaranteed strict newtype. Accidentally using functions from .Lazy and the lazy instances are such footguns.

It would be interesting to know how much code would actually break if we just changed the meaning of the current modules.

[meooow25]

I've created #1124, we can continue the discussion there.