Libraries Digest, Vol 93, Issue 21

[Edward Kmett]

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.

On the other hand, a case where it would seem to make sense to have a
version with two types would be were you make two versions, split on whether
or not they are both spine-strict or not, rather than if they are
value-strict. In that case, both are valid instances of Functor, Foldable,
Traversable, but the spine-lazy version will tend to be pretty slow due to
the fact that most of its functions will have to keep dispatching via
indirect jumps as they traverse down the spine.

-Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110530/a517d95e/attachment.htm>