Data.HashMap: Strict or lazy by default?

[Jan-Willem Maessen]

On Thu, Feb 17, 2011 at 10:46 PM, Edward Kmett <ekmett at gmail.com> wrote:
> On Thu, Feb 17, 2011 at 10:06 PM, Jan-Willem Maessen <jmaessen at alum.mit.edu>
> 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