Re: Data.HashMap: Strict or lazy by default?

On Thu, Feb 17, 2011 at 10:46 PM, Edward Kmett wrote:

On Thu, Feb 17, 2011 at 10:06 PM, Jan-Willem Maessen wrote:

...

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.

Er, I think we're violently agreeing here, which probably means I didn't state myself clearly enough. You want a specialized type rather than just a StrictMap k (Lazy v) because the latter introduces a layer of indirection at every leaf. But it does suggest how to quickly get a *working* pair of strict & lazy maps: build the best possible strict map, *then* specialize. -Jan