Libraries Digest, Vol 93, Issue 21

[John Lato]

On Tue, May 31, 2011 at 2:08 AM, Edward Kmett <ekmett at gmail.com> wrote:

> On Mon, May 23, 2011 at 5:13 AM, John Lato <jwlato at gmail.com> wrote:
>
>>
>>> Message: 3
>>> Date: Sun, 22 May 2011 06:52:49 -0400
>>> From: "Edward Z. Yang" <ezyang at MIT.EDU>
>>> Subject: Re: Proposal: Value strict versions of containers
>>> To: Milan Straka <fox at ucw.cz>
>>> Cc: libraries <libraries at haskell.org>
>>> Message-ID: <1306061483-sup-1713 at ezyang>
>>> Content-Type: text/plain; charset=UTF-8
>>>
>>> Excerpts from Milan Straka's message of Sun May 22 06:50:07 -0400 2011:
>>> > - the types Data.IntMap.IntMap, Data.IntMap.Lazy.IntMap and
>>> >   Data.IntMap.Strict.IntMap should be equal -- so I can use strict
>>> >   methods on IntMap someone else created with lazy methods. That is
>>> >   simple in absence of type classes.
>>>
>>> Comment: This would mean you would get no static assurances against
>>> mixing up a strict IntMap with a lazy IntMap; for all intents and
>>> purposes,
>>> this is equivalent to implementing strict versions of all functions on
>>> top
>>> of a lazy data type.
>>>
>>
>> Another consequence to this design is that, should someone want to have
>>
>> > class MapC m key value | m -> key, m -> value where
>>
>> it becomes impossible to directly write
>>
>> > instance MapC (Data.IntMap.Strict.IntMap Int a) Int a where
>> >
>> > instance MapC (Data.IntMap.Lazy.IntMap Int a) Int a where
>>
>> because the two instances are the same.
>>
>> Regardless, +1 for Milan's proposal either with one type or separate types
>> for strict and lazy.
>>
>
> I'm perfectly fine with adding a separate module that exports the strict
> versions of the functions.
>
> The main problem with the separate versions is that a strict value
> container is a valid instance of almost no interesting classes.
>
> It violates the Functor laws, the Foldable laws, and Traversable laws,
> because of its treatment of bottoms. I would be +1 for the single type
> version, but I would have serious misgivings about a version with two types
> as the temptation to add those bogus instances would be strong.
>

Programmers using strict containers need to make their own proofs for bottom
anyway, so I don't see it as particularly onerous to do so for these
instances provided that they're correct for non-bottom values and that it's
documented.  With a strict container, I'd rather have a Functor that doesn't
handle bottoms properly than no Functor at all.

And with a single Map with strict and lazy interfaces, then wouldn't there
properly be no strict Functor at all?  If the base map is strict, then the
Functor instance would have to go through boxed values to handle bottom
properly.  If the base map is lazy, the Functor instance would be lazy too,
which would negate the benefits of a strict interface.  Is this correct?

John Lato
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110531/6391b1c8/attachment.htm>