[Haskell-cafe] Why is there no Zippable class? Would this work?

Edward Kmett ekmett at gmail.com
Sun Jul 19 05:36:44 EDT 2009


On Fri, Jul 17, 2009 at 10:37 PM, <porges at porg.es> wrote:

> 2009/7/18 Edward Kmett <ekmett at gmail.com>:
>
>> I wrote a short blog post on this:
>> http://comonad.com/reader/2008/zipping-and-unzipping-functors/
>> and one on the less powerful dual operations (less powerful because while
>> every Haskell Functor is strong, much fewer are costrong):
>> http://comonad.com/reader/2008/cozipping/
>> -Edward Kmett
>>
>
> This is getting a bit OT, but I just wanted to comment that attempting to
> remove polymorphism from the Functor class (see thread a couple of days ago)
> means that not every Functor is strong. So strength for Functor would seem
> to require a fully polymorphic type. I don't know if costrength is 'easier'
> to derive for those 'restricted' Functors..


Continuing the OT aside...

Well, the monomorphic not-quite-Functor from that post is a pretty ugly
concept categorically, and obviously doesn't qualify as a Hask endofunctor,
given its limited scope. That isn't to say that occasionally you don't want
a function that can map a ByteString to a ByteString a byte at a time
-- merely that it is a different animal. ;)

Strength does require polymorphism... which comes for free if we're talking
about an actual endofunctor. The ad-hoc not-quite-Functor provides no
guarantee that a member of that you have an instance of the class supporting
pairs "instance Functor' F (X,Y)" or that if you do that you have an
instance for the class supports pairs that you have one for the left side of
the pair "instance Functor' F X" let alone that these definitions are
consistent.

But even if you grant all of that, regarding costrength, it makes things no
easier.

Costrength is effectively about the ability to check inside of a functor and
see if in some Functor f, a value f x where x = Either a b has any b's and
if so, it gives you one, otherwise it gives you an "f a", because no
b's occurred. Clearly for some simple functors you can complete this
operation. But, there are many for which you cannot. The most obvious
problem case is f = (->) a, because you need an oracle that knows the
outcome of an arbitrary Haskell function; Kurt Godel would roll over in his
grave. Similarly you run into problems deciding the outcome of costrength on
a stream of Eithers even if you limit your instances to the bare minimum of
() and Either () (), because you'd need to decide equality of streams, which
leads to a need for a halting problem oracle.

See http://comonad.com/reader/2008/deriving-strength-from-laziness/ for more
details.

-Edward Kmett
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090719/99609bfb/attachment.html


More information about the Haskell-Cafe mailing list