Data.HashMap: Strict or lazy by default?

[Edward Kmett]

On Thu, Feb 17, 2011 at 8:15 PM, Ivan Lazar Miljenovic <
ivan.miljenovic at gmail.com> wrote:

> On 18 February 2011 11:51, Johan Tibell <johan.tibell at gmail.com> wrote:
> >
> > Option 1:
> > Data.HashMap (strict)
> > Data.HashMap.Lazy
>
> This would probably work the best, especially as it's the behaviour
> already taken by ByteString, Text, etc.


However, it is quite different than the behavior of Data.Map, which is a
much closer analogue. Bytestring and Text's strict and lazy versions are
radically different structures from one another. Here the miniscule
differences between strict and lazy WriterT, StateT, etc. is probably a much
closer analogue. There they use the separate data types to reflect the fact
that you have different operations that you want classes to provide (like
the strict map in the above discussion).

Here I'd probably look more towards the mtl and transformers as a guideline,
as it has been balancing tensions between the two world views with regards
to maximizing laziness for a long time. That would steer towards Option 3,
likely with being lazy in the value being the default exported from
Data.HashMap.

But even that analogy is flawed, because there the only difference is the
use of a few irrefutable patterns to avoid a couple of bottoms where
possible. Here the difference in strictness is much more dramatic as it
causes you to fail even the *Functor* laws and I for one would really like
to see these be Foldable/Traversable, etc.

Making the map strict in the value (at least for map, traverse, mapM) is
pretty ugly because it changes the set of things that it can contain by
making it an error to try to stuff an error, undefined, or potentially
bottom value into the map.

Making the map strict in its internal structure never introduces
non-termination into your code, and is almost always a win because of the
decreased amount of indirect jumps made by the STG. Making the map strict in
the values shrinks the size of the range of the map unnaturally, and makes
it veer radically from the model of a function from k -> Maybe v.

-Edward Kmett
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110217/f90b4c92/attachment.htm>