読者です 読者をやめる 読者になる 読者になる

( ꒪⌓꒪) ゆるよろ日記

( ゚∀゚)o彡°オパーイ!オパーイ! ( ;゚皿゚)ノシΣ フィンギィィーーッ!!!

Freeモナド in Scala

scalaz scala 関数型言語 haskell

噂のFreeモナドScalaで写経してみた。
Freeモナドは、取り込む型SのFunctorと組み合わせて、Functorの特性に応じたモナドを得ることができるものらしい。


そろそろFreeモナドに関して一言いっとくか - fumievalの日記
Freeモナドって何なのさっ!? - capriccioso String Creating(Object something){ return My.Expression(something); }
Haskell for all: Why free monads matter
stackless scala with free monad
独習 Scalaz: 18日目 | eed3si9n


( ゚д゚) 「ナンデ!?モナドナンデ!?」


モナドセブンセンシズならFreeモナドはエイトセンシズくらいなのでかなり小宇宙を高めないと理解が追いつかないので、まずは写経してみた。

Freeモナドの定義

そのままScalaに移植するにあたって、型SはFunctorである必要があるので、Functor型クラスを用意し、flatMapにimplicit parameterでFunctor型クラスのインスタンスを注入する形式にする。

// type class: Functor
trait Functor[F[_]] {
  def map[A, B](m: F[A])(f: A => B): F[B]
}

// data Free f a = Pure a | Free (f (Free f a))
// instance Functor f => Monad (Free f) where
//     return = Pure
//     Pure a >>= k = k a
//     Free fm >>= k = Free (fmap (>>=k) fm) f a))
//
sealed trait FreeM[S[+_], +A] {
  def flatMap[B](f: A => FreeM[S, B])(implicit s: Functor[S]): FreeM[S, B]
  def map[B](f: A => B)(implicit s: Functor[S]): FreeM[S, B] = flatMap(a => Pure(f(a)))
}

case class Pure[S[+_], +A](a: A) extends FreeM[S, A] {
  def flatMap[B](f: A => FreeM[S, B])(implicit s: Functor[S]): FreeM[S, B] = f(a)
}

case class Free[S[+_], +A](k: S[FreeM[S, A]]) extends FreeM[S, A]{
  def flatMap[B](f: A => FreeM[S, B])(implicit s: Functor[S]): FreeM[S, B] = Free(s.map(k)(_.flatMap(f)))
}

haskellのをそのまま移植しただけで、特に難しいことはやってない。

サンプルのCharIOを写経する

そろそろFreeモナドに関して一言いっとくか - fumievalの日記 のCharIOを写経してみる。Haskell版ではIO[Char]になるが、ScalaにはIOモナド無いのでそのままCharでやる。


まずは、CharIO型の定義。これはそのまま。

// data CharIO a = GetCh (Char -> a) | PutCh Char a
sealed trait CharIO[+A]
case class GetCh[+A](f:Char => A) extends CharIO[A]
case class PutCh[+A](c:Char, a:A) extends CharIO[A]


つぎに、CharIOのFunctorインスタンスを定義する。

// instance Functor CharIO where
//    fmap f (GetCh g) = GetCh (f . g)
//    fmap f (PutCh c x) = PutCh c (f x)
implicit val charIOFunctor =
  new Functor[CharIO] {
    def map[A, B](a: CharIO[A])(f: A => B): CharIO[B] = a match {
      case GetCh(g)    => GetCh(f compose g)
      case PutCh(c, x) => PutCh(c, f(x))
    }
  }

これもそのまま。


続いて、Free[CharIO, Char]を返すユーティリティ関数を定義する。

// getCh :: Free CharIO Char
// getCh = Free $ GetCh $ \ch -> Pure ch
//
// putCh :: Char -> Free CharIO ()
// putCh ch = Free $ PutCh ch (Pure ())
//
def getCh:FreeM[CharIO, Char] = Free(GetCh({ch => Pure(ch)}))
def putCh(ch:Char):FreeM[CharIO, Unit] = Free(PutCh(ch, Pure(())))

同じっすね。


では、サンプルどおりに、doの中でこれらの関数を用いてFree[CharIO, Char]を組み合わせてみる。

// mapM_
def mapFreeM[S[+_]:Functor, A](f:A => FreeM[S,Unit], s:Seq[A]):FreeM[S,Unit] = s.toList match {
  case x::xs => xs.foldLeft(f(x)){(m:FreeM[S,Unit],c:A) => m.flatMap{unit => f(c)} }
  case Nil => Pure(())
}

//  ex0 = do
//     mapM_ putCh "Hello, Haskeller! Please input a character:"
//     ch <- getCh
//     mapM_ putCh "The ordinal of the character is:"
//     mapM_ putCh (show (ord ch))
//     mapM_ putCh ".\n Thank you!\n" }

val io:FreeM[CharIO, Unit] = for{
    _  <- mapFreeM(putCh, "Hello, Scala Programmer! Please input a character:")
    ch <- getCh
    _  <- mapFreeM(putCh, "The ordinal of the character is:")
    _  <- mapFreeM(putCh, ch.toInt.toString)
    _  <- mapFreeM(putCh, ".\n Thank you!\n")
  } yield ()

ScalaにはmapM_がないので、代わりにSeq[A]にそれぞれ(f: A => FreeM[S, Unit])を適用しつつflatMapでたたみ込むようmapFreeMを用意した。
で、Scalaにおけるモナド糖衣構文はforなので、これにFreeモナドを与えてみる。 "for{_ <- m ... } yield ()" って記法ェ……。


これで、Free[CharIO, Char]を結合させたもio:FreeM[CharIO, Unit]が得られた。これは、いわばSのFunctorによってflatMapで合成されたCharIOのLinkedListと言えなくもない。
あとは、このio:FreeM[CharIO, Unit]を渡り歩きながら処理を行うインタプリター関数を定義すればいいわけだ。

// runStdIO :: Free CharIO a -> IO a
// runStdIO (Pure a) = return a
// runStdIO (Free (GetCh f)) = getChar >>= \ch -> runStdIO (f ch)
// runStdIO (Free (PutCh ch cont)) = putChar ch >> runStdIO cont
def runCharIO(free:FreeM[CharIO, Unit]):Unit = free match { 
  case Pure(a)               => a
  case Free(GetCh(f))        => runCharIO(f(readChar()))
  case Free(PutCh(ch, cont)) => print(ch);runCharIO(cont)
}

実行してみる。

scala> runCharIO(io)
Hello, Scala Programmer! Please input a character:The ordinal of the character is:97.
 Thank you!

Stackless Freeモナド

ねこはる先生の資料どおりに、Stackless化したものが以下。FreeM#flatMapで渡されたfをその場ですぐに評価してしまうと、fが再帰的にrunCharIOなのでインタプリター関数を呼び出すようになっているとスタックを食い尽くしてしまう。

Stacklessにするためには、FreeMの構築しにFlatMap型を追加して、Free#flatMapでは渡されたfをFlatMap型で包んでおいて評価を遅延させ、resumeでFreeMを1ステップづつ取り出していくことで対処している、という理解。