Libraries Digest, Vol 93, Issue 21

[John Lato]

On Tue, May 31, 2011 at 6:16 PM, Edward Kmett <ekmett at gmail.com> wrote:

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

I hope we can agree to disagree on this, although I would like to state that
I'm generally in favor of law-abiding instances.  Except for the particular
case of bottoms and strict types.


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

Yes, that's what I meant.


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

I don't like the two-data-types solution because it's duplication and is
much more work to maintain.  Not that I'll be maintaining it, but I still
find it ugly.


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

I'm not backing any particular approach, I was simply trying to explore the
ramifications of different designs which have been proposed.  I think most
people have expressed a preference for the Data.HashMap style of
implementation now anyway.

Personally, what I would like to see are hooks for reduction strategies.  I
often want this for tuples.


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

That only works if you use Strict.map instead of fmap.  If you're using a
third-party algorithm, that may not be an option.

John
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110531/540f4d12/attachment-0001.htm>