Discussion: Strict maps

[David Feuer]

Well, I guess you can see it as a minor technical point in the sense that
fmap f . fmap g <= fmap (f . g), and that's good enough for many purposes.
On Nov 24, 2014 1:02 PM, "David Feuer" <david.feuer at gmail.com> wrote:

> Ah, that is not a minor technical point; it's a very good point. The
> solution is simple: don't make the strict versions Functor or Traversable
> instances at all. Then there won't be any confusion! They can have
> strictMap and strictTraverse functions instead.
> On Nov 24, 2014 12:57 PM, "Edward Kmett" <ekmett at gmail.com> wrote:
>
>> 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/901d43b4/attachment.html>