Proposal: Warn about ArrowLoop instance for Kleisli Arrows
Hello, I recently noticed that the instance MonadFix m => ArrowLoop (Kleisli m) does not fulfill the ArrowLoop laws for most monads, rendering it either useless or dangerous for the unwary. Removing it would be the correct thing to do, but I think that the sensible thing to do is to merely document said fact at the instance declaration in the haddocks. This way, the few monads that do support an ArrowLoop instance (most notably the lazy state monad) can keep their instance while everyone else is warned. Thus, I suggest to add documentation to the instances, along the lines of "Even though every monad that supports 'mfix' can be made an instance of 'ArrowLoop', it usually /does not/ fulfill all of the corresponding ArrowLoop laws. Use this instance at your own risk." The main problem is the right-tightening law loop (first h <<< f) = h <<< loop f which fails for most monads. Consider the following example: bad :: String -> IO () bad = runKleisli $ loop (first (Kleisli putStrLn) <<< arr swap) where swap (a,b) = (b,a) Using the ArrowLoop laws [1], this example should be equal to ... = runKleisli $ Kleisli putStrLn <<< loop (arr swap) = putStrLn However, trying the example in GHCi will throw "Exception: <<loop>>", which clearly shows that this equality is not true. The underlying reason is that MonadFix doesn't support a corresponding right-tightening law, just as mentioned for example in [2]. [1]: http://www.soi.city.ac.uk/~ross/papers/fop.html [2]: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5172 Discussion period: 2 weeks (ends 24 October 2011) Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
On Sun, 9 Oct 2011, Heinrich Apfelmus wrote:
Hello,
I recently noticed that the instance
MonadFix m => ArrowLoop (Kleisli m)
does not fulfill the ArrowLoop laws for most monads, rendering it either useless or dangerous for the unwary. Removing it would be the correct thing to do, but I think that the sensible thing to do is to merely document said fact at the instance declaration in the haddocks. This way, the few monads that do support an ArrowLoop instance (most notably the lazy state monad) can keep their instance while everyone else is warned.
... and since the lazy state monad does not fulfill the Functor laws, there is no monad at all, where the ArrowLoop instance is correct?
On Sun, Oct 9, 2011 at 4:57 AM, Henning Thielemann
... and since the lazy state monad does not fulfill the Functor laws, there is no monad at all, where the ArrowLoop instance is correct?
What about the arrow type A' = Kleisli (ArrowMonad A) where A is a instance of ArrowApply and ArrowLoop? -- Felipe.
Henning Thielemann wrote:
On Sun, 9 Oct 2011, Heinrich Apfelmus wrote:
I recently noticed that the instance
MonadFix m => ArrowLoop (Kleisli m)
does not fulfill the ArrowLoop laws for most monads, rendering it either useless or dangerous for the unwary. Removing it would be the correct thing to do, but I think that the sensible thing to do is to merely document said fact at the instance declaration in the haddocks. This way, the few monads that do support an ArrowLoop instance (most notably the lazy state monad) can keep their instance while everyone else is warned.
.... and since the lazy state monad does not fulfill the Functor laws, there is no monad at all, where the ArrowLoop instance is correct?
Ah, I don't intend to haggle over seq and _|_. In my view, the ArrowLoop instance for the lazy state monad fulfills the right-tightening law just fine. The trouble is with monads where you cannot a write a function first :: (a -> M b) -> ((a,d) -> M (b,d)) that allows you to "lazily observe" the second parameter d without forcing a to some extend. The lazy state monad allows you to write first m = \p -> m (fst p) >>= \b -> return (b,snd p) = \p s -> let (b,s') = m (fst p) s in ((b,snd p),s') and you can extract the d component from the result just fine. But, according to the literature, you can't something similar for monads where >>= is strict in the first argument, like Maybe or [] or IO or various monad transformer stacks. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
Heinrich Apfelmus writes:
Thus, I suggest to add documentation to the instances, along the lines of "Even though every monad that supports 'mfix' can be made an instance of 'ArrowLoop', it usually /does not/ fulfill all of the corresponding ArrowLoop laws. Use this instance at your own risk."
The main problem is the right-tightening law
loop (first h <<< f) = h <<< loop f
which fails for most monads.
We could be more specific: "For many monads (those for which the '>>=' operation is strict) this instance will not satisfy the right-tightening law."
Heinrich Apfelmus wrote:
I recently noticed that the instance
MonadFix m => ArrowLoop (Kleisli m)
does not fulfill the ArrowLoop laws for most monads, rendering it either useless or dangerous for the unwary. Removing it would be the correct thing to do, but I think that the sensible thing to do is to merely document said fact at the instance declaration in the haddocks.
[..] Discussion period: 2 weeks (ends 24 October 2011)
The discussion period has ended and it seems to me that there is unanimous support for this documentation change. The following formulation seems best to me: "Every monad that supports 'mfix' can be made an instance of 'ArrowLoop'. But for many monads (those for which the '>>=' operation is strict) this instance will /not/ satisfy the right-tightening law required by the 'ArrowLoop' class. Use these instances at your own risk." What exactly do I have to do to move this towards inclusion in the base libraries? Make a track ticket? And then? Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
On 25 October 2011 14:47, Heinrich Apfelmus > What exactly do I have to do to move this towards inclusion in the base
libraries? Make a track ticket? And then?
* First setup your system to build GHC: http://hackage.haskell.org/trac/ghc/wiki/Building/Preparation * Checkout the sources: $ git clone http://darcs.haskell.org/ghc.git/ $ cd ghc $ ./sync-all get * Make your change by editing: libraries/base/Control/Arrow.hs * Test it by building ghc and the libraries: $ cp mk/build.mk.sample mk/build.mk You might want to use the quick BuildFlavour but make sure to set HADDOCK_DOCS to YES. $ perl boot $ ./configure $ make * Commit! $ git add Control/Arrow.hs $ git commit $ git format-patch * Add the patch to your ticket. Not to spoil anything but I saw Ross already made the change ;-) Bas
Bas van Dijk wrote:
On 25 October 2011 14:47, Heinrich Apfelmus
What exactly do I have to do to move this towards inclusion in the base libraries? Make a track ticket? And then?
* First setup your system to build GHC: http://hackage.haskell.org/trac/ghc/wiki/Building/Preparation
* Checkout the sources: $ git clone http://darcs.haskell.org/ghc.git/ $ cd ghc $ ./sync-all get
* Make your change by editing: libraries/base/Control/Arrow.hs
* Test it by building ghc and the libraries: $ cp mk/build.mk.sample mk/build.mk You might want to use the quick BuildFlavour but make sure to set HADDOCK_DOCS to YES. $ perl boot $ ./configure $ make
* Commit! $ git add Control/Arrow.hs $ git commit $ git format-patch
* Add the patch to your ticket.
Not to spoil anything but I saw Ross already made the change ;-)
That's great, thanks! The procedure for Compiling GHC did look rather daunting to me. :) Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
Heinrich Apfelmus wrote:
Bas van Dijk wrote:
On 25 October 2011 14:47, Heinrich Apfelmus
What exactly do I have to do to move this towards inclusion in the base libraries? Make a track ticket? And then? [...] Not to spoil anything but I saw Ross already made the change ;-)
That's great, thanks! The procedure for Compiling GHC did look rather daunting to me. :)
I trimmed the warning a little. I also added the laws for the classes while I was there.
participants (5)
-
Bas van Dijk -
Felipe Almeida Lessa -
Heinrich Apfelmus -
Henning Thielemann -
Paterson, Ross