Quantcast

MonadZip for Data.Tree

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

MonadZip for Data.Tree

David Feuer
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: MonadZip for Data.Tree

Edward Kmett-2
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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: MonadZip for Data.Tree

David Feuer
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" <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: MonadZip for Data.Tree

Edward Kmett-2
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 <[hidden email]> 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" <[hidden email]> 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 <[hidden email]> 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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: MonadZip for Data.Tree

wren romano
On Thu, Dec 29, 2016 at 10:54 PM, Edward Kmett <[hidden email]> wrote:
> 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 one nice thing is that munzip can perform (fmap fst &&& fmap snd)
in a single pass, rather than taking two passes. This is why we have
all those combined functions in containers like insertLookup,
updateLookup, etc. Though, yes, I'd much rather have a more generic
version which works for any pair/set of functions rather than
hardcoding (fst,snd).

--
Live well,
~wren
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Loading...