이 글은 책 Learn You a Haskell for Great Good!에서 290쪽부터 292쪽까지 읽고 일부를 정리한 것이다.
A Knight's Quest
여기 리스트 모나드로 풀 수 있는 문제가 하나 있다. 체스판이 하나 있고 그 위에 나이트가 하나 있다고 하자. 특정 위치에 나이트를 세 번 움직여서 갈 수 있는지 알고 싶다. 체스판에서 나이트의 위치를 표현하기 위해 순서쌍을 이용한다. 첫 번째 번호는 나이트가 있는 열을 나타내고 두 번째 번호는 행을 나타낸다.
type KnightPos = (Int, Int)나이트가 (6, 2)에서 시작한다고 하자. 나이트를 정확히 세 번 움직여서 (6, 1)로 이동할 수 있을까? 한 번 이동할 때 가장 좋은 위치는 어디일까? 전부 다는 어떨까! 어디로 이동할지 움직임 하나를 고르기보다는 모든 경우의 수를 한번에 골라 보자. 아래 함수는 현재 나이트의 위치를 입력으로 받아서 그 다음에 움직일 수 있는 모든 위치를 알려 준다.
moveKnight :: KnightPos -> [KnightPos]
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')(c', r')은 움직일 수 있는 모든 경우의 수를 담고 guard는 체스판 범위 밖에 있는 좌표는 걸러 준다. 이 함수는 리스트 모나드 없이 작성할 수도 있다.
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]위에서 정의한 두 함수 모두 같은 동작을 한다. 마음에 드는 걸로 골라서 사용하자.
ghci> moveKnight (6, 2)
[(8,1),(8,3),(4,1),(4,3),(7,4),(5,4)]
ghci> moveKnight (8, 1)
[(6,2),(7,3)]잘 동작한다! 좌표를 하나 넣었을 때 그 다음에 한 번만 움직였을 때 갈 수 있는 모든 경우의 수를 알 수 있게 되었다.
아래 함수는 현재 좌표를 넣으면 세 번 움직여서 갈 수 있는 모든 좌표를 알려 준다.
in3 :: KnightPos -> [KnightPos]
in3 start = do
first <- moveKnight start
second <- moveKnight first
moveKnight second위 코드를 do 표기법 없이 적으면 다음과 같다.
in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight이제 좌표 두 개를 입력 받아서 세 번 움직여서 갈 수 있는지 여부를 알려 주는 함수를 만들어 보자.
canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start먼저 세 번 움직여서 갈 수 있는 모든 경우의 수를 만들고 입력한 좌표가 그 중에 포함되는지 확인하면 된다. (6, 2)에서 (6, 1)로 세 번 움직여서 갈 수 있는지 보면 아래와 같다.
ghci> (6, 2) `canReachIn3` (6, 1)
True잘 된다! (6, 2)에서 (7, 3)은 어떨까?
ghci> (6, 2) `canReachIn3` (7, 3)
False참고
