Free Monads

• Recursive data structure

• monoid: a "set" with 2 operations

  • concat: A -> A -> A (eg: "a"+"b"="ab", 1+2=3, [1,2]++[3]=[1,2,3])
  • id: A
  • associative, and it exists an identity element (eg: ""+"a"="a", 0+1=1, []++[1,2]=[1,2])

• functor: a morphism

  • map: F[A] -> A -> B -> F[B] (eg: map([1,2])(_.toString) = ["2","3"])

• monad: a "computation builder"

  • flatMap: M[A] -> A -> M[B] -> M[B] (eg: flatMap([1,2])(x => [x,x]) = [1,1,2,2]
  • pure: A -> M[A] (eg: pure(1) = [1])

Moreoever, a Free monad is:

• Free from interpretation
• FREE: You don't lose ANY input data
• not NOT FREE: not like 5+4=9. From 9, you can't go back. The Free attitude don't lose the source, it stacks computations.
• It defers the side-effects.
• The computation is only evaluated at the end, when we run the monoid.

eg: ListMonoid: concat: a++b, id: []

It doesn't use stack when running computation, it uses the heap ("stack safety"). It uses TCE, tail call elimination strategy (otherwise, that would be useless). That replaces recursion with simple "jumps" in the code (think loop). This is called trampolining ("trading" stack for heap).

Note that a trampoline is a Free monad with a simple Function0. (ie: () -> A) Free is simply a generalization of a trampoline.

A Free monad has 2 subtypes:

• Suspend (or Join, or More): the computation is not done, return the next step
  • "Suspend" means the computation is currently suspended at this step
• Return (or Point, or Done): the computation is done, return the result

sealed trait Trampoline[+A] {
  final/* eliminate tail call*/ def runT: A =
    this match {
      case More(k) => k().runT
      case Done(v) => v
    }
}
case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]
case class Done[+A](result: A) extends Trampoline[A]

  def continue(t: (Int, Double)): Trampoline[(Int, Double)] = {
    println(s"iteration ${t._1} (previous ${t._2})")
    val r = math.random()
    if (r > 0.999999)
      Done((t._1 + 1, r))
    else
      continue((t._1 + 1, r))
  }

  println(More(() => continue((1, math.random))).runT)