自由モナドの概念は interpreter パターンを超えたものだ。 恐らくこれからも新しい自由モナドの応用範囲が見つかっていくと思う。
Rúnar (@runarorama) さんは Scala で Free を使うことを広めた第一人者だ。
6日目に扱った Dead-Simple Dependency Injection というトークでは
key-value ストアを実装するためのミニ言語を Free を用いて実装していた。
同年の Scala Days 2012 では Rúnar さんは
Stackless Scala With Free Monads というトークをやっている。
ペーパーを読む前にトークを観ておくことをお勧めするけど、ペーパーの方が引用しやすいので
Stackless Scala With Free Monads もリンクしておく。
Rúnar さんはまず State モナドの実装を使ってリストに添字を zip するコードから始める。 これはリストがスタックの限界よりも大きいと、スタックを吹っ飛ばす。 続いてプログラム全体を一つのループで回すトランポリンというものを紹介している。
sealed trait Trampoline [+ A] {
final 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]
上記のコードでは Function0 の k は次のステップのための thunk となっている。
これを State モナドを使った使用例に拡張するため、flatMap を FlatMap というデータ構造に具現化している:
case class FlatMap [A,+B](
sub: Trampoline [A],
k: A => Trampoline[B]) extends Trampoline[B]
続いて、Trampoline は実は Function0 の Free モナドであることが明かされる。
Cats では以下のように定義されている:
type Trampoline[A] = Free[Function0, A]
トランポリンを使えば、どんなプログラムでもスタックを使わないものに変換することができる。
Trampoine object はトランポリン化するのに役立つ関数を定義する:
object Trampoline {
def done[A](a: A): Trampoline[A] =
Free.Pure[Function0,A](a)
def suspend[A](a: => Trampoline[A]): Trampoline[A] =
Free.Suspend[Function0, A](() => a)
def delay[A](a: => A): Trampoline[A] =
suspend(done(a))
}
トークに出てきた even と odd を実装してみよう:
import cats._, cats.syntax.all._, cats.free.{ Free, Trampoline }
import Trampoline._
def even[A](ns: List[A]): Trampoline[Boolean] =
ns match {
case Nil => done(true)
case x :: xs => defer(odd(xs))
}
def odd[A](ns: List[A]): Trampoline[Boolean] =
ns match {
case Nil => done(false)
case x :: xs => defer(even(xs))
}
even(List(1, 2, 3)).run
// res0: Boolean = false
even((0 to 3000).toList).run
// res1: Boolean = false
上を実装してるうちにまた SI-7139 に引っかかったので、Cats を少し改良する必要があった。 #322
さらに Rúnar さんは便利な Free モナドを作れるいくつかのデータ型を紹介する:
type Pair[+A] = (A, A)
type BinTree[+A] = Free[Pair, A]
type Tree[+A] = Free[List, A]
type FreeMonoid[+A] = Free[({type λ[+α] = (A,α)})#λ, Unit]
type Trivial[+A] = Unit
type Option[+A] = Free[Trivial, A]
モナドを使った Iteratee まであるみたいだ。最後に自由モナドを以下のようにまとめている:
- データが末端に来る全ての再帰データ型に使えるモデル
- 自由モナドは変数が末端にある式木で、flatMap は変数の置換にあたる。
Free を使って「リスト」を定義してみよう。
type FreeMonoid[A] = Free[(A, +*), Unit]
def cons[A](a: A): FreeMonoid[A] =
Free.liftF[(A, +*), Unit]((a, ()))
val x = cons(1)
// x: FreeMonoid[Int] = Suspend(a = (1, ()))
val xs = cons(1) flatMap { _ => cons(2) }
// xs: Free[(Int, β0), Unit] = FlatMapped(
// c = Suspend(a = (1, ())),
// f = <function1>
// )
この結果を処理する一例として標準の List に変換してみる:
implicit def tuple2Functor[A]: Functor[(A, *)] =
new Functor[(A, *)] {
def map[B, C](fa: (A, B))(f: B => C) =
(fa._1, f(fa._2))
}
def toList[A](list: FreeMonoid[A]): List[A] =
list.fold(
{ _ => Nil },
{ case (x: A @unchecked, xs: FreeMonoid[A]) => x :: toList(xs) })
toList(xs)
// res2: List[Int] = List(1, 2)