scalaz - Free

Free

今回試したバージョンは7.1のFreeだ。

Freeとは何だろうか。

Functorと組み合わせて様々な挙動を実現できるモナド。
Freeモナドって何なのさっ！？

Freeの説明は探せば結構出てくるが、どの説明も共通しているのが、

1. 独自のデータ型にFunctorを定義する。
2. Freeを実行するインタープリタを定義する。

この2点だ。

使ってみる

意味が分からないと思うので、実際に使ってみよう。

まずは型の定義から。

trait Command[+A]
case class Cd[A](path: String, next: A) extends Command[A]
case class Ls[A](next: A) extends Command[A]
case class Done() extends Command[Nothing]

コマンドをイメージしてみた。コマンドを続けて打てるように次のコマンドnextを持つ。

Cd("/", Ls(Done()))
// Cd[Ls[Done]]

次のコマンドを持ってるので再帰的に何かできそうだが、

Cd("/", Ls(Cd("/tmp", Ls(Done()))))
// Cd[Ls[Cd[Ls[Done]]]]

ネストいっぱいになってやばい。

まだ型だけだが、これでは実際に処理を書くのが難しそうだ。

そこでFreeだ。

1. 独自のデータ型にFunctorを定義する。

最初に言ったけど、FreeはFunctorを定義する必要がある。

implicit val cf = new Functor[Command] {
  def map[A, B](c: Command[A])(f: A => B): Command[B] = c match {
    case Cd(path, next) => Cd(path, f(next))
    case Ls(next) => Ls(f(next))
    case Done() => Done()
  }
}

単純に持ってるデータをA => Bに返るだけだ。

2. Freeを実行するインタープリタを定義する。

次に、それぞれの型ごとに具体的な処理を書く。

val interp = new (Command ~> Id) {
  import scala.sys.process._
  def apply[A](a: Command[A]): A = a match {
    case Cd(path, next) =>
      val cmd = s"cd $path"
      cmd.!! // !!でコマンド実行
      println(cmd)
      next
    case Ls(next) =>
      println("ls".!!)
      next
  }
}

(実際にcdは移動できないけど雰囲気だけ)

処理の流れを書く

定義した処理を、組み合わせてみよう。

まず分かりやすいようにFreeに包む関数を書いておこう。

def cd(path: String): Free[Command, Unit] = Free.liftF[Command, Unit](Cd(path, Done()))
def ls: Free[Command, Unit] = Free.liftF[Command, Unit](Ls(Done()))

for文で組み合わせるんだ。

val f1: Free[Command, Unit] = for {
  _ <- cd("/")
  _ <- ls
  _ <- cd("/usr/bin")
  _ <- ls
} yield ()

処理をつなげても書けるんだ。

val f2: Free[Command, Unit] = for {
  _ <- f1 // ←
  _ <- cd("/tmp")
  _ <- ls
} yield ()

実行してみよう

f2.foldMap(interp)

// cd /
// a.txt
// 
// cd /usr/bin
// a.txt
//
// cd /tmp
// a.txt

とりあえず動いたようだ。

インタープリタを切り替えてみよう

インタープリタに具体的な処理が書いてあるので、これを切り替えるだけで色々できそうだ。新しいデザインパターンみたいだ。

試しにmockにしてみる。

val interpMock = new (Command ~> Id) {
  def apply[A](a: Command[A]): A = a match {
    case Cd(path, next) =>
      println(s"cd $path")
      next
    case Ls(next) =>
      println("ls")
      next
  }
}

f2.foldMap(interpMock)
// cd /
// ls
// cd /usr/bin
// ls
// cd /tmp
// ls

例が微妙だったが、雰囲気だけ..。

他のFreeの例を載せておこう。

• http://d.hatena.ne.jp/xuwei/20140618/1403054751#20140618f3
• http://timperrett.com/2013/11/21/free-monads-part-1/
• http://d.hatena.ne.jp/its_out_of_tune/20121111/1352632815

さらに詳しく

使い方が大体分かったところで、型をみていく。

object Free extends FreeInstances with FreeFunctions {

  /** Return from the computation with the given value. */
  private[scalaz] case class Return[S[_], A](a: A) extends Free[S, A]

  /** Suspend the computation with the given suspension. */
  private[scalaz] case class Suspend[S[_], A](a: S[Free[S, A]]) extends Free[S, A]

  /** Call a subroutine and continue with the given function. */
  private sealed abstract case class Gosub[S[_], B]() extends Free[S, B] {
    type C
    val a: () => Free[S, C]
    val f: C => Free[S, B]
  }

Freeは、ReturnとSuspendとGosubを主に使っているようだ。

Returnを作るにはpointを使う。(もしくはpure)

Free.point[List, Int](1)
// Free[List,Int] = Return(1)

Suspendを作るにはsuspendを使う。もしくはliftFが便利だ。

Free.suspend(Free.point[List, Int](1))
// Free[List,Int] = Suspend(List(Return(1)))

Free.liftF(List(1))
// Free[List,Int] = Suspend(List(Return(1)))

長いで関数にしておこう。

val pointInt: Int => Free[Id, Int] = Free.point[Id, Int](_)
val suspendInt: Int => Free[Id, Int] = n => Free.suspend[Id, Int](pointInt(n))

scala> pointInt(1)
//res37: scalaz.Free[scalaz.Scalaz.Id,Int] = Return(1)

scala> suspendInt(1)
//res38: scalaz.Free[scalaz.Scalaz.Id,Int] = Suspend(Return(1))

Gosubは、処理を続けるものなのでmapやflatMapで作られる。

scala> pointInt(1).map(_ + 1)
//res39: scalaz.Free[scalaz.Scalaz.Id,Int] = Gosub()

resumeで実行してみる。

scala> .resume
//res40: scalaz.\/[scalaz.Scalaz.Id[scalaz.Free[scalaz.Scalaz.Id,Int]],Int] = \/-(2)

1+1されてる。

Suspendがあると?

scala> pointInt(1).map(_ + 1).flatMap(suspendInt).map(_ + 1).resume
//res41: scalaz.\/[scalaz.Scalaz.Id[scalaz.Free[scalaz.Scalaz.Id,Int]],Int] = -\/(Gosub())

残りの処理がscalaz.-\/に入るようだ。続けて実行してみよう。

scala> .fold(_.resume, identity)
res42: Any = \/-(3)

お、続けて実行できた。

一時停止したり、処理を続けたりできるので何か使えそう。

独自の型以外にも便利に使えそうだ。

次は今のを使った型を見てみよう。

トランポリン

Freeを使った型にTrampolineというものがある。

トランポリンを使えば、どんなプログラムでもスタックを使わないものに変換することができる。
独習 Scalaz — Stackless Scala with Free Monads

型を見ると確かにFreeだ。これはFree.scalaの中に定義されている。

type Trampoline[A] = Free[Function0, A]

試しにクイックソートをスタックレスで書いてみよう。参考

import Trampoline.{done, suspend}

def qsort[T: Order](xs: List[T]): Free.Trampoline[List[T]] = {
  println("do")
  val result: Free.Trampoline[List[T]] = xs match {
    case Nil => done(Nil)
    case y :: ys => suspend {
      for {
        l <- qsort(ys filter (_ < y))
        r <- qsort(ys filter (y < _))
      } yield l ::: (y :: (ys filter (_ == y))) ::: r
    }
  }
  println("done")
  result
}
qsort(3 :: 1 :: 2 :: Nil).run

// scala> qsort(3 :: 1 :: 2 :: Nil).run
// do
// done
// do
// done
// do
// done
// do
// done
// do
// done
// do
// done
// do
// done
// res3: List[Int] = List(1, 2, 3)

再帰だったらdoとdoneが交互に呼ばれることはないはずだ。

Source | Sink

Freeを使った型にSourceとSinkというのがTrampolineの定義の下にあった。

これはHaskellでいうConduitが元になってるんだと思う。 (xuwei_kさんにコメントいただきましたー)

• http://melpon.org/yesodbookjp/conduit
• http://qiita.com/siphilia_rn/items/f3d8d83496a8eab65274

Conduitはストリームデータを処理する為のライブラリです。
ストリームデータ処理の流れを「データの取得」「データの加工」「最終処理」の3段階に分けて記述していきます。

定義をみてみよう。

/** A computation that produces values of type `A`, eventually resulting in a value of type `B`. */
  type Source[A, B] = Free[({type f[x] = (A, x)})#f, B]

  /** A computation that accepts values of type `A`, eventually resulting in a value of type `B`.
    * Note the similarity to an [[scalaz.iteratee.Iteratee]].
    */
  type Sink[A, B] = Free[({type f[x] = (=> A) => x})#f, B]

うん。Freeだ。

それぞれ以下の関数で作れるようだ。ソース

Free.produce(1)
//Free.Source[Int,Unit] = Suspend((1,Return(())))

Free.await[Int]
//Free.Sink[Int,Int] = Suspend(<function1>)

試しにListをsumしてみよう。

// Listを受け取るsource
val source = Free.produce(1 to 10 toList)

// sumするsink
val sink = Free.await[List[Int]].map(_.sum)

// 実行する
sink drain source
// (Int, Unit) = (55,())

何かと処理を分離できそうだ。

他の関数も見てみよう。

collect: Sourceのデータを集める。Returnになるまで値をListに入れて返す。ソース

val source = for { _ <- Free.produce(1); _ <- Free.produce(2) } yield 3
// Free[[x](Int, x),Int] = Gosub()
// Suspend(
//   (1, Suspend(
//     (2, Return(3), ..

source.collect[Int]
// (Vector[Int], Int) = (Vector(1, 2),3)

drive: SourceにSinkを渡して実行。ソース

driveはSink[Option[E], B]を受け取るようだ。

val source = for { _ <- Free.produce(1); _ <- Free.produce(2) } yield 3
// Free[[x](Int, x),Int] = Gosub()

val sink = for { aOpt <- Free.await[Option[Int]]; bOpt <- Free.await[Option[Int]] } yield aOpt |+| bOpt
// Free[[x](=> Option[Int]) => x,Option[Int]] = Gosub()

source drive sink
// (Int, Option[Int]) = (3,Some(3))
// (Sourceの最後の値, Sinkが計算した値)

feed: SinkにStreamを渡して実行。ソース

val sink = for { a <- Free.await[Int]; b <- Free.await[Int] } yield a + b
// Free[[x](=> Int) => x,Int] = Gosub()

sink feed Stream(100, 200)
// 300

drain: SinkにSourceを渡して実行。ソース

val source = for { a <- Free.produce(1); b <- Free.produce(2) } yield 3

val sink = for { a <- Free.await[Int]; b <- Free.await[Int] } yield a * b

sink drain source
// (Int, Int) = (2,3)
// (Sourceの最後の値, Sinkが計算した値)

いい例が書けたら追加したい。

FreeC

Coyonedaを使った型もあった。

/** A free monad over the free functor generated by `S` */
type FreeC[S[_], A] = Free[({type f[x] = Coyoneda[S, x]})#f, A]

ただのデータ型からFunctorを生み出せる
http://d.hatena.ne.jp/its_out_of_tune/20130601/1370109743

ものらしい。

なので最初にFunctorを定義していたが、FreeCを使えば定義しなくてもいいんだ。

// 定義して
def cd(path: String): Free.FreeC[Command, Done] = Free.liftFC(Cd(path, Done()))
def ls: Free.FreeC[Command, Done] = Free.liftFC(Ls(Done()))

// 処理の流れ書いて
val fc = for { _ <- cd("/"); _ <- ls } yield ()

// 実行する
Free.runFC(fc)(interpMock)
// cd /
// ls

Functor定義しなくても実行できた。

Freeを使って定義された型は以上だ。

他のインスタンスの関数

Freeの他の関数を見てみよう。

さっきも使ったが、確認用に便利な関数も定義しておこう。

val pointInt: Int => Free[Id, Int] = Free.point[Id, Int](_)
val suspendInt: Int => Free[Id, Int] = n => Free.suspend[Id, Int](pointInt(n))

resume: ReturnかSuspendに当たるまでFreeを実行する。ソース

結果はscalaz.\/で返る。

pointInt(1).map(_ + 1).resume
// \/-(2)

Suspendがあるとそこで止まる。さらにresumeして進めてみた。

for { x <- pointInt(1); y <- suspendInt(x) } yield x + y
.resume
// -\/(Gosub())
.fold(_.resume, identity)
// \/-(2)

mapSuspension: Suspendの場合、Free[S, A]をFree[G, A]に変換できるものだ。

pointInt(1).mapSuspension {
  new (Id ~> Option) { def apply[A](fa: Id[A]): Option[A] = fa |> some }
}
//Free[Option,Int] = Return(1)

mapFirstSuspension: これは最初に見つかったSuspendだけ適用するみたいだ。

flatMapSuspension: さっきのflatMap版だ。

これは S ~> Free[G, _] のようにGを持ったFreeを返して変更できるようだ。

pointInt(1).flatMapSuspension[Option] {
  new (Id ~> ({type λ[a]=Free[Option, a]})#λ) {
    def apply[A](fa: Id[A]): Free[Option, A] = Free.point[Option, A](fa)
  }
}
// Free[Option,Int] = Return(1)

bounce: S[Free[S, A]] => Free[S, A] を受け取り、最初のSuspendに適用する。

(pointInt(1) >>= suspendInt).bounce {
  free: Id[Free[Id, Int]] => free.map(_ - 1)
}
//Gosub()
//.resume \/-(0)

go: bounceの全部版。Free実行して、Suspendには渡した関数を適用。

(pointInt(1) >>= suspendInt >>= suspendInt >>= pointInt).go {
  free: Id[Free[Id, Int]] => free.map(_ - 1)
}
// -1

runM: S[Free[S,A]] => M[[Free[M,A]] にする関数を渡して、Suspendのときに適用する。

(pointInt(1) >>= suspendInt).runM {
  free: Id[Free[Id, Int]] => Option(free.map(_ + 1))
}
// Some(2)

foldMap: Suspendの場合、F ~> G にする。

これは最初の例でインタープリタを渡すところで使ったやつだ。

(pointInt(1) >>= suspendInt).foldMap {
  new (Id ~> Option) {
    def apply[A](fa: Id[A]): Option[A] = fa.some
  }
}
// Some(1)

foldRight: resumeしてrightの時に第一引数のnatural transformationsが与えられて、leftのときには第二引数の。

\/-と-\/で変換する処理が分けて渡せるので、何か使えそう。

(pointInt(100) >>= { i: Int => suspendInt(i * 3) } >>= { i: Int => suspendInt(i + 1) })
  .foldRight(
    new (Id ~> Option) {
      def apply[A](fa: Id[A]): Option[A] = fa.some
    })(
    new (({type λ[a]=Id[Option[a]]})#λ ~> Option) {
      def apply[A](fa: Id[Option[A]]): Option[A] = fa
    }
  )
// Some(301)

foldRun: freeのfoldLeftだ。

何かと使えそうな予感だ。

(pointInt(100) >>= { i: Int => suspendInt(i * 3) } >>= { i: Int => suspendInt(i + 1) })
  .foldRun("") { case (s, free) => (s + "!", free) }
// (String, Int) = (!!,301)

いろんな関数があるのが分かった。

Freeは色々と便利そうではあるものの、使いどころが難しそうだ。良い使用例があったらぜひ教えて欲しい。

まだいくつか残っているが、疲れたので続きはまた今度。