Relationship between Operational, Free, and Coyoneda

comment.txt

From Edward's comment here - https://www.reddit.com/r/haskell/comments/4cfxri/relationship_between_operational_monad_and_oleg/d1hxmfr

You can view Operational f as sugar for Free (Coyoneda f).

Coyonedamakes a functor out of anything of kind * -> *. This is good and bad, depending on how you use the result. If you inspect it multiple times and do more fmap's etc, you may wind up lifting and lowering repeatedly and converting back and forth between f and Coyoneda f does require an fmap on the roundtrip.

Similarly, Free makes a monad by using any Functor worth of instructions.

These notions compose very naturally. Now your 'instructions' don't have to start as a Functor, they just get to be anything of kind * -> *.

This observation gives rise to the Operational monad.

It is technically a "free monad" as well, but you have to be careful when you say something is free, it is always free relative to what you forget. In one case you forget that something is a Monad, and remember that it is a Functor, in the other you forget even that it is a Functor and only remember * -> *.

"Reflection without Remorse" gave a more efficient free monad at least asymptotically, when you inspect the result multiple times. Sadly, the constants are pretty bad, but the asymptotic win can be huge in some situations.

Freer is just the "Reflection without Remorse" construction applied to the Operational monad, rather than the Free monad. Alternately you can think of is as just reflection without remorse but with Coyoneda f as the base functor.

From Edward's comment here - https://www.reddit.com/r/haskell/comments/4cfxri/relationship_between_operational_monad_and_oleg/d1hxmfr

You can view Operational f as sugar for Free (Coyoneda f).

Coyonedamakes a functor out of anything of kind * -> *. This is good and bad, depending on how you use the result. If you inspect it multiple times and do more fmap's etc, you may wind up lifting and lowering repeatedly and converting back and forth between f and Coyoneda f does require an fmap on the roundtrip.

Similarly, Free makes a monad by using any Functor worth of instructions.

These notions compose very naturally. Now your 'instructions' don't have to start as a Functor, they just get to be anything of kind * -> *.

This observation gives rise to the Operational monad.

It is technically a "free monad" as well, but you have to be careful when you say something is free, it is always free relative to what you forget. In one case you forget that something is a Monad, and remember that it is a Functor, in the other you forget even that it is a Functor and only remember * -> *.

"Reflection without Remorse" gave a more efficient free monad at least asymptotically, when you inspect the result multiple times. Sadly, the constants are pretty bad, but the asymptotic win can be huge in some situations.

Freer is just the "Reflection without Remorse" construction applied to the Operational monad, rather than the Free monad. Alternately you can think of is as just reflection without remorse but with Coyoneda f as the base functor.