Scalaz でリストモナド - Kleisli による関数合成

前回 id:fits:20120828 に引き続き、今回も書籍「 すごいHaskellたのしく学ぼう! 」 のサンプルを Scalaz で実装してみる事にします。

今回は、リストモナドを使ったナイト移動 *1 の処理です。

  • Scalaz 7.0.0-M3
  • sbt 0.12.0

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

3手先の位置

まずはお手本とする Haskell 版です。(本のサンプルそのままです)

Haskell版 move_knight.hs
type KnightPos = (Int, Int)

-- ナイトの次の移動先を列挙
moveKnight :: KnightPos -> [KnightPos]
moveKnight (c, r) = filter onBoard
    [
        (c + 2, r - 1), (c + 2, r + 1),
        (c - 2, r - 1), (c - 2, r + 1),
        (c + 1, r - 2), (c + 1, r + 2),
        (c - 1, r - 2), (c - 1, r + 2)
    ]
    where onBoard (c', r') = c' `elem` [1..8] && r' `elem` [1..8]

-- 3手先の移動位置を列挙(重複あり)
in3 :: KnightPos -> [KnightPos]
in3 start = do
    first <- moveKnight start
    second <- moveKnight first
    moveKnight second
{- 以下でも可
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight
-}

-- 指定位置に3手で到達できるか否かを判定
canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

main = do
    putStrLn $ show $ moveKnight (8, 1)

    putStrLn $ show $ in3 (6, 2)

    putStrLn $ show $ (6, 2) `canReachIn3` (6, 1)
    putStrLn $ show $ (6, 2) `canReachIn3` (7, 3)

実行結果は以下のようになります。

Haskell版の実行結果
> runghc move_knight.hs
[(6,2),(7,3)]
[(8,1),(8,3),・・・,(3,4),(3,8)]
True
False


それでは、Scala で実装していきます。

まずは、Scalaz を使わずに実装してみます。
do 式の代わりに for を使っている等の違いはありますが、基本的な処理内容は Haskell と同じです。

Scala版 move_knight.scala
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 }

// 3手先の移動位置を列挙(重複あり)
val in3 = (start: KnightPos) =>
    for {
        first <- moveKnight(start)
        second <- moveKnight(first)
        third <- moveKnight(second)
    } yield third

// 指定位置に3手で到達できるか否かを判定
val canReachIn3 = (start: KnightPos, end: KnightPos) => in3(start).contains(end)

println( moveKnight (8, 1) )

println( in3 (6, 2) )

println( canReachIn3((6, 2), (6, 1)) )
println( canReachIn3((6, 2), (7, 3)) )

実行すると以下のように Haskell と同等の結果となります。

Scala版の実行結果
> scala move_knight.scala
List((6,2), (7,3))
List((8,1), (8,3), ・・・, (3,4), (3,8))
true
false

ちなみに、moveKnight の処理は for を使って以下のように実装する事も可能です。(ただし、上記のものとは出力結果の順序が異なります)

処理内容は、p の位置と (2, 1) もしくは (1, 2) との加算・減算の組み合わせをリスト化しています。

moveKnight の別実装 Scala版 move_knight2.scala
・・・
val fl = List((_: Int) + (_: Int), (_: Int) - (_: Int))

val moveKnight = (p: KnightPos) =>
    (
        for {
            a <- List(2, 1)
            b <- List(2, 1)
            fa <- fl
            fb <- fl
            if a != b
        } yield (fa(p._1, a), fb(p._2, b))
    ) filter {
        case (x, y) => 1 <= x && x <= 8 && 1 <= y && y <= 8
    }
・・・


次は Scalaz で実装してみます。
と言っても基本的には in3 の処理を >>= を使って書き直しただけです。(ただし、sbt で実行するため object にしています)

Scalaz版 MoveKnight.scala
package fits.sample

import scalaz._
import Scalaz._

object MoveKnight 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 }

    val in3 = (start: KnightPos) => start |> moveKnight >>= moveKnight >>= moveKnight

    val canReachIn3 = (start: KnightPos, end: KnightPos) => in3(start).contains(end)

    println( moveKnight (8, 1) )

    println( in3 (6, 2) )

    println( canReachIn3((6, 2), (6, 1)) )
    println( canReachIn3((6, 2), (7, 3)) )
}

実行結果は以下の通りです。

Scalaz版の実行結果
> sbt console
・・・
scala> fits.sample.MoveKnight.main(null)
List((6,2), (7,3))
List((8,1), (8,3), ・・・, (3,4), (3,8))
true
false

sbt のビルドファイルは以下の通りです。

build.sbt
scalaVersion := "2.10.0-M7"

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

N手先の位置

次は 3手と手数を固定せずに引数で手数を指定できるようにします。

まずは Haskell 版です。(こちらも本のサンプルそのままです)

Haskell版 move_knight_many.hs
import Control.Monad

type KnightPos = (Int, Int)

moveKnight :: KnightPos -> [KnightPos]
moveKnight (c, r) = filter onBoard
    [
        (c + 2, r - 1), (c + 2, r + 1),
        (c - 2, r - 1), (c - 2, r + 1),
        (c + 1, r - 2), (c + 1, r + 2),
        (c - 1, r - 2), (c - 1, r + 2)
    ]
    where onBoard (c', r') = c' `elem` [1..8] && r' `elem` [1..8]

-- x手先の移動位置を列挙
inMany :: Int -> KnightPos -> [KnightPos]
inMany x start = return start >>= foldr (<=<)
    return (replicate x moveKnight)

-- 指定位置にx手で到達できるか否かを判定
canReachIn :: Int -> KnightPos -> KnightPos -> Bool
canReachIn x start end = end `elem` inMany x start

main = do
    putStrLn $ show $ inMany 3 (6, 2)

    putStrLn $ show $ canReachIn 3 (6, 2) (6, 1)
    putStrLn $ show $ canReachIn 3 (6, 2) (7, 3)

moveKnight 関数が x 個入ったリストを作って foldr と <=< でモナディック関数の合成を行っています。

実行結果は以下の通り。3手を指定した場合に 3手固定版と同じ結果となります。

Haskell版の実行結果
> runghc move_knight_many.hs
[(8,1),(8,3),・・・,(3,4),(3,8)]
True
False


Scalaz 版は以下のようになります。
<=< 等を使ったモナディック関数の合成を行うには Kleisli を使います。

Scalaz版 MoveKnightMany.scala
package fits.sample

import scalaz._
import Scalaz._

object MoveKnightMany 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 }

    // x手先の移動位置を列挙
    val inMany = (x: Int) => (start: KnightPos) => {
        start |> List.fill(x){ Kleisli(moveKnight) }.reduceRight {(a, b) =>
            b <=< a
        }
    }

    // 指定位置にx手で到達できるか否かを判定
    val canReachIn = (x: Int) => (start: KnightPos, end: KnightPos) =>
        inMany(x)(start).contains(end)

    println( inMany(3)(6, 2) )

    println( canReachIn(3)((6, 2), (6, 1)) )
    println( canReachIn(3)((6, 2), (7, 3)) )
}

処理内容は Haskell とほぼ同じで、Kleisli でくるんだ moveKnight が x 個入ったリストを作って reduceRight と <=< で関数合成し、合成結果の関数に対して開始位置 start を適用しています。

実行結果は以下の通りです。

Scalaz版の実行結果
> sbt console
・・・
scala> fits.sample.MoveKnightMany.main(null)
List((8,1), (8,3), ・・・, (3,4), (3,8))
true
false
備考

reduceRight を使わずに reduceLeft と >=> を使って以下のようにしても同じ結果となります。(集計結果の方を b で統一しています)

val inMany = (x: Int) => (start: KnightPos) => {
    start |> List.fill(x){ Kleisli(moveKnight) }.reduceLeft {(b, a) =>
        b >=> a
    }
}

*1:チェス盤のナイトの現在位置から次に移動可能な位置を列挙する