chtefi

11/23/2016 - 12:58 AM

Some notes about 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]`

)

- concat:
functor: a morphism

- map:
`F[A] -> A -> B -> F[B]`

(eg:`map([1,2])(_.toString) = ["2","3"]`

)

- map:
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]`

)

- flatMap:

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)
```