Arrow (Kleisli) で List モナド - Haskell, Frege, Scalaz
「Scalaz でリストモナド - Kleisli による関数合成 」等で試してきた List モナドを使ったチェスのナイト移動の処理を Arrow (Kleisli) を使って実装し直してみました。
Arrow は計算のための汎用的なインターフェースで、モナドを扱うための Arrow として Kleisli があります。
ソースは http://github.com/fits/try_samples/tree/master/blog/20140810/
Haskell の場合
Haskell の Arrow は >>>
や <<<
で合成できるようになっています。
Kleisli はモナドを扱うための Arrow なので、下記では List モナドを返す関数 moveKnight を Kleisli へ包んで合成しています。
Kleisli から包んだ関数を取り出すには runKleisli
を使います。
3手版
まずは 3手版です。
以前の List モナド版との違いは in3
と canReachIn3
関数を Arrow で実装し直した点です。
Kleisli を使えば、モナド値が無くてもモナドを返す関数 (通常の値を取ってモナドを返す関数) を簡単に合成できるので in3
はポイントフリースタイルで定義しました。 (このため canReachIn3 関数の引数の順序が 以前のもの と異なっています)
また、通常の関数は Arrow のインスタンスなので、canReachIn3 関数の部分は単純に canReachIn3 end = runKleisli in3 >>> elem end
とする事も可能です。
move_knight.hs
import Control.Arrow 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 :: Kleisli [] KnightPos KnightPos in3 = Kleisli moveKnight >>> Kleisli moveKnight >>> Kleisli moveKnight -- 指定位置に3手で到達できるか否かを判定 canReachIn3 :: Arrow a => KnightPos -> a KnightPos Bool canReachIn3 end = arr (runKleisli in3) >>> arr (elem end) -- 以下でも可 -- canReachIn3 :: KnightPos -> KnightPos -> Bool -- canReachIn3 end = runKleisli in3 >>> elem end main = do print $ runKleisli in3 $ (6, 2) print $ canReachIn3 (6, 1) $ (6, 2) print $ canReachIn3 (7, 3) $ (6, 2)
実行結果
> runghc move_knight.hs [(8,1),(8,3),・・・ ・・・ ,(3,4),(3,8)] True False
N手版
3手版と同様に inMany
と canReachInMany
関数を Arrow で実装し直してみました。
move_knight_many.hs
・・・ -- N手先の移動位置を列挙 inMany :: Int -> Kleisli [] KnightPos KnightPos inMany x = foldr (>>>) returnA (replicate x (Kleisli moveKnight)) -- 指定位置にN手で到達できるか否かを判定 canReachInMany :: Arrow a => Int -> KnightPos -> a KnightPos Bool canReachInMany x end = arr (runKleisli (inMany x)) >>> arr (elem end) -- 以下でも可 -- canReachInMany :: Int -> KnightPos -> KnightPos -> Bool -- canReachInMany x end = runKleisli (inMany x) >>> elem end main = do print $ runKleisli (inMany 3) $ (6, 2) print $ canReachInMany 3 (6, 1) $ (6, 2) print $ canReachInMany 3 (7, 3) $ (6, 2)
実行結果
> runghc move_knight_many.hs [(8,1),(8,3),・・・ ・・・ ,(3,4),(3,8)] True False
Frege の場合
Frege は Haskell とほとんど同じ実装になりますが、下記の点が異なります。
>>>
の代わりに.
で Arrow を合成runKleisli
の代わりにrun
を使用
なお、.
は >>>
と合成の向きが異なります。
3手版
3手版です。
move_knight.fr
package sample.MoveKnight where import frege.control.Arrow import frege.control.arrow.Kleisli 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 :: Kleisli [] KnightPos KnightPos in3 = Kleisli moveKnight . Kleisli moveKnight . Kleisli moveKnight -- 指定位置に3手で到達できるか否かを判定 canReachIn3 :: Arrow a => KnightPos -> a KnightPos Bool canReachIn3 end = arr (elem end) . arr in3.run -- 以下でも可 -- canReachIn3 :: KnightPos -> KnightPos -> Bool -- canReachIn3 end = elem end . in3.run main args = do println $ in3.run $ (6, 2) println $ canReachIn3 (6, 1) $ (6, 2) println $ canReachIn3 (7, 3) $ (6, 2)
実行結果
> java -jar frege3.21.586-g026e8d7.jar move_knight.fr ・・・ > java -cp .;frege3.21.586-g026e8d7.jar sample.MoveKnight [(8, 1), (8, 3), ・・・ ・・・ (3, 4), (3, 8)] true false
N手版
N手版です。
move_knight_many.fr
package sample.MoveKnightMany where ・・・ -- N手先の移動位置を列挙 inMany :: Int -> Kleisli [] KnightPos KnightPos inMany x = foldr (.) id (replicate x (Kleisli moveKnight)) -- 指定位置にN手で到達できるか否かを判定 canReachInMany :: Arrow a => Int -> KnightPos -> a KnightPos Bool canReachInMany x end = arr (elem end) . arr (inMany x).run -- 以下でも可 -- canReachInMany :: Int -> KnightPos -> KnightPos -> Bool -- canReachInMany x end = elem end . (inMany x).run main args = do println $ (inMany 3).run $ (6, 2) println $ canReachInMany 3 (6, 1) $ (6, 2) println $ canReachInMany 3 (7, 3) $ (6, 2)
実行結果
> java -jar frege3.21.586-g026e8d7.jar move_knight_many.fr ・・・ > java -cp .;frege3.21.586-g026e8d7.jar sample.MoveKnightMany [(8, 1), (8, 3), ・・・ ・・・ (3, 4), (3, 8)] true false
Scalaz の場合
最後に Scalaz を使った Scala による実装です。
Haskell と同様に >>>
で Arrow を合成できるようになっています。
3手版
3手版です。
MoveKnight.scala
package sample import scalaz._ import Scalaz._ object MoveKnight extends App { type KnightPos = Tuple2[Int, Int] val inRange = (p: Int) => 1 to 8 contains p 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) => inRange(x) && inRange(y) } // 3手先の移動位置を列挙 val in3 = Kleisli(moveKnight) >>> Kleisli(moveKnight) >>> Kleisli(moveKnight) // 以下でも可 // val in3 = Kleisli(moveKnight) >==> moveKnight >==> moveKnight // 指定位置に3手で到達できるか否かを判定 val canReachIn3 = (end: KnightPos) => in3.run >>> { xs => xs.contains(end) } in3 (6, 2) |> println (6, 2) |> canReachIn3 (6, 1) |> println (6, 2) |> canReachIn3 (7, 3) |> println }
実行結果
> gradle run MoveKnight :compileJava UP-TO-DATE :compileScala UP-TO-DATE :processResources UP-TO-DATE :classes UP-TO-DATE :run List((8,1), (8,3), ・・・ ・・・ ・・・, (3,4), (3,8)) true false
N手版
N手版です。
MoveKnightMany.scala
package sample import scalaz._ import Scalaz._ object MoveKnightMany extends App { ・・・ // N手先の移動位置を列挙 val inMany = (x: Int) => List.fill(x) { Kleisli(moveKnight) }.reduce { (a, b) => a >>> b } // 以下でも可 // val inMany = (x: Int) => List.fill(x) { Kleisli(moveKnight) }.reduce { (a, b) => a >=> b } // 指定位置にN手で到達できるか否かを判定 val canReachInMany = (x: Int) => (end: KnightPos) => inMany(x).run >>> { xs => xs.contains(end) } (6, 2) |> inMany(3) |> println (6, 2) |> canReachInMany(3)(6, 1) |> println (6, 2) |> canReachInMany(3)(7, 3) |> println }
実行結果
> gradle run -Pmany MoveKnightMany :compileJava UP-TO-DATE :compileScala UP-TO-DATE :processResources UP-TO-DATE :classes UP-TO-DATE :run List((8,1), (8,3), ・・・ ・・・ ・・・, (3,4), (3,8)) true false
なお、ビルドと実行には下記のような Gradle ビルド定義ファイルを使用しました。
build.gradle
apply plugin: 'application' apply plugin: 'scala' repositories { mavenCentral() } dependencies { compile 'org.scala-lang:scala-library:2.11.2' compile 'org.scalaz:scalaz-core_2.11:7.1.0' } if (!hasProperty('many')) { println 'MoveKnight' mainClassName = 'sample.MoveKnight' } else { println 'MoveKnightMany' mainClassName = 'sample.MoveKnightMany' }