外部作用とI/O ~ FP in Scala 第13章

Jul 11, 2019 11:25 · 541 words · 3 minute read

“Scala関数型デザイン＆プログラミング ―Scalazコントリビューターによる関数型徹底ガイド”（原題: Functional Programming in Scala）“第13章外部作用とI/O”のメモ

IO

純粋関数にならない箇所、例えば IO などの作用をどのように扱うかの章。はじめの戦略として IO というデータ型を用意し、作用を次のように扱う。

"作用"をもつ処理の記述を生成（IOを生成）
"作用"を適用するための別のインタープリタで実行（IO.runを実行）

sealed trait IO[A] {
  def run: A
  def flatMap[B](f: A => IO[B]): IO[B] =
    new IO[B] {
      def run = f(self.run).run
    }
}

こうして定義された IO 型は Monad を形成できる。 flatMap, unit, run 以外の関数（Monad コンビネータ）を手に入れたということだ。

object IO extends Monad[IO] {
  def unit[A](a: => A): IO[A] = new IO[A] { def run = a }
  def flatMap[A, B](fa: IO[A])(f: A => IO[B]) = fa flatMap f
  def apply[A](a: => A): IO[A] = unit(a)
}

TailRec

この定義による IO の flatMap は再帰的に新しい IO オブジェクトを作成し、run を呼び出すので stack overflow を引き起こす。これを防ぐために flatMap の実装を、新しい IO オブジェクトを生成ではなく、f に相当する関数を引数に持つコンストラクタ FlatMap を返すようにする。さらに run が末尾再帰するようにすることで、 stack overflow を防ぐことができる。このようなテクニックをトランポリンと呼ぶ。トランポリンは入出力操作に限らないので IO という名前は適切ではない。 TailRec と名付けておく。

sealed trait TailRec[A] {
  def flatMap[B](f: A => IO[B]): IO[B] =
    FlatMap(this, f)
}

case class Return[A](a: A) extends TailRec[A]
case class Suspend[A](resume: () => A) extends TailRec[A]
case class FlatMap[A, B](sub: TailRec[A], k: A => TailRec[B]) extends TailRec[B]

@annotaion.tailrec def run[A](tr: TailRec[A]): A = tr match {
  case Return(a) => a
  case Suspend(r) => r()
  case FlatMap(x, f) => x match {
     case Return(a) => run(f(a))
     case Suspend(r) => run(f(r()))
     case FlatMap(y, g) => run(y flatMap (a => g(a) flatMap f))
  }
}

Async

run が非同期呼び出しをサポートできない。TrilRec における Suspend の引数 resume の型は Function0[A] だからだ。例えば、 run(FlatMap(Suspend(s), k)) の場合、 run(k(s())) であり、s を実行してその完了を待たなければ run に制御を戻すことができない。

そこで Function0[A] を Par[A] に変更する。これを Async と呼ぶ。これで非同期処理が可能になった。

sealed trait Async[A] {
  def flatMap[B](f: A => Async[B]): Async[B] =
    FlatMap(this, f)
}

case class Return[A](a: A) extends Async[A]
case class Suspend[A](resume: Par[A]) extends Async[A]
case class FlatMap[A,B](sub: Async[A], k: A => Async[B]) extends Async[B]

@annotation.tailrec def step[A](async: Async[A]): Async[A] = async match {
  case FlatMap(FlatMap(x, f), g) => step(x flatMap (a => f(a) flatMap g))
  case FlatMap(Return(x), f) => step(f(x))
  case _ => async
}

def run[A](async: Async[A]): Par[A] = step(async) match {
  case Return(a) => Par.unit(a)
  case Suspend(r) => r
  case FlatMap(x, f) => x match {
    case Suspend(r) => Par.flatMap(r)(a => run(f(a)))
    case _ => sys.error("Impossible, since `step` eliminates these cases")
  }
}

Free

Suspend の引数の型を抽象化する。Free と呼ぶ。Free[F, A] は F が提供する命令セットで記述されたプログラムのようなものである。

sealed trait Free[F[_], A] {
  def flatMap[B](f: A => Free[F, B]): Free[F, B] =
    FlatMap(this, f)
}

case class Return[F[_], A](a: A) extends Free[F, A]
case class Suspend[F[_], A](s: F[A]) extends Free[F, A]
case class FlatMap[F[_], A, B](s: Free[F, A], f: A => Free[F, B]) extends Free[F, B]

つまり TailRec も Async も型エイリアスとして書ける。

type TailRec[A] = Free[Function0, A]
type Async[A] = Free[Par, A]

Translate

F が Monad のとき、Free[F, A] のインタープリタは次のように書ける。

@annotation.tailrec
  def step[F[_], A](a: Free[F, A]): Free[F, A] = a match {
    case FlatMap(FlatMap(x, f), g) => step(x flatMap (a => f(a) flatMap g))
    case FlatMap(Return(x), f) => step(f(x))
    case _ => a
  }

def run[F[_], A](a: Free[F, A])(implicit F: Monad[F]): F[A] = step(a) match {
  case Return(a) => F.unit(a)
  case Suspend(r) => r
  case FlatMap(Suspend(r), f) => F.flatMap(r)(a => run(f(a)))
  case _ => sys.error("Impossible, since `step` eliminates these cases")
}

F が Monad ではないときのために、Translate という型を使って Monad を形成する型 G に変換するようにする。

trait Translate[F[_], G[_]] {
  def apply[A](f: F[A]): G[A]
}
type ~>[F[_], G[_]] = Translate[F, G]

これによって run をさらに一般化することができる。

def runFree[F[_], G[_], A](free: Free[F, A])(t: F ~> G)(implicit G: Monad[G]) =
  step(free) match {
    case Return(a) => G.unit(a)
    case Suspend(r) => t(r)
    case FlatMap(Suspend(r), f) => G.flatMap(t(r))(a => runFree(f(a))(t))
    case _ => sys.error("")
  }