Discussion: Strict maps

[David Feuer]

The containers package has Data.Map.Strict and Data.IntMap.Strict, offering
functions for handling maps that are strict in the values stored. But these
modules are lies, as comments in the source explain:

-- API of this module is strict in the keys, but lazy in the values.
-- If you need value-strict maps, use "Data.Map.Strict" instead.
-- The 'Map' type itself is shared between the lazy and strict modules,
-- meaning that the same 'Map' value can be passed to functions in
-- both modules (although that is rarely needed).

-- Be aware that the 'Functor', 'Traversable' and 'Data' instances
-- are the same as for the "Data.Map.Lazy" module, so if they are used
-- on strict maps, the resulting maps will be lazy.

Yuck. This is not nice. Clearly, the current interfaces need to stay around
for compatibility, but I think we should add some unbroken ones too. There
are two and a half sane ways to do this:

1. Make strict types that just wrap the lazy ones in newtype wrappers. The
benefits: a) They can reuse all the code from Data.Map.Strict or
Data.IntMap.Strict, producing tiny little wrapper modules. b) They can
support cheap strictToLazy and unsafeLazyToStrict operations (newtype
unwrappers/wrappers). c) They support lazyToStrict operations with no
significant new code (reusing the NFData code).

2. Make entirely separate strict types. The benefits: a) The code
implementing them does not have to be careful to force everything as it
goes in, so the strictness is maintained automatically; changes to the code
don't need careful strictness auditing. b) Values only need to be forced on
insertion, and GHC should be able to recognize that returned values will
have been forced. This should speed things up when lookups are common and
updates are rare. c) There may (I'm not sure) be more opportunities for GHC
to unbox values when their types are known.

2.5. Do both of the above.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141124/71f68524/attachment.html>