scalaz - Free

## Free

今回試したバージョンは[7.1のFree](https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/Free.scala)だ。

Freeとは何だろうか。

> Functorと組み合わせて様々な挙動を実現できるモナド。
> [Freeモナドって何なのさっ！？](http://d.hatena.ne.jp/its_out_of_tune/20121111/1352632815)

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

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

この2点だ。

### 使ってみる

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

まずは型の定義から。

```scala
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を持つ。

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

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

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

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

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

そこでFreeだ。

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

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

```scala
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を実行するインタープリタを定義する。

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

```scala
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に包む関数を書いておこう。

```scala
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文で組み合わせるんだ。

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

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

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

### 実行してみよう

```scala
f2.foldMap(interp)

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

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

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

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

試しにmockにしてみる。

```scala
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
  }
}
```

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


## さらに詳しく

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

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

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

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

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

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

```scala
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
scala> pointInt(1).map(_ + 1)
//res39: scalaz.Free[scalaz.Scalaz.Id,Int] = Gosub()
```

resumeで実行してみる。

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

1+1されてる。

Suspendがあると?

```scala
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
scala> .fold(_.resume, identity)
res42: Any = \/-(3)
```

お、続けて実行できた。

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

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

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

### トランポリン

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

> トランポリンを使えば、どんなプログラムでもスタックを使わないものに変換することができる。
> [独習 Scalaz — Stackless Scala with Free Monads](http://eed3si9n.com/learning-scalaz/ja/Stackless+Scala+with+Free+Monads.html)

型を見ると確かにFreeだ。これは[Free.scalaの中](https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/Free.scala#L34)に定義されている。

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

試しにクイックソートをスタックレスで書いてみよう。[参考](https://github.com/scalaz/scalaz/blob/series/7.2.x/example/src/main/scala/scalaz/example/TrampolineUsage.scala)

```scala
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段階に分けて記述していきます。

定義をみてみよう。

```scala
/** 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だ。

それぞれ以下の関数で作れるようだ。[ソース](https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/Free.scala#L359-L364)

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

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

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

```scala
// 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に入れて返す。[ソース](https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/Free.scala#L185)

```scala
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を渡して実行。[ソース](https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/Free.scala#L195)

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

```scala
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を渡して実行。[ソース](https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/Free.scala#L207)

```scala
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を渡して実行。[ソース](https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/Free.scala#L217)

```scala
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を使った型もあった。

```scala
/** 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を使えば定義しなくてもいいんだ。

```scala
// 定義して
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の他の関数を見てみよう。

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

```scala
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を実行する。[ソース](https://github.com/scalaz/scalaz/blob/series/7.1.x/core/src/main/scala/scalaz/Free.scala#L69)

結果は`scalaz.\/`で返る。

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

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

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

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

```scala
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を返して変更できるようだ。

```scala
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に適用する。

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

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

```scala
(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のときに適用する。

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

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

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

```scala
(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のときには第二引数の。

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

```scala
(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だ。

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

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

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

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

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