Stackless Scala with Free Monads 

自由モナドの概念は 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]

上記のコードでは Function0k は次のステップのための thunk となっている。

これを State モナドを使った使用例に拡張するため、flatMapFlatMap というデータ構造に具現化している:

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

トークに出てきた evenodd を実装してみよう:

scala> import cats._, cats.data._, cats.implicits._, cats.free.{ Free, Trampoline }
import cats._
import cats.data._
import cats.implicits._
import cats.free.{Free, Trampoline}

scala> import Trampoline._
import Trampoline._

scala> :paste
// Entering paste mode (ctrl-D to finish)
def even[A](ns: List[A]): Trampoline[Boolean] =
  ns match {
    case Nil => done(true)
    case x :: xs => suspend(odd(xs))
  }
def odd[A](ns: List[A]): Trampoline[Boolean] =
  ns match {
    case Nil => done(false)
    case x :: xs => suspend(even(xs))
  }

// Exiting paste mode, now interpreting.

even: [A](ns: List[A])cats.free.Trampoline[Boolean]
odd: [A](ns: List[A])cats.free.Trampoline[Boolean]

scala> even(List(1, 2, 3)).run
res0: Boolean = false

scala> 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 を用いた自由モノイド 

Free を使って「リスト」を定義してみよう。

scala> type FreeMonoid[A] = Free[(A, +?), Unit]
defined type alias FreeMonoid

scala> def cons[A](a: A): FreeMonoid[A] =
         Free.liftF[(A, +?), Unit]((a, ()))
cons: [A](a: A)FreeMonoid[A]

scala> val x = cons(1)
x: FreeMonoid[Int] = Free(...)

scala> val xs = cons(1) flatMap {_ => cons(2)}
xs: cats.free.Free[[+β](Int, β),Unit] = Free(...)

この結果を処理する一例として標準の List に変換してみる:

scala> implicit def tuple2Functor[A]: Functor[(A, ?)] =
         new Functor[(A, ?)] {
           def map[B, C](fa: (A, B))(f: B => C) =
             (fa._1, f(fa._2))
         }
tuple2Functor: [A]=> cats.Functor[[β](A, β)]

scala> def toList[A](list: FreeMonoid[A]): List[A] =
         list.fold(
           { _ => Nil },
           { case (x: A @unchecked, xs: FreeMonoid[A]) => x :: toList(xs) })
toList: [A](list: FreeMonoid[A])List[A]

scala> toList(xs)
res2: List[Int] = List(1, 2)

Contents