NB I believe that it is possible to make a lazy-valued Map (IntMap,
HashMap, etc...) from a strict one via:

data Lazy a = Lazy a

newtype LazyMap k v = StrictMap k (Lazy v)

So in principle (and I believe this is only useful for key-strict
structures) the strict map is more "universal". A separate lazy
implementation mostly saves us a layer of indirection.

A reasonable point, but it seems to me you don't save a layer of indirection. Regardless of if the underlying map is lazy or strict it still has the same indirection to its elements: Node -> value, and here it becomes Node -> Lazy -> value, and since you can't unbox polymorphically, your argument actually cuts the other way, by adding a layer for the lazy user. To elide the layer of indirection and unpack the value into the node constructor you'd need an 'adaptive-containers' or 'unboxed-containers' -style strict map.

What you do gain with your approach is potentially the ability to elide an indirect jump or two due to the known strictness of the case scrutinee, but I have no idea if the magnitude of that effect would warrant increasing the memory footprint for lazy users, given that the other benefits of a strict-by-default map in terms of avoiding space leaks, etc. can all be had by supplying a second set of combinators.

-Edward

-Jan-Willem Maessen