Free Monad

NewCircle @TheNewCircle

Video: Dead-Simple Dependency Injection in #Scala with @runarorama from the 2012 #NEScala Symposium - http://t.co/ULfIcsJM

mergeconflict @mergeconflict

@runarorama i think i missed an important point somewhere in your #nescala talk: does using Free[_, _] have an advantage over Reader[_, _]?

mergeconflict @mergeconflict

@runarorama ... and doesn't Reader[KVS, _] fit the description of "a little program that describes what we might do to a KVS if we had one"?

mergeconflict @mergeconflict

@runarorama ... or do you just use them in totally different situations?

Rúnar @runarorama

@mergeconflict Yeah, but such a program is totally opaque. Note that Free lets us pass in an immutable map as the store.

Rúnar @runarorama

@mergeconflict Same for IO and State--the action is opaque. With a free monad, the interpreter can reason about what the program does.

mergeconflict @mergeconflict

@runarorama i can see that Free[_,_] turns the program inside-out, s.t. the impl of KVS here is externalized, but don't see why it's useful

mergeconflict @mergeconflict

@runarorama i.e. it was some effort to make our "language" so we may vary its interpreter, but why not State[KVS, _] and vary the KVS impl?

mergeconflict @mergeconflict

@runarorama btw, please reply in haiku form. 140 characters is not sufficiently limiting.

Rúnar @runarorama

@mergeconflict 1: A sufficiently long program in State will overflow the stack, whereas Free can be TCOed via a codensity monad.

Rúnar @runarorama

@mergeconflict 2: Free monads compose in parallel. Free[F, A] and Free[G, A] compose into Free[({type f[x]=Either[F[A],G[A]]})#f, A]

Rúnar @runarorama

@mergeconflict Ask the same of any free monad. Why are Option and Either useful? How is Iteratee useful? Comes down to ADTs vs interfaces.

mergeconflict @mergeconflict

@runarorama then i think you undersold Free (pun intended) in your preso. We get const stack like Reader and immutability like State, yeah?

mergeconflict @mergeconflict

@runarorama and it looks like Free[KVS, _] specifically (with get, put, etc.) is a nice replacement for State if i understand correctly?

mergeconflict @mergeconflict

@runarorama so you're saying Option is a free monad? Meaning it can be expressed as a Free[Something, _]? What's that something?

Rúnar @runarorama

@mergeconflict Yeah, you get constant stack since running the free monad is tail-recursive.

Rúnar @runarorama

@mergeconflict Free[Get * Put, A] is a nice replacement for State, yes.

Rúnar @runarorama

@mergeconflict type Trivial[A] = Unit; type Option[A] = Free[Trivial, A]