Scalaz で Writer モナド

今回は、ログを追記する Writer モナドを Scalaz で使ってみます。

• Scalaz 7.0.0-M3
• sbt 0.12.0

サンプルソースは http://github.com/fits/try_samples/tree/master/blog/20120917/

使用した sbt 用ビルドファイルは以下です。

build.sbt

scalaVersion := "2.10.0-M7"

libraryDependencies += "org.scalaz" % "scalaz-core" % "7.0.0-M3" cross CrossVersion.full

単純な Writer モナド

まずは、単純な Writer モナドのサンプルです。

WriterT.writer に (ログ, 値) のタプルを渡して Writer モナドを生成します。

Writer モナドを返す関数（下記の logNum や logNumList）を >>= で繋げばログが追記されていきます。*1

下記サンプルではログ部分に String と List をそれぞれ使った Writer モナドを用意し、String 版では " + <値>" という文字列が、List 版では値そのものがログとして残るようにしています。

なお、ログの内容を取得するには written、値を取得するには value を使います。

WriterSample.scala

package fits.sample

import scalaz._
import Scalaz._
import WriterT._

object WriterSample extends App {
    // ログに String を使った Write モナド生成（ Writer[String, Int] ）
    val logNum = (n: Int) => (x: Int) => writer (s" + $n", n + x)

    val r1 = writer ("2", 2) >>= logNum(5) >>= logNum(3)

    println(s"${r1.written} = ${r1.value}")

    // >>= の代わりに for を使用
    val r2 = for {
        w1 <- writer ("2", 2)
        w2 <- logNum(5)(w1)
        w3 <- logNum(3)(w2)
    } yield w3

    println(s"${r2.written} = ${r2.value}")

    // ログに List を使った Writer モナド生成（ Writer[List[Int], Int] ）
    val logNumList = (n: Int) => (x: Int) => writer (List(n), n + x)

    val r3 = writer (List(2), 2) >>= logNumList(5) >>= logNumList(3)

    println(s"${r3.written} = ${r3.value}")
}

実行結果は以下の通り。
加算した値がログとして残っている事を確認できます。

実行結果

> sbt console
・・・
scala> fits.sample.WriterSample.main(null)
2 + 5 + 3 = 10
2 + 5 + 3 = 10
List(2, 5, 3) = 10

List モナドの機能を備えた Writer モナド （WriterT.writerT() の利用）

次に、List モナドの機能を備えた Writer モナドを使ってみます。

基本的に、WriterT.writerT() にモナドで包んだ (ログ, 値) のタプルを渡す事で、別のモナドの機能を備えた Writer モナドを取得できます。

下記サンプルでは、List モナドに包んだ (String, Int) を WriterT.writerT() に渡す事で WriterT[List, String, Int] *2 を取得しています。

ちなみに、Scalaz における Writer[A, B] 型は WriterT[scalaz.Id.Id, A, B] の別名です。

WriterTSample.scala

・・・
object WriterTSample extends App {
    // Writer モナド生成（ WriterT[List, String, Int] ）
    val logManyNum = (n: Int) => (x: Int) => {
        val list = for {
            i <- (1 to n).toList
        } yield (s" + $i", x + i)

        // (String, Int) タプルの List を使って Writer モナド生成
        writerT(list)
    }

    val w = writerT(("2", 2) :: Nil) >>= logManyNum(3) >>= logManyNum(2)
    //以下でも同じ
    //val w = writerT(List(("2", 2))) >>= logManyNum(3) >>= logManyNum(2)

    println(s"written = ${w.written}")
    println(s"value = ${w.value}")
    println(s"run = ${w.run}")
}

実行結果は以下の通り。
ログと値がそれぞれ List になっており、run によって (ログ, 値) タプルの List を取得しています。

実行結果

scala> fits.sample.WriterTSample.main(null)
written = List(2 + 1 + 1, 2 + 1 + 2, 2 + 2 + 1, 2 + 2 + 2, 2 + 3 + 1, 2 + 3 + 2)
value = List(4, 5, 5, 6, 6, 7)
run = List((2 + 1 + 1,4), (2 + 1 + 2,5), (2 + 2 + 1,5), (2 + 2 + 2,6), (2 + 3 + 1,6), (2 + 3 + 2,7))

ナイト移動の経路1

それでは Writer モナドの応用として、前回 id:fits:20120912 のナイト移動の処理に対して移動経路をログとして付けてみます。

まずは List モナドの要素を Writer モナドとする事で実装してみました。

moveKnight の引数を Writer モナドに変更し Writer モナドの List を返すように変更しています。 （ログは String で追記）

そして、start から x 手後に end に到達した際の経路を返す routeReachIn を追加しました。

MoveKnightWriter.scala

・・・
object MoveKnightWriter extends App {

    type KnightPos = Tuple2[Int, Int]
    type PosCalc = Function2[Int, Int, Int]

    // Writer モナドの生成
    val createWriter = (p: KnightPos, sep: String) => writer (s"$sep$p", p)

    // 次の位置を設定した Writer モナドを取得
    val nextPos = (a: Int, b: Int, fa: PosCalc, fb: PosCalc) => 
        (p: KnightPos) => createWriter((fa(p._1, a), fb(p._2, b)), " -> ")

    val fl = List((_: Int) + (_: Int), (_: Int) - (_: Int))

    val moveKnight = (p: Writer[String, KnightPos]) => 
        (
            for {
                a <- List(2, 1)
                b <- List(2, 1)
                fa <- fl
                fb <- fl
                if a != b
            } yield p >>= nextPos(a, b, fa, fb)
        ) filter {
            _.value match {
                case (x, y) => 1 <= x && x <= 8 && 1 <= y && y <= 8
            }
        }

    val inMany = (x: Int) => (start: KnightPos) => {
        List(createWriter(start, "")) >>= List.fill(x){ Kleisli(moveKnight) }.reduceRight {(a, b) =>
            b <=< a
        }
    }

    // start から x 手後に end へ到達した際の経路 (String の List) を取得
    val routeReachIn = (x: Int) => (start: KnightPos, end: KnightPos) =>
        inMany(x)(start).filter { _.value == end } map { _.written }

    routeReachIn(3)((6, 2), (6, 1)).foreach {println}
    println("-----")
    routeReachIn(3)((6, 2), (7, 3)).foreach {println}
}

実行結果は以下の通り。
3手で (6, 2) から (6, 1) へ移動した際の経路が出力できており、(7, 3) への経路は無いため出力されていません。

実行結果

scala> fits.sample.MoveKnightWriter.main(null)
(6,2) -> (8,1) -> (7,3) -> (6,1)
(6,2) -> (4,1) -> (5,3) -> (6,1)
(6,2) -> (7,4) -> (5,3) -> (6,1)
(6,2) -> (7,4) -> (8,2) -> (6,1)
(6,2) -> (5,4) -> (7,3) -> (6,1)
(6,2) -> (5,4) -> (4,2) -> (6,1)
-----

なお、moveKnight は以下のように 2段で for を使って実装することも可能です。

val moveKnight = (p: Writer[String, KnightPos]) => 
    (
        for {
            a <- List(2, 1)
            b <- List(2, 1)
            fa <- fl
            fb <- fl
            if a != b
        } yield {
            for {
                pv <- p
                np <- nextPos(a, b, fa, fb)(pv)
            } yield np
        }
    ) filter {
        ・・・
    }

ナイト移動の経路2

次は WriterT.writerT() を使って List モナドの機能を持つ Writer モナドを使ってみます。

moveKnight の結果を WriterT[List, String, KnightPos] 用に変換し、Writer モナドを取得する moveKnightWriter 関数を別途用意してみました。

また、moveKnightWriter 関数を Kleisli に上手く適用する方法が分からなかったので *3、関数合成は >>= を使って自前で行っています。

MoveKnightWriterT.scala

・・・
object MoveKnightWriterT extends App {

    type KnightPos = Tuple2[Int, Int]

    val moveKnight = (p: KnightPos) => List(
        (p._1 + 2, p._2 - 1), (p._1 + 2, p._2 + 1),
        (p._1 - 2, p._2 - 1), (p._1 - 2, p._2 + 1),
        (p._1 + 1, p._2 - 2), (p._1 + 1, p._2 + 2),
        (p._1 - 1, p._2 - 2), (p._1 - 1, p._2 + 2)
    ).filter { case (x, y) => 1 <= x && x <= 8 && 1 <= y && y <= 8 }

    // Writer モナドを生成（ WriterT[List, String, KnightPos] ）
    val moveKnightWriter = (p: KnightPos) => {
        // List[KnightPos] を List[Tupble2[String, KnightPos]] に変換
        val list = moveKnight(p).map {np =>
            (s" -> $np", np)
        }
        writerT(list)
    }

    val inMany = (x: Int) => (start: KnightPos) => {
        val stWriter = writerT((s"$start", start) :: Nil)
        // 以下でも同じ
        //val stWriter = writerT(List((s"$start", start)))

        stWriter >>= List.fill(x){ moveKnightWriter }.reduceRight {(a, b) =>
            // Kleisli を使わずに関数合成
            (p: KnightPos) => b(p) >>= a
        }
    }

    // start から x 手後に end へ到達した際の経路 (String の List) を取得
    val routeReachIn = (x: Int) => (start: KnightPos, end: KnightPos) =>
        inMany(x)(start).run.filter { _._2 == end } map { _._1 }

    routeReachIn(3)((6, 2), (6, 1)).foreach {println}
    println("-----")
    routeReachIn(3)((6, 2), (7, 3)).foreach {println}
}

実行結果

scala> fits.sample.MoveKnightWriterT.main(null)
(6,2) -> (8,1) -> (7,3) -> (6,1)
(6,2) -> (4,1) -> (5,3) -> (6,1)
(6,2) -> (7,4) -> (5,3) -> (6,1)
(6,2) -> (7,4) -> (8,2) -> (6,1)
(6,2) -> (5,4) -> (7,3) -> (6,1)
(6,2) -> (5,4) -> (4,2) -> (6,1)
-----

*1:ログの追記は Writer モナド内で勝手にやってくれます

*2:ログは String、値は Int

*3:型の関係上、そのままでは適用できないようです