Discussion: Strict maps

[David Feuer]

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/ce864265/attachment-0001.html>