<div dir="ltr"><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"><div class="gmail_default" style="font-family:'courier new',monospace;display:inline">
</div>Well, that they are heavily used in practice does not mean that they are actually useful in practice. The thing is that as soon as your functor is a monad, I don't think you really need the Free type anymore -- your instruction type is already a monad.</span></blockquote>
<div><font face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default"><font face="arial, helvetica, sans-serif">I don't use that myself, so I leave this for others to answer. But you should note that `Free m` is not the same as `m`: e.g. if `m` is a probability monad `newtype P a = P [(Double, a)]`, then `Free P` gives you much more: the whole tree of probabilities (not only probs of final results), so one could traverse that tree. So I believe `Free m` is rather useful (as is deriving instances for `Free m` the way it is).</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">(But I think it will be impossible for MonadCont).</span></blockquote><div class="gmail_default"><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div>
<div class="gmail_default"><span style="font-family:arial,sans-serif;font-size:13px">It is. See </span><a href="https://github.com/ekmett/free/pull/33">https://github.com/ekmett/free/pull/33</a> for FreeT. FT has the instance in HEAD already.</div>
<div class="gmail_default"><br></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">Almost, but not quite. The key qualification is "while still allowing pattern matching".</span></blockquote>
<div><br></div><div class="gmail_default"><font face="arial, helvetica, sans-serif">You're right. But I think it is unnecessary for a library user to pattern match on F's structure. It is pattern matching on supplied functor that matters. And that ability is not lost.</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">To summarize, I currently don't see what 'free' offers that the 'operational' package can't do equally well with only 11 exported symbols.</span></blockquote>
<div class="gmail_default"><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div class="gmail_default"><font face="arial, sans-serif">As far as I can tell, while with operational you can certainly do more things, free provides more things for free (these "baked algebraic laws"). free also provides some other interesting things, like iterative (co)monad trasformers, cofree comonads and free applicatives/alternatives (which are out of operational/free common area).</font></div>
<div class="gmail_default"><font face="arial, sans-serif"><br></font></div><div class="gmail_default"><font face="arial, sans-serif">That all said, I don't feel myself concerned/experienced enough to state that one package should be preferred to another.</font></div>
<div class="gmail_default"><font face="arial, sans-serif"><br></font></div><div class="gmail_default"><font face="arial, sans-serif">Best,</font></div><div class="gmail_default"><font face="arial, sans-serif">Nick</font></div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/12/1 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">Nickolay Kudasov wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
In the 'free' approach, I find it unpleasant that some laws are<br>
automatic from the functor type, while others have to be ensured by the<br>
interpreter. That's why 'operational' offers only one way to implement<br>
monads: everything has to be done in the interpreter.<br>
</blockquote>
<br>
As far as I know these instances are heavily used in practice, though they<br>
are inconvenient in a way. Perhaps they could be moved in a separate<br>
module. On the other hand one could use `FreeT` which derives instances in<br>
a different manner.<br>
</blockquote>
<br></div>
Well, that they are heavily used in practice does not mean that they are actually useful in practice. The thing is that as soon as your functor is a monad, I don't think you really need the Free type anymore -- your instruction type is already a monad.<div class="im">
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
If you look at the transformer version Control.Monad.Trans.Free , you<br>
will see that there are no MonadState instances -- as expected, because you<br>
have to specify the interaction of effects.<br>
</blockquote>
<br>
Some instances are present in HEAD [1], just not on hackage yet. Some<br>
other instances (MonadCont [2], MonadWriter [3]) are waiting for Edward<br>
Kmett's approval.<br>
</blockquote>
<br></div>
Ah, I see now. Yes, it is possible for all classes that don't have control operations. (But I think it will be impossible for MonadCont).<br>
<br>
And looking at my 'operational' package, it appears that ProgramT already includes the desired MonadState and MonadIO instances! In other words, 'operational' had always included proper support for monad transformer stacks.<br>
<br>
(The MonadReader class has a control operation, local , but looking at the source for FreeT , it appears that it can actually be lifted. Amazing!)<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Note that `Free` does not have "the true" set of mtl instances. While these<br>
instances (derived from underlying functor) are heavily used in practice<br>
for `Free`, `FreeT` suggests deriving instances from the transformed monad<br>
(not underlying functor). It turns out the latter can be done for the most<br>
part of MonadX instances (MonadWriter instance is somewhat questionable).<br>
See some comments in [4].<br>
<br>
That said, as we saw, Free can give you some laws automatically. However,<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
this also has a drawback: Program has an optimization that Free can never<br>
have. Namely, Program gives you a (>>=) that can be used in a<br>
left-associative way (Think (((x ++ y) ++ z) ++ w) ) while still allowing<br>
pattern matching.<br>
</blockquote>
<br>
As far as I can tell, this corresponds to church encoded versions of `Free`<br>
and `FreeT`, namely `F` and `FT`.<br>
This is possible due to the work "Asymptotic Improvement of Computations<br>
over Free Monads" by Janis Voightländer [5] and based on Edward Kmett's "Free<br>
Monads for Less" series of articles [6,7]. `F` is on hackage already and<br>
`FT` is in HEAD.<br>
</blockquote>
<br>
Almost, but not quite. The key qualification is "while still allowing pattern matching". The church encoding is akin to difference lists: you get O(1) (++), but now head and tail are O(n) .<br>
<br>
In contrast, Program represents lists of instructions in a way similar to<br>
<br>
data List a = Nil | One a | Concat (List a) (List a)<br>
<br>
This gives you O(1) append and head / tail if used in an ephemeral fashion. (It is actually possible to turn this into a genuine O(1) head and tail, but it's not worth it.) You can't do this optimization in Free.<br>
<br>
<br>
To summarize, I currently don't see what 'free' offers that the 'operational' package can't do equally well with only 11 exported symbols.<br>
<br>
<br>
Best regards,<br>
Heinrich Apfelmus<br>
<br>
--<br>
<a href="http://apfelmus.nfshost.com" target="_blank">http://apfelmus.nfshost.com</a><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>
</blockquote></div><br></div>