Re: Libraries Digest, Vol 93, Issue 21

31 May 2011

      On Tue, May 31, 2011 at 2:08 AM, Edward Kmett  wrote:
...
On Mon, May 23, 2011 at 5:13 AM, John Lato  wrote:
...
...
Message: 3
Date: Sun, 22 May 2011 06:52:49 -0400
From: "Edward Z. Yang" 
Subject: Re: Proposal: Value strict versions of containers
To: Milan Straka 
Cc: libraries 
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