[Haskell] 『すごいHaskell たのしく学ぼう!』13.6節の演習

『すごいHaskell たのしく学ぼう!』の13.6節ではリストモナドによる非決定性計算を使ってチェスのナイトが3手で指定したマスに到達できるかを計算する関数が紹介された。

ghci> (6, 2) `canReachIn3` (6, 1)
True

のように始点と終点を指定すると到達の可否がかえってくる。

節尾の演習にどのように到達できるか教えてくれるようにせよとあったので書いてみる。

import Monad

type KnightPos = (Int, Int)
type KnightTrack = [KnightPos]

moveKnight :: KnightTrack -> [KnightTrack]
moveKnight ((c, r) : xs)  = 
  map addLog $
  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]
        addLog pos = pos : (c, r) : xs

in3 :: KnightTrack -> [KnightTrack]
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight

canReachIn3 :: KnightPos -> KnightPos -> [KnightTrack]
canReachIn3 start end = 
  filter (\(pos : track) -> pos == end) $ in3 [start]

canReachIn3は真偽値でなくナイトの軌跡を返すように変更した。到達できないときは [] が帰る。

ghci>canReachIn3 (6,2) (6,1)
[[(6,1),(7,3),(8,1),(6,2)],[(6,1),(5,3),(4,1),(6,2)],[(6,1),(5,3),(7,4),(6,2)],
[(6,1),(8,2),(7,4),(6,2)],[(6,1),(7,3),(5,4),(6,2)],[(6,1),(4,2),(5,4),(6,2)]]
ghci>canReachIn3 (6,2) (7,3)
[]