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.
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