Libraries Digest, Vol 93, Issue 21

[Edward Kmett]

On Tue, May 31, 2011 at 6:03 AM, John Lato <jwlato at gmail.com> wrote:

> On Tue, May 31, 2011 at 2:08 AM, Edward Kmett <ekmett at gmail.com> wrote:
>
>> 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.
>>
>
>
With a strict container, I'd rather have a Functor that doesn't handle
> bottoms properly than no Functor at all.
>

This is where our fundamental disagreement lies. I find such an instance
abhorrent, because now I am forced to second guess whether or not I have a
real Functor instance everywhere. Your local strictness consideration
infects all the third party code that just needed functoriality.

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

I would argue that the Functor instance would have to be the non-strict
version, because the other violates the laws. This is why I advocated in
favor of the single-data-type two-module approach.

I don't really like polymorphic value-strict containers because their
benefits are very fragile. You lose the benefit if you store tuples in them
or any other composite data type else that risks capturing a closure.  This
is why I advocated for a single data type with two modules, as is used by
Data.HashMap. In general, I find that putting a ! annotation on a
polymorphic type is a bad idea. It doesn't ensure that it is fully
evaluated, merely that it is in whnf. The reason I don't object to the !
annotation on the key in Data.Map and Data.Set is the very limited
justification that the compare function is required to be able to do
something with the key, so it'll need to do look at it somehow (discounting
the () case).

Using a value-strict map underneath strikes me as a bad solution, because
the non-strict case requires an extra layer of indirection, ensuring crappy
performance for the lazy version. While both versions can perform well when
there is no 'underlying container' involved, just one type. Using strict
methods to plug leaks is fine, but it really is the exception rather than
the rule and so the feature should "pay its own way" -- to borrow a phrase
from Kent Dybvig -- rather than impose a tax on every other use case.

The reason I don't like the two-data-types solution, is that I really don't
think that in addition to making up pseudo-Functor/Foldable/Traversable
instances that I need to second guess in any code that uses them, it also
eliminates the ability to fix up leaks on a case by case basis.

If you use some 'underlying value-strict' container, then I can't just
switch back and forth, instead I must map a Boxed type through, and wrap it
in a newtype wrapper to call a single lazy method, or unwrap, and map the
unboxing method through everywhere in order to force a single value. Both of
these strike me as remarkably poor solutions.

With the two module, one type approach, I can happily use the default Map
type, and add a ' here or there (or use a qualified Strict.foo instead of
foo) to fix leaky behavior.


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

Yes it would be lazy, but I don't see how it negates any benefits from your
strict API. Just expose a Strict.map.

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