Free monads

387 views
Skip to first unread message

etorreborre

unread,
Sep 17, 2012, 6:14:02 AM9/17/12
to scala-fu...@googlegroups.com
Not really Scala, but a great blog post explaining the Free Monad and its use to create interpreters: 

Nick Partridge

unread,
Sep 17, 2012, 5:56:41 PM9/17/12
to scala-fu...@googlegroups.com
The Free representation in scalaz differs from that article. I think I understand why, but I thought I've give it a go at explaining it here so I can be corrected.

The scalaz Free trait has 3 constructors, the first 2 line up with the article:

case class Return[S[+_]: Functor, +A](a: A) extends Free[S, A] // previously called Fill
case class Suspend[S[+_]: Functor, +A](a: S[Free[S, A]]) extends Free[S, A] // previously called Roll

But then there's this one:

case class Gosub[S[+_]: Functor, A, +B](a: Free[S, A], f: A => Free[S, B]) extends Free[S, B] // previously called FlatMap

The old name gives a good clue as to what this for: it wraps up a bind/flatMap operation into data. There's a type declaration soon after this that's a bit of a spoiler: this is about trampolining, turning usage of stack into usage of heap.

In the flatMap/bind operation for Free, instead of applying the function argument, it's wrapped up inside a Gosub:

  final def flatMap[B](f: A => Free[S, B]): Free[S, B] = this match {
    case Gosub(a, g) => Gosub(a, (x: Any) => Gosub(g(x), f))
    case a           => Gosub(a, f)
  }

No inner application of the function means that the flatMap returns without consuming stack. Instead, we choose to use up heap by allocating an object that represents the flatMap. We're now free to build Free's of mega-depth using bind without worrying about hitting the stack limit.

At least, that's how I understand it.

- Nick

--
You received this message because you are subscribed to the Google Groups "scala-functional" group.
To unsubscribe from this group, send email to scala-function...@googlegroups.com.
 
 

Tony Morris

unread,
Sep 17, 2012, 6:00:20 PM9/17/12
to scala-fu...@googlegroups.com

I didn't write scalaz.Free, but certainly that extra constructor looking like flatMap is a requirement to keep stack usage reasonable.

I'm guessing you are right.

etorreborre

unread,
Sep 17, 2012, 6:57:35 PM9/17/12
to scala-fu...@googlegroups.com
That's my understanding as well, and that's clearly indispensable to have that in Scala :-)

Tony Morris

unread,
Sep 17, 2012, 7:07:59 PM9/17/12
to scala-fu...@googlegroups.com
Related: Stackless Scala With Free Monads
http://days2012.scala-lang.org/node/451
-- 
Tony Morris
http://tmorris.net/

Debasish Ghosh

unread,
Sep 17, 2012, 11:52:11 PM9/17/12
to scala-fu...@googlegroups.com
Related ..

Sometime back I was reading free monads (inspired by the Functional Pearl - Data types a la carte) and had the confusion interpreting the semantics of *free* in the context of a free monad. Edward Kmett was kind enough to write a detailed explanation on my g+ post .. Here it goes ..  https://plus.google.com/u/0/106871002817915335660/posts/g9LASrMjeFS 

Thanks.

ivano.pagano

unread,
Sep 18, 2012, 6:48:57 AM9/18/12
to scala-fu...@googlegroups.com, tmo...@tmorris.net
I think the related scaladays2012 talk from Runar is here

Bye
Ivano
Reply all
Reply to author
Forward
0 new messages