Discussion: Strict maps

[Edward Kmett]

There also is the minor technical point that when 'properly strict' in the
element you can't actually pass the laws for Functor and Traversable.

Mind you, I'm not terribly consistent on that point, as linear actually
works strict in the elements right now, after I yielded to persistent user
pressure. So I am very much being a hypocrite here. ;)

I personally have no problem with the status quo, and have a lot of code
that would break with a naive change for whatever that is worth.

-Edward

On Mon, Nov 24, 2014 at 12:36 PM, Milan Straka <fox at ucw.cz> wrote:

> Hi all,
>
> here is the discussion that initiated the Lazy and Strict versions:
> https://www.haskell.org/pipermail/libraries/2011-May/016362.html
>
> What follows is only my own interpretation of the discussion, please
> feel to reed it by yourselves. There were few people discussing, but
> I feel that avoiding the distinction on a type level was quite
> supported. I advocated the idea that strictness is not a property of the
> map itself, but a property of how you work with the map. The flexibility
> of one data type at the expense of some static checking was mentioned.
>
> Note that if strictness is encoded on the type level, it is part of an
> API -- for example, a JSON parser might advertise that it returns the
> results in a "strict" map and cannot change this (as I see an internal
> implementation issue) without changing the API.
>
> One of the biggest downsides of Data.Map.Lazy and Data.Map.Strict is
> that they have one set of instances. That is a general issue of Haskell
> class system -- when you sort a list of Ints, it is complicated to use
> other that default 'Ord' instance. You can have a newtype with other
> 'Ord' instance, and you have to coerce the list of Ints to be a list of
> OtherInts, and then back to list of Ints after sorting. As the list of
> OtherInts cannot be passed directly to a method consuming a list of
> Ints, it usually has to be converted back immediately. (However, in this
> case the OtherInt may inherit the Num instance, so it can be passed to
> a method requiring a list of Num; but it would not be the case if we
> started with a list of Strings.)
>
> We probably need newtypes for strict Map and strict IntMap, so that we
> have instances like Traversable for strict containers. I am nevertheless
> not sure that methods like Data.Map.Strict.insert should use them.
> Personally, instead of saying ``this map is a strict one'' I like to say
> ``I want a strict instance of this map'', even though it is a bit clumsy
> with Haskell syntax.
>
> Cheers,
> Milan Straka
>
> > -----Original message-----
> > From: David Feuer <david.feuer at gmail.com>
> > Sent: 24 Nov 2014, 11:42
> >
> > 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.
>
> > _______________________________________________
> > Libraries mailing list
> > Libraries at haskell.org
> > http://www.haskell.org/mailman/listinfo/libraries
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141124/367e4a42/attachment.html>