<div dir="ltr"><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-family:arial,sans-serif;font-size:13px">In the 'free' approach, I find it unpleasant that some laws are automatic from the functor type, while others have to be ensured by the interpreter. That's why 'operational' offers only one way to implement monads: everything has to be done in the interpreter.</span></blockquote>
<div class="gmail_default" style="font-family:'courier new',monospace"></div><div class="gmail_default"><font face="arial, helvetica, sans-serif">As far as I know these instances are heavily used in practice, though they are inconvenient in a way. Perhaps they could be moved in a separate module. On the other hand one could use `FreeT` which derives instances in a different manner.</font></div>
</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span style="font-family:arial,sans-serif;font-size:13px">If you look at the transformer version Control.Monad.Trans.Free , you will see that there are no MonadState instances -- as expected, because you have to specify the interaction of effects.</span></blockquote>
<div><br></div><div class="gmail_default"><font face="arial, helvetica, sans-serif">Some instances are present in HEAD [1], just not on hackage yet. Some other instances (MonadCont [2], MonadWriter [3]) are waiting for Edward Kmett's approval.</font></div>
<div class="gmail_default"><font face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default"><font face="arial, helvetica, sans-serif">Note that `Free` does not have "the true" set of mtl instances. While these instances (derived from underlying functor) are heavily used in practice for `Free`, `FreeT` suggests deriving instances from the transformed monad (not underlying functor). It turns out the latter can be done for the most part of MonadX instances (MonadWriter instance is somewhat questionable). See some comments in [4].</font></div>
<div class="gmail_default"><font face="arial, helvetica, sans-serif"><br></font></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<span style="font-family:arial,sans-serif;font-size:13px">That said, as we saw, Free can give you some laws automatically. However, this also has a drawback: Program has an optimization that Free can never have. Namely, Program gives you a (>>=) that can be used in a left-associative way (Think (((x ++ y) ++ z) ++ w) ) while still allowing pattern matching.</span></blockquote>
<div><br></div><div class="gmail_default"><font face="arial, helvetica, sans-serif">As far as I can tell, this corresponds to church encoded versions of `Free` and `FreeT`, namely `F` and `FT`</font><font face="courier new, monospace">.</font><br>
<font face="arial, helvetica, sans-serif">This is possible due to the work </font><span style="color:rgb(0,0,0);font-family:sans-serif;font-size:13px;line-height:18px">"Asymptotic Improvement of Computations over Free Monads" by Janis Voightländer [5] and based on Edward Kmett's </span><span style="color:rgb(0,0,0);font-family:sans-serif;font-size:13px;line-height:18px">"Free Monads for Less" series of articles [6,7]. `F` is on hackage already and `FT` is in HEAD.</span></div>
<div class="gmail_default"><span style="color:rgb(0,0,0);font-family:sans-serif;font-size:13px;line-height:18px"><br></span></div><div class="gmail_default"><span style="color:rgb(0,0,0);font-family:sans-serif;font-size:13px;line-height:18px">Best,</span></div>
<div class="gmail_default"><span style="color:rgb(0,0,0);font-family:sans-serif;font-size:13px;line-height:18px">Nick</span></div><div class="gmail_default"><span style="color:rgb(0,0,0);font-family:sans-serif;font-size:13px;line-height:18px"><br>
</span></div><div class="gmail_default"><font face="arial, helvetica, sans-serif">[1] <a href="https://github.com/ekmett/free">https://github.com/ekmett/free</a></font></div><div class="gmail_default"><font face="arial, helvetica, sans-serif">[2] </font><a href="https://github.com/ekmett/free/pull/33">https://github.com/ekmett/free/pull/33</a></div>
<div class="gmail_default">[3] <a href="https://github.com/ekmett/free/issues/25">https://github.com/ekmett/free/issues/25</a></div><div class="gmail_default">[4] <a href="https://github.com/ekmett/free/issues/31#issuecomment-28481426">https://github.com/ekmett/free/issues/31#issuecomment-28481426</a></div>
<div class="gmail_default">[5] <a href="http://www.iai.uni-bonn.de/~jv/mpc08.pdf">http://www.iai.uni-bonn.de/~jv/mpc08.pdf</a></div><div class="gmail_default">[6] <a href="http://comonad.com/reader/2011/free-monads-for-less/">http://comonad.com/reader/2011/free-monads-for-less/</a></div>
<div class="gmail_default">[7] <a href="http://comonad.com/reader/2011/free-monads-for-less-2/">http://comonad.com/reader/2011/free-monads-for-less-2/</a></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">
2013/11/30 Heinrich Apfelmus <span dir="ltr"><<a href="mailto:apfelmus@quantentunnel.de" target="_blank">apfelmus@quantentunnel.de</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">Alejandro Serrano Mena wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Dear Café,<br>
I've been reading lately about the relation between the 'free' package and<br>
the 'operational' package for rolling your own monads [1] [2]. Furthermore,<br>
I've discovered that the 'free-operational' package, which is some sort of<br>
bridge between the two worlds, and provides not only Monad but also<br>
Applicative and Alternative instances for ProgramT.<br>
The problem is that right now everything is a little confused in my head.<br>
In particular, I have the following questions:<br>
</blockquote>
<br></div>
(Author of 'operational' here.)<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
- I've read that free allows you to 'bake algebraic laws' in the resulting<br>
monad. How does this work? Why doesn't operational offer that feature?<br>
</blockquote>
<br></div>
What I mean by 'baking in algebraic laws' is the following: Consider the free monad over the functor<br>
<br>
data F a = MZero | MPlus a a<br>
<br>
mzero :: Free F a<br>
mzero = Free MZero<br>
<br>
mplus :: Free F a -> Free F a -> Free F a<br>
mplus x y = Free (MPlus x y)<br>
<br>
For convenience, let me reproduce the relevant definitions for the free monad here<br>
<br>
data Free f a = Return a | Free (f (Free f a))<br>
<br>
(>>=) :: Functor f => Free f a -> (a -> Free f b) -> Free f b<br>
(>>=) (Return a) k = k a<br>
(>>=) (Free x) k = Free (fmap (>>= k) x)<br>
<br>
Now, if you think about the definition of bind for a moment, you will see that it automatically guarantees a distributive law for mplus :<br>
<br>
mplus x y >>= k = mplus (x >>= k) (y >>= k)<br>
<br>
However, it turns out [1] that there is another law that you might want mplus to satisfy<br>
<br>
mplus (return a) y = return a<br>
<br>
but which is incompatible with the distributive law. So, if you want to implement a monad where mplus should obey the latter law, you have to start with a different functor type F (which one?).<br>
<br>
<br>
In the 'free' approach, I find it unpleasant that some laws are automatic from the functor type, while others have to be ensured by the interpreter. That's why 'operational' offers only one way to implement monads: everything has to be done in the interpreter.<br>
<br>
[1]: <a href="http://www.haskell.org/haskellwiki/MonadPlus" target="_blank">http://www.haskell.org/<u></u>haskellwiki/MonadPlus</a><div class="im"><br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
- One of the things I really like from the free package is that it provides<br>
support for many monad transformer stacks, whereas operational does not? Is<br>
there any special restriction why operational cannot do this? Would it be<br>
possible to provide similar instances for free-operational?<br>
</blockquote>
<br></div>
There is a good reason why 'operational' cannot do this: in general, it is impossible to mix different effects in a general way. Why would<br>
<br>
ProgramT SomeInstruction (State s)<br>
<br>
be a state monad as well even though SomeInstruction can introduce new effects?<br>
<br>
If you look at the monad transformer instances for Free , like MonadState, you will notice that they require the functor to be that monad, i.e. they make use of the "baking in laws" effect. This is quite useless in practice, as writing a MonadState instance of the instruction type F is the same work as writing a MonadState instance for the Free F monad.<br>
<br>
If you look at the transformer version Control.Monad.Trans.Free , you will see that there are no MonadState instances -- as expected, because you have to specify the interaction of effects.<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
- It seems that free gives more features (Alternative, Applicative) with<br>
the same work. In which situations should I prefer operational to free? I<br>
really like the separation between providing a data type and then a<br>
interpretation that operational embodies...<br>
</blockquote>
<br></div>
Well, the features may look good on screen, but once you check the preconditions for the class instances, you will find that fulfilling them is as much work as writing the instance from scratch.<br>
<br>
The only two things that a free monad can give you is:<br>
<br>
* A Monad instance.<br>
* A way to pattern match on instructions and write an interpreter.<br>
<br>
This is what operational does. Everything else just shuffles work around, but doesn't alleviate it for you.<br>
<br>
That said, as we saw, Free can give you some laws automatically. However, this also has a drawback: Program has an optimization that Free can never have. Namely, Program gives you a (>>=) that can be used in a left-associative way (Think (((x ++ y) ++ z) ++ w) ) while still allowing pattern matching.<div class="im">
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
- Should I replace my usage of operational with free-operational altogether?<br>
</blockquote>
<br></div>
I would say no, but then again, I'm the author of the 'operational' package. :)<br>
<br>
<br>
Best regards,<br>
Heinrich Apfelmus<br>
<br>
--<br>
<a href="http://apfelmus.nfshost.com" target="_blank">http://apfelmus.nfshost.com</a><div class="HOEnZb"><div class="h5"><br>
<br>
______________________________<u></u>_________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br></div>