Data.HashMap: Strict or lazy by default?

[Edward Kmett]

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.
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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110217/0626d222/attachment.htm>