free vs. operational vs. free-operational

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
20 messages Options
Reply | Threaded
Open this post in threaded view
|

free vs. operational vs. free-operational

Alejandro Serrano Mena
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 :)


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

oleg-30

Alejandro Serrano Mena wrote:
> I really like the separation between providing a data type and then a
> interpretation that operational embodies...

Then perhaps you may like extensible effects then. They are designed
around the separation of requestors and their interpreters. However, the
set of requests is open (and can be extended at any time without
recompiling the program). Likewise the interpreters can be extended
incrementally. One can add an interpreter for an effect without caring
what other effects are there -- unless one has some reason for caring
about other effects (e.g.,m for finalization). One may then snoop on
other effects while interpreting. Moreover, the handlers may be
scattered around program; they don't have to be all at the very top.

Crucially, unlike data types a la carte, extensible effects provide
effect encapsulation: one can not only add effects but subtract them,
by completely handling the effects. The type system ensures that all
effects must be completely handled at the end.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Nickolay Kudasov

Hi Oleg,

These extensible effects are great, thank you for bringing them up!

However it seems that the code is still under early development.
Could you please elaborate on the current state of the project?
Can it be considered stable?
Where should I look for the uses of extensible effects?

Thanks in advance,
Nick



2013/11/26 <[hidden email]>

Alejandro Serrano Mena wrote:
> I really like the separation between providing a data type and then a
> interpretation that operational embodies...

Then perhaps you may like extensible effects then. They are designed
around the separation of requestors and their interpreters. However, the
set of requests is open (and can be extended at any time without
recompiling the program). Likewise the interpreters can be extended
incrementally. One can add an interpreter for an effect without caring
what other effects are there -- unless one has some reason for caring
about other effects (e.g.,m for finalization). One may then snoop on
other effects while interpreting. Moreover, the handlers may be
scattered around program; they don't have to be all at the very top.

Crucially, unlike data types a la carte, extensible effects provide
effect encapsulation: one can not only add effects but subtract them,
by completely handling the effects. The type system ensures that all
effects must be completely handled at the end.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Ben Foppa
Hi Nick,

Uploader and current maintainer of the extensible-effects package here.
Although I'm still confused myself about the more theoretical bits of extensible-effects,
I think I might be able to shed some light on it from a user's and maintainer's perspective.

extensible-effects is currently operational, and works quite well wherever I use it.
That said, it's a new package and I'd expect some shifts before it settles down.

In general, extensible-effects seems to be applicable in most cases where one might think "hey, I should make a Monad for this".
The base extensible-effects package includes "translations" of Control.Monad.Fresh, as well as Control.Monad.State.Strict.
Clark Gaebel has also created the system-random-effect package for (pure) random number generation via the extensible-effects interface.
Although the implementations will generally differ from traditional monadic implementations,
the usage is remarkably similar (by far the most common use I've had of extensible-effects is using do-notation).

Hope this helps,
Ben Foppa

On Tuesday, 26 November 2013 07:20:15 UTC-5, Nickolay Kudasov wrote:

Hi Oleg,

These extensible effects are great, thank you for bringing them up!

However it seems that the code is still under early development.
Could you please elaborate on the current state of the project?
Can it be considered stable?
Where should I look for the uses of extensible effects?

Thanks in advance,
Nick



2013/11/26 <<a href="javascript:" target="_blank" gdf-obfuscated-mailto="t-RVdpBBchYJ" onmousedown="this.href='javascript:';return true;" onclick="this.href='javascript:';return true;">ol...@...>

Alejandro Serrano Mena wrote:
> I really like the separation between providing a data type and then a
> interpretation that operational embodies...

Then perhaps you may like extensible effects then. They are designed
around the separation of requestors and their interpreters. However, the
set of requests is open (and can be extended at any time without
recompiling the program). Likewise the interpreters can be extended
incrementally. One can add an interpreter for an effect without caring
what other effects are there -- unless one has some reason for caring
about other effects (e.g.,m for finalization). One may then snoop on
other effects while interpreting. Moreover, the handlers may be
scattered around program; they don't have to be all at the very top.

Crucially, unlike data types a la carte, extensible effects provide
effect encapsulation: one can not only add effects but subtract them,
by completely handling the effects. The type system ensures that all
effects must be completely handled at the end.


_______________________________________________
Haskell-Cafe mailing list
<a href="javascript:" target="_blank" gdf-obfuscated-mailto="t-RVdpBBchYJ" onmousedown="this.href='javascript:';return true;" onclick="this.href='javascript:';return true;">Haskel...@...
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank" onmousedown="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.haskell.org%2Fmailman%2Flistinfo%2Fhaskell-cafe\46sa\75D\46sntz\0751\46usg\75AFQjCNHiVycCM53czUVzPma4Fkb_wPqP2A';return true;" onclick="this.href='http://www.google.com/url?q\75http%3A%2F%2Fwww.haskell.org%2Fmailman%2Flistinfo%2Fhaskell-cafe\46sa\75D\46sntz\0751\46usg\75AFQjCNHiVycCM53czUVzPma4Fkb_wPqP2A';return true;">http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Alejandro Serrano Mena
In reply to this post by oleg-30
Thanks for the pointer! :)
The extensible-effects package seems very interesting. I would really like to have instances of all usual monads: Reader, Writer, State.Lazy and so on in the package. Maybe that's a project for the future :)

Even so, I'm still interesting in understanding my original concerns with free vs. operational, specially the "baking algebraic laws" part and whether it's good to replace operational with free-operational altogether.


2013/11/26 <[hidden email]>

Alejandro Serrano Mena wrote:
> I really like the separation between providing a data type and then a
> interpretation that operational embodies...

Then perhaps you may like extensible effects then. They are designed
around the separation of requestors and their interpreters. However, the
set of requests is open (and can be extended at any time without
recompiling the program). Likewise the interpreters can be extended
incrementally. One can add an interpreter for an effect without caring
what other effects are there -- unless one has some reason for caring
about other effects (e.g.,m for finalization). One may then snoop on
other effects while interpreting. Moreover, the handlers may be
scattered around program; they don't have to be all at the very top.

Crucially, unlike data types a la carte, extensible effects provide
effect encapsulation: one can not only add effects but subtract them,
by completely handling the effects. The type system ensures that all
effects must be completely handled at the end.




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Nickolay Kudasov
Hi Alejandro,

I suspect that "baking algebraic laws" means "getting monad laws for free".

There's a talk by Andres Loh [1] in which he explains some approaches to custom EDSLs in Haskell, namely, using GADTs and free monads. The former is actually what `operational` implements and the latter is the `free` package.



2013/11/27 Alejandro Serrano Mena <[hidden email]>
Thanks for the pointer! :)
The extensible-effects package seems very interesting. I would really like to have instances of all usual monads: Reader, Writer, State.Lazy and so on in the package. Maybe that's a project for the future :)

Even so, I'm still interesting in understanding my original concerns with free vs. operational, specially the "baking algebraic laws" part and whether it's good to replace operational with free-operational altogether.


2013/11/26 <[hidden email]>


Alejandro Serrano Mena wrote:
> I really like the separation between providing a data type and then a
> interpretation that operational embodies...

Then perhaps you may like extensible effects then. They are designed
around the separation of requestors and their interpreters. However, the
set of requests is open (and can be extended at any time without
recompiling the program). Likewise the interpreters can be extended
incrementally. One can add an interpreter for an effect without caring
what other effects are there -- unless one has some reason for caring
about other effects (e.g.,m for finalization). One may then snoop on
other effects while interpreting. Moreover, the handlers may be
scattered around program; they don't have to be all at the very top.

Crucially, unlike data types a la carte, extensible effects provide
effect encapsulation: one can not only add effects but subtract them,
by completely handling the effects. The type system ensures that all
effects must be completely handled at the end.




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

oleg-30
In reply to this post by Alejandro Serrano Mena

> The extensible-effects package seems very interesting. I would really like
> to have instances of all usual monads: Reader, Writer, State.Lazy and so on
> in the package. Maybe that's a project for the future :)

There is already a Reader and Writer, in Control.Eff.State. I guess
Ben Foppa collected them there because they all deal with aspects of
State (unlike say, non-determinism or coroutine).

I must stress that thinking of extensible-effects effects as just
another implementation of MTL is not productive. Not all effects can
be decomposed into State, Reader, etc. layers. Manly, effects should
not be decomposed into layers.

The recently discussed Logger was an excellent example. The original
poster wondered if Logger is a Writer, or a Reader + IO, or something
else. I'd suggest that the answer is that a Logger does a logging
effect. One may then think what sort of interaction with the external
world executing this logging effect should cause. The original poster
thought exactly in these terms and outlined three scenarios. With
extensible effects, one implements these scenarios directly.

It seems MTL wrought quite a round-about way of thinking about
effects. First we specify the desired interactions with the world and
then we start thinking of decomposing them into `usual monads'. Why
not to implement the specification directly, without any
decomposition?

To make an analogy, it is believed that a mathematical proof can be
traced back to ZFC axioms. Yet no mathematician (unless working
specifically on foundations) actually thinks of ZFC when doing the
proof. [The analogy is imperfect: there are effects that cannot
in principle be represented as composition of monad transformer
layers.]


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Alejandro Serrano Mena
Thanks for both the pointers and the discussion about extensible-effects. I had some time yesterday to look at the paper itself, and I found it really useful and clean.

Even though, I still think that porting more monad transformers into extensible-effects could help the latter being used more widely. Right now MTL provides Reader, Writer, State, Cont, Error, RWS; and we have packages for random numbers, or monad-supply for a supply of unique values. I would be willing to use extensible-effects if I knew that I can do all of that within the framework. I still see the possibility of having a nice weekend projects in Haskell :)

By the way, I'm also interested in knowing if extensible-effects have some relation to MonadPlus or Applicative in any way.

Thanks again for the answers! I really liked the ideas!


2013/11/28 <[hidden email]>

> The extensible-effects package seems very interesting. I would really like
> to have instances of all usual monads: Reader, Writer, State.Lazy and so on
> in the package. Maybe that's a project for the future :)

There is already a Reader and Writer, in Control.Eff.State. I guess
Ben Foppa collected them there because they all deal with aspects of
State (unlike say, non-determinism or coroutine).

I must stress that thinking of extensible-effects effects as just
another implementation of MTL is not productive. Not all effects can
be decomposed into State, Reader, etc. layers. Manly, effects should
not be decomposed into layers.

The recently discussed Logger was an excellent example. The original
poster wondered if Logger is a Writer, or a Reader + IO, or something
else. I'd suggest that the answer is that a Logger does a logging
effect. One may then think what sort of interaction with the external
world executing this logging effect should cause. The original poster
thought exactly in these terms and outlined three scenarios. With
extensible effects, one implements these scenarios directly.

It seems MTL wrought quite a round-about way of thinking about
effects. First we specify the desired interactions with the world and
then we start thinking of decomposing them into `usual monads'. Why
not to implement the specification directly, without any
decomposition?

To make an analogy, it is believed that a mathematical proof can be
traced back to ZFC axioms. Yet no mathematician (unless working
specifically on foundations) actually thinks of ZFC when doing the
proof. [The analogy is imperfect: there are effects that cannot
in principle be represented as composition of monad transformer
layers.]




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

oleg-30
In reply to this post by Nickolay Kudasov

> Could you please elaborate on the current state of the project?
> Can it be considered stable?
> Where should I look for the uses of extensible effects?

Ben Foppa has already answered most of these questions. I should add
that although there are some improvements to be made (I'm thinking of
a couple), they are either definitely or highly likely will preserve
the existing interface. So, your code will not have to change. For
example, closed type families in the upcoming GHC 7.8 will let us
implement OpenUnions better. The interface shall be preserved, only
the implementation will change.

Most of the new development is writing more examples and more and
better explanations. Recently, for example, I added committed choice
(in Prolog terms, soft-cut) to the Choice effect. I was surprised how
easy it was and how nothing had to be changed. I merely added a new
handler. So, we get another implementation of LogicT, this time in
terms of extensible effects.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Clark Gaebel-2
In reply to this post by Alejandro Serrano Mena
Reader/Writer/State are handled in extensible-effects inside Control.Eff.State. Cont is handled in Control.Eff.Coroutine (although could use better documentation, patches welcome!). RWS isn't done, but I don't see why it can't be implemented in terms of State! Error is provided by Control.Eff.Exception, and a substitute for monad-supply is provided by Control.Eff.Fresh. Random numbers are in a new package: system-random-effect.

Eff is an instance of applicative, but not MonadPlus. I don't immediately see a way to make it an instance of MonadPlus, especially since we can have an 'IO' effect.

Hope that helps!
  - Clark


On Thu, Nov 28, 2013 at 2:53 AM, Alejandro Serrano Mena <[hidden email]> wrote:
Thanks for both the pointers and the discussion about extensible-effects. I had some time yesterday to look at the paper itself, and I found it really useful and clean.

Even though, I still think that porting more monad transformers into extensible-effects could help the latter being used more widely. Right now MTL provides Reader, Writer, State, Cont, Error, RWS; and we have packages for random numbers, or monad-supply for a supply of unique values. I would be willing to use extensible-effects if I knew that I can do all of that within the framework. I still see the possibility of having a nice weekend projects in Haskell :)

By the way, I'm also interested in knowing if extensible-effects have some relation to MonadPlus or Applicative in any way.

Thanks again for the answers! I really liked the ideas!


2013/11/28 <[hidden email]>


> The extensible-effects package seems very interesting. I would really like
> to have instances of all usual monads: Reader, Writer, State.Lazy and so on
> in the package. Maybe that's a project for the future :)

There is already a Reader and Writer, in Control.Eff.State. I guess
Ben Foppa collected them there because they all deal with aspects of
State (unlike say, non-determinism or coroutine).

I must stress that thinking of extensible-effects effects as just
another implementation of MTL is not productive. Not all effects can
be decomposed into State, Reader, etc. layers. Manly, effects should
not be decomposed into layers.

The recently discussed Logger was an excellent example. The original
poster wondered if Logger is a Writer, or a Reader + IO, or something
else. I'd suggest that the answer is that a Logger does a logging
effect. One may then think what sort of interaction with the external
world executing this logging effect should cause. The original poster
thought exactly in these terms and outlined three scenarios. With
extensible effects, one implements these scenarios directly.

It seems MTL wrought quite a round-about way of thinking about
effects. First we specify the desired interactions with the world and
then we start thinking of decomposing them into `usual monads'. Why
not to implement the specification directly, without any
decomposition?

To make an analogy, it is believed that a mathematical proof can be
traced back to ZFC axioms. Yet no mathematician (unless working
specifically on foundations) actually thinks of ZFC when doing the
proof. [The analogy is imperfect: there are effects that cannot
in principle be represented as composition of monad transformer
layers.]




_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe




--
Clark.

Key ID     : 0x78099922
Fingerprint: B292 493C 51AE F3AB D016  DD04 E5E3 C36F 5534 F907

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Oliver Charles-3
In reply to this post by oleg-30
On 11/28/2013 10:30 AM, [hidden email] wrote:
> Most of the new development is writing more examples and more and
> better explanations. Recently, for example, I added committed choice
> (in Prolog terms, soft-cut) to the Choice effect. I was surprised how
> easy it was and how nothing had to be changed. I merely added a new
> handler. So, we get another implementation of LogicT, this time in
> terms of extensible effects.

This sounds very interesting - is this work available for us to look at
anywhere?

- ocharles


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (501 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Oliver Charles-3
In reply to this post by Clark Gaebel-2
On 11/28/2013 12:59 PM, Clark Gaebel wrote:
Reader/Writer/State are handled in extensible-effects inside Control.Eff.State. Cont is handled in Control.Eff.Coroutine (although could use better documentation, patches welcome!). RWS isn't done, but I don't see why it can't be implemented in terms of State! Error is provided by Control.Eff.Exception, and a substitute for monad-supply is provided by Control.Eff.Fresh. Random numbers are in a new package: system-random-effect.

Eff is an instance of applicative, but not MonadPlus. I don't immediately see a way to make it an instance of MonadPlus, especially since we can have an 'IO' effect.
And if you do want MonadPlus-like stuff, you just add in the "Choice" effect - right?

- ocharles

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (501 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

oleg-30
In reply to this post by Alejandro Serrano Mena

> By the way, I'm also interested in knowing if extensible-effects have some
> relation to MonadPlus or Applicative in any way.

The Eff monad is a genuine monad, and all monads are Applicatives. So,
extensible-effects directly relates to Applicative.

As Oliver Charles noted, the extensible-effects package provides the Choose
effect, with the operation
        choose :: Member Choose r => [a] -> Eff r a
to non-deterministically select an element from a list. It is easy to
see that Choose is as alias of MonadPlus: given choose one can
implement mplus and mzero (the latter is choose []). Conversely,
MonadPlus lets us implement Choose. The signature of choose says the
resulting computation will have the Choose effect -- and, since the
effect label |r| is left polymorphic, the computation may have an
unspecified number of other effects (including IO).

> > handler. So, we get another implementation of LogicT, this time in
> > terms of extensible effects.
>
> This sounds very interesting - is this work available for us to look at
> anywhere?

Actually yes, from the very slightly updated
        http://okmij.org/ftp/Haskell/extensible/Eff.hs
Please search for 'Soft-cut'. The implementation is so trivial that it
didn't seem worth mentioning before. The most interesting part is
        reflect :: VE a r -> Eff r a
which is the inverse of admin (aka, reify). It is gratifying that
monadic reification-reflection can be implemented with extensible-effects
_generically_, once and for all.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Heinrich Apfelmus
In reply to this post by Alejandro Serrano Mena
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Nickolay Kudasov
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



2013/11/30 Heinrich Apfelmus <[hidden email]>
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Nickolay Kudasov
​​
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 <[hidden email]>
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Heinrich Apfelmus
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/BreadthFirstParsing.hs#L47


> 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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Ben Franksen
In reply to this post by Ben Foppa
Ben Foppa wrote:

> Uploader and current maintainer of the extensible-effects package here.
> Although I'm still confused myself about the more theoretical bits of
> extensible-effects,
> I think I might be able to shed some light on it from a user's and
> maintainer's perspective.
>
> extensible-effects is currently operational, and works quite well wherever
> I use it.
> That said, it's a new package and I'd expect some shifts before it settles
> down.

Let me first say that I like the general idea very much. I just read the
paper and it all looks extremely promising. And I greatly appreciate your
effort to put it on hackage and maintain it.

It is a good thing that the library is not yet settled, though, because I
think some of the names should be re-considered. For instance, why Eff and
not Effect? Or why type Exn but corresponding functions throwError and
catchError?

(IMO such slips are okay for a paper, or a proof-of-concept implementation,
but not for a library that aspires to overthrow monad transformers.)

Cheers
Ben
--
"Make it so they have to reboot after every typo." -- Scott Adams


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: free vs. operational vs. free-operational

Ben Franksen
Ben Franksen wrote:
> Or why type Exn

(I meant to write Exc)

> but corresponding functions throwError and
> catchError?

Ah, I just saw that this inconsistency is already fixed, it's Exc
consistently in the latest version on hackage.

I guess Exc has been chosen to avoid collisions when importing the library
unqualified?

Cheers
Ben
--
"Make it so they have to reboot after every typo." -- Scott Adams


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe