[Haskell-cafe] Interpreter with Cont

[David Menendez]

On Mon, Nov 21, 2011 at 2:13 PM, Tim Baumgartner
<baumgartner.tim at googlemail.com> wrote:
> Free Monads. It's amazing to be confronted again with notions I learned more
> than ten years ago for groups. I have to admit that I'm probably not yet
> prepared for a deeper understanding of this, but hopefully I will return to
> it later ;-)
> Is Cont free as well? I guess so because I heard it's sometimes called the
> mother of all monads.

As I understand it, Cont is not a free monad, but there is a
connection between the ideas. Certainly, any free monad can be easily
reimplemented using Cont.

Here's how you might implement your monad using Cont,

type InteractionM a b = Cont (Interaction a b)

exit b   = Cont $ \k -> Exit b
output b = Cont $ \k -> Output b (k ())
input    = Cont $ \k -> Input k
runM m   = runCont m Exit

That's very similar to the free monad's implementation, only with the
continuation replacing Val.

exit b   = Wrap $ ExitF b
output b = Wrap $ OutputF b (Val ())
input    = Wrap $ InputF Val
runM m   = foldFree Exit roll m

The Cont-based version has essentially taken the work performed in
foldFree and distributed it to  return and (>>=). This eliminates the
intermediate data structures, resulting in a more efficient
implementation.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>