Freeモナド in Scala
噂の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!