On Mon, May 23, 2011 at 5:13 AM, John Lato <jwlato@gmail.com> wrote:

Message: 3
Date: Sun, 22 May 2011 06:52:49 -0400
From: "Edward Z. Yang" <ezyang@MIT.EDU>
Subject: Re: Proposal: Value strict versions of containers
To: Milan Straka <fox@ucw.cz>
Cc: libraries <libraries@haskell.org>
Message-ID: <1306061483-sup-1713@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