読者です 読者をやめる 読者になる 読者になる

すごいhaskell本の練習問題(knightの動き)

すごいhaskell本の13章にあるチェスのknightの動きを求める練習問題を解いてみたのでメモ

初期位置と目的位置、移動回数を指定して
移動できるならその経路をリストとして出力するようにした

最終的なコードはこんな感じ

 import Control.Monad    

type Pos = (Int, Int)  
type Route = [Pos]     

moveKnight :: Pos -> [Pos]                                                                             
moveKnight (c, r) = do                                                                                 
  (c', r') <- [(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)] 
  guard (c' `elem` [1..8] && r' `elem` [1..8])                                                         
  return (c', r')                                                                                      

findRoute :: Pos -> Pos -> Int -> [Route]               
findRoute from to moveCount = findRoute' [from] moveCount                   
  where                                                 
    findRoute' :: Route -> Int -> [Route]               
    findRoute' route n                                  
      | n <= 0 = [reverse route | head route == to]     
      | otherwise = do                                  
          r <- map (:route) $ moveKnight $ head route   
          findRoute' r (n-1)                            

moveKnightは本の内容のままで、指定した位置の次に取りうる位置を返す関数
経路は位置のリストとして表現し、移動できる位置があればそれを既存の経路につなげていく

リストをモナドとして使うことはあまりしたことがなかったため
次の位置を既存の経路につなげてmapする処理で生成されたリストの一要素をrに束縛して使うというやり方を考えるのに時間がかかった。最初はリストとして束縛した上でさらにmapするようなやり方を考えていた。

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!