On Mon, Nov 21, 2011 at 2:13 PM, Tim Baumgartner
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