MonadZip for Data.Tree

[Edward Kmett]

By opposite facing information preservation law, I mean there is a law
right now called Information Preservation in the haddocks for the class.

It only supplies half the story about how uncurry mzip and munzip are
"almost inverses", but the law given in the haddocks is actually pretty
weird.

The nice law I mentioned 'uncurry mzip . munzip = id' says uncurry mzip
'retracts' munzip in category theoretic terms.

The existing law is kind of abomination that tries to imply that if you
have the same shape on both sides they should zip together in a way that
unzips without destroying or creating any weird new shapes, but without the
retraction law I don't think you can prove that you've ruled out all the
wonky instances.

As for what I have against munzip as a member, it is a boring, unnecessary
member with no interesting definitions. It has to be equivalent to fmap fst
&&& fmap snd to pass the laws and free theorems involved.

The *only* interesting instance I've ever derived is one I came up with for
a memoizing variant of Lindsey Kuper's idempotent Par monad that admits
pure LVar reads, and lacks region parameters. There you could exploit
idempotence to reuse the results and share *some* computation effort in
case you use <*> to glue the parts you munzipped back together, but I don't
exactly see people lining up to use it. ;) As a pure computation you need
to make a new promise/IVar, fill it with the computation that will produce
the (a,b) pair. Then return two computations that each demand the result of
the promise when run and fmap fst or fmap snd the result appropriately.

But building that one interesting monad requires embracing at least
unsafeInterleaveST levels of evil, and the instance requires upgrading that
to unsafePerformST levels of messiness.

-Edward

On Fri, Dec 30, 2016 at 12:22 AM, David Feuer <david.feuer at gmail.com> wrote:

> The class is altogether annoying because it has a Monad superclass instead
> of a Functor one, excluding perfectly good zippable functors like Map k,
> IntMap k, and even, ironically, ZipList. What do you mean by the opposite
> facing information preservation law? And what do you have against munzip,
> aside from the fact that it looks like it wants to be in the
> too-lofty-for-its-like circle of Functor?
>
> On Dec 29, 2016 11:22 PM, "Edward Kmett" <ekmett at gmail.com> wrote:
>
> No real preference, but this does remind me that MonadZip probably should
> have the following extra law:
>
> uncurry mzip . munzip = id
>
> This law is passed by all current instances and fits the intent of much
> harder to state opposite facing information preservation law.
>
> Since we continue to insist on this class containing the annoying munzip
> operation, this law is actually far easier to demonstrate than the existing
> law.
>
> We can also restate the other information preservation law now that
> Functor is a superclass of Monad to the rather more succinct
>
> () <$ ma = () <$ mb ==>  munzip (mzip ma mb) = (ma, mb)
>
> -Edward
>
> On Thu, Dec 29, 2016 at 4:54 PM, David Feuer <david.feuer at gmail.com>
> wrote:
>
>> MonadZip doesn't really explain how strict mzipWith and (especially)
>> munzip should be. For example, we could have
>>
>>   munzip (Node (a, b) ts) = (Node a as, Node b bs)
>>     where (as, bs) = Data.List.unzip (map munzip ts)
>>
>> or we could make some or all of the pattern matches lazy, or we could
>> use something lazier than Data.List.unzip, or we could make everything
>> completely spine-strict (surely unwise).
>>
>> Does anyone have a particular preference, or a particular reason to
>> prefer one choice over others? If not, I think we should go with the
>> simple version above.
>>
>> David Feuer
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20161230/7f6b42a7/attachment.html>