Re: Libraries Digest, Vol 93, Issue 21

On Tue, May 31, 2011 at 6:03 AM, John Lato wrote:

On Tue, May 31, 2011 at 2:08 AM, Edward Kmett 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