free vs. operational vs. free-operational
Dear Café, I've been reading lately about the relation between the 'free' package and the 'operational' package for rolling your own monads [1] [2]. Furthermore, I've discovered that the 'free-operational' package, which is some sort of bridge between the two worlds, and provides not only Monad but also Applicative and Alternative instances for ProgramT. The problem is that right now everything is a little confused in my head. In particular, I have the following questions: - I've read that free allows you to 'bake algebraic laws' in the resulting monad. How does this work? Why doesn't operational offer that feature? - One of the things I really like from the free package is that it provides support for many monad transformer stacks, whereas operational does not? Is there any special restriction why operational cannot do this? Would it be possible to provide similar instances for free-operational? - It seems that free gives more features (Alternative, Applicative) with the same work. In which situations should I prefer operational to free? I really like the separation between providing a data type and then a interpretation that operational embodies... - Should I replace my usage of operational with free-operational altogether? Thanks for the help :) [1] http://www.reddit.com/r/haskell/comments/17a33g/free_functors_the_reason_fre... [2] http://stackoverflow.com/questions/14263363/is-operational-really-isomorphic...
Alejandro Serrano Mena wrote:
Dear Café, I've been reading lately about the relation between the 'free' package and the 'operational' package for rolling your own monads [1] [2]. Furthermore, I've discovered that the 'free-operational' package, which is some sort of bridge between the two worlds, and provides not only Monad but also Applicative and Alternative instances for ProgramT. The problem is that right now everything is a little confused in my head. In particular, I have the following questions:
(Author of 'operational' here.)
- I've read that free allows you to 'bake algebraic laws' in the resulting monad. How does this work? Why doesn't operational offer that feature?
What I mean by 'baking in algebraic laws' is the following: Consider the free monad over the functor data F a = MZero | MPlus a a mzero :: Free F a mzero = Free MZero mplus :: Free F a -> Free F a -> Free F a mplus x y = Free (MPlus x y) For convenience, let me reproduce the relevant definitions for the free monad here data Free f a = Return a | Free (f (Free f a)) (>>=) :: Functor f => Free f a -> (a -> Free f b) -> Free f b (>>=) (Return a) k = k a (>>=) (Free x) k = Free (fmap (>>= k) x) Now, if you think about the definition of bind for a moment, you will see that it automatically guarantees a distributive law for mplus : mplus x y >>= k = mplus (x >>= k) (y >>= k) However, it turns out [1] that there is another law that you might want mplus to satisfy mplus (return a) y = return a 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?). 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. [1]: http://www.haskell.org/haskellwiki/MonadPlus
- One of the things I really like from the free package is that it provides support for many monad transformer stacks, whereas operational does not? Is there any special restriction why operational cannot do this? Would it be possible to provide similar instances for free-operational?
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 ProgramT SomeInstruction (State s) be a state monad as well even though SomeInstruction can introduce new effects? 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. 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.
- It seems that free gives more features (Alternative, Applicative) with the same work. In which situations should I prefer operational to free? I really like the separation between providing a data type and then a interpretation that operational embodies...
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. The only two things that a free monad can give you is: * A Monad instance. * A way to pattern match on instructions and write an interpreter. This is what operational does. Everything else just shuffles work around, but doesn't alleviate it for you. 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.
- Should I replace my usage of operational with free-operational altogether?
I would say no, but then again, I'm the author of the 'operational' package. :) Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
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.
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.
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.
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. 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]. 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.
As far as I can tell, this corresponds to church encoded versions of `Free`
and `FreeT`, namely `F` and `FT`.
This is possible due to the work "Asymptotic Improvement of Computations
over Free Monads" by Janis Voightländer [5] and based on Edward Kmett's "Free
Monads for Less" series of articles [6,7]. `F` is on hackage already and
`FT` is in HEAD.
Best,
Nick
[1] https://github.com/ekmett/free
[2] https://github.com/ekmett/free/pull/33
[3] https://github.com/ekmett/free/issues/25
[4] https://github.com/ekmett/free/issues/31#issuecomment-28481426
[5] http://www.iai.uni-bonn.de/~jv/mpc08.pdf
[6] http://comonad.com/reader/2011/free-monads-for-less/
[7] http://comonad.com/reader/2011/free-monads-for-less-2/
2013/11/30 Heinrich Apfelmus
Alejandro Serrano Mena wrote:
Dear Café, I've been reading lately about the relation between the 'free' package and the 'operational' package for rolling your own monads [1] [2]. Furthermore, I've discovered that the 'free-operational' package, which is some sort of bridge between the two worlds, and provides not only Monad but also Applicative and Alternative instances for ProgramT. The problem is that right now everything is a little confused in my head. In particular, I have the following questions:
(Author of 'operational' here.)
- I've read that free allows you to 'bake algebraic laws' in the resulting
monad. How does this work? Why doesn't operational offer that feature?
What I mean by 'baking in algebraic laws' is the following: Consider the free monad over the functor
data F a = MZero | MPlus a a
mzero :: Free F a mzero = Free MZero
mplus :: Free F a -> Free F a -> Free F a mplus x y = Free (MPlus x y)
For convenience, let me reproduce the relevant definitions for the free monad here
data Free f a = Return a | Free (f (Free f a))
(>>=) :: Functor f => Free f a -> (a -> Free f b) -> Free f b (>>=) (Return a) k = k a (>>=) (Free x) k = Free (fmap (>>= k) x)
Now, if you think about the definition of bind for a moment, you will see that it automatically guarantees a distributive law for mplus :
mplus x y >>= k = mplus (x >>= k) (y >>= k)
However, it turns out [1] that there is another law that you might want mplus to satisfy
mplus (return a) y = return a
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?).
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.
[1]: http://www.haskell.org/haskellwiki/MonadPlus
- One of the things I really like from the free package is that it
provides support for many monad transformer stacks, whereas operational does not? Is there any special restriction why operational cannot do this? Would it be possible to provide similar instances for free-operational?
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
ProgramT SomeInstruction (State s)
be a state monad as well even though SomeInstruction can introduce new effects?
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.
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.
- It seems that free gives more features (Alternative, Applicative) with
the same work. In which situations should I prefer operational to free? I really like the separation between providing a data type and then a interpretation that operational embodies...
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.
The only two things that a free monad can give you is:
* A Monad instance. * A way to pattern match on instructions and write an interpreter.
This is what operational does. Everything else just shuffles work around, but doesn't alleviate it for you.
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.
- Should I replace my usage of operational with free-operational
altogether?
I would say no, but then again, I'm the author of the 'operational' package. :)
Best regards, Heinrich Apfelmus
-- http://apfelmus.nfshost.com
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Nickolay Kudasov wrote:
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. 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.
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.
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.
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.
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). 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. (The MonadReader class has a control operation, local , but looking at the source for FreeT , it appears that it can actually be lifted. Amazing!)
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].
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.
As far as I can tell, this corresponds to church encoded versions of `Free` and `FreeT`, namely `F` and `FT`. This is possible due to the work "Asymptotic Improvement of Computations over Free Monads" by Janis Voightländer [5] and based on Edward Kmett's "Free Monads for Less" series of articles [6,7]. `F` is on hackage already and `FT` is in HEAD.
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) . In contrast, Program represents lists of instructions in a way similar to data List a = Nil | One a | Concat (List a) (List a) 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. To summarize, I currently don't see what 'free' offers that the 'operational' package can't do equally well with only 11 exported symbols. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
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.
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). (But I think it will be impossible for MonadCont). It is. See https://github.com/ekmett/free/pull/33 for FreeT. FT has the instance in HEAD already. Almost, but not quite. The key qualification is "while still allowing
pattern matching".
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. To summarize, I currently don't see what 'free' offers that the
'operational' package can't do equally well with only 11 exported symbols.
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).
That all said, I don't feel myself concerned/experienced enough to state
that one package should be preferred to another.
Best,
Nick
2013/12/1 Heinrich Apfelmus
Nickolay Kudasov wrote:
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.
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.
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.
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.
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.
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).
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.
(The MonadReader class has a control operation, local , but looking at the source for FreeT , it appears that it can actually be lifted. Amazing!)
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].
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.
As far as I can tell, this corresponds to church encoded versions of `Free` and `FreeT`, namely `F` and `FT`. This is possible due to the work "Asymptotic Improvement of Computations over Free Monads" by Janis Voightländer [5] and based on Edward Kmett's "Free Monads for Less" series of articles [6,7]. `F` is on hackage already and `FT` is in HEAD.
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) .
In contrast, Program represents lists of instructions in a way similar to
data List a = Nil | One a | Concat (List a) (List a)
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.
To summarize, I currently don't see what 'free' offers that the 'operational' package can't do equally well with only 11 exported symbols.
Best regards, Heinrich Apfelmus
-- http://apfelmus.nfshost.com
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Nickolay Kudasov wrote:
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.
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).
Yes, but in this case, Free P is useful *regardless* of P being a monad. If you didn't declare a monad instance for the P type, then you would still get the tree of probabilities. It bugs me that the functor is expected to already be a monad. The instance MonadState s m => MonadState s (Free m) is a fancy way of saying that if the instruction type m has two instructions get and put , then the free monad will have them as well. This is fine from the perspective of variant types, but we don't need to know that m is a monad for that. Furthermore, the MonadState class suggests that the usual laws for the state monad hold -- which they do not! Here a counterexample: {-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-} import Control.Monad.State data Free f a = Return a | Free (f (Free f a)) instance Functor f => Monad (Free f) where return = Return (Free f) >>= k = Free $ fmap (>>= k) f instance MonadState s (Free (State s)) where state f = Free . state $ \s -> let (a,s') = f s in (Return a, s') interpret :: Free (State s) a -> (s -> s) interpret (Return a) s0 = s0 interpret (Free f ) s0 = snd (runState f s0) -- apply only the first instruction, skip the rest example1 = interpret (put 'a' >> get >> put 'b' >> get) undefined example2 = interpret (put 'b' >> get) undefined If we expect the usual laws for the state monad, then both example1 and example2 should be the same value. However, this is not the case: example1 = 'a' while example2 = 'b' . Just because you have two operations put and get doesn't mean that they can't have additional effects. And apparently, the MonadState condition is not strong enough to guarantee all the put/get laws.
(But I think it will be impossible for MonadCont).
It is. See https://github.com/ekmett/free/pull/33 for FreeT. FT has the instance in HEAD already.
That's surprising, I will have to check that. It appears to me that the MonadReader instance is only correct because the control operation is a morphism: local f (m >>= k) = local f m >>= local f . k Otherwise, I don't see how a general control operation can be lifted.
Almost, but not quite. The key qualification is "while still allowing pattern matching".
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.
A pattern match view :: F f a -> Either a (f (F f a)) that runs in O(1) time is very useful for implementing interpreters. For an example, see [1]. In particular, we can use the remainder to create new monadic actions with (>>=). The distinction is similar between being able to pattern match on (:) and using only fold to operate on lists. The former is more flexible. [1]: https://github.com/HeinrichApfelmus/operational/blob/master/doc/examples/Bre...
To summarize, I currently don't see what 'free' offers that the
'operational' package can't do equally well with only 11 exported symbols..
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).
That all said, I don't feel myself concerned/experienced enough to state that one package should be preferred to another.
As mentioned, I'm not a fan of the "baked in algrebraic laws" because this excludes an optimization and many laws have to be written in the interpreter anyway. But you're saying that 'free' provides other free structures besides monads. That's a good point. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
participants (3)
-
Alejandro Serrano Mena -
Heinrich Apfelmus -
Nickolay Kudasov