Scalaz でリストモナド - Kleisli による関数合成
前回 id:fits:20120828 に引き続き、今回も書籍「 すごいHaskellたのしく学ぼう! 」 のサンプルを Scalaz で実装してみる事にします。
- 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:チェス盤のナイトの現在位置から次に移動可能な位置を列挙する
