Haskell Monad Functions

Question

I'm going through a Haskell tutorial and am given this piece of code to do with moving a knight in chess:

import Control.Monad

type KnightPos = (Int,Int)

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')

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

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start 

An exercise is to modify the functions so that canReachIn3 tells you what moves you can take to get to the end position if it is possible to get there.

This tutorial has basically no exercises so I'm having trouble with basic stuff like this...I was thinking of changing the return values of all 3 functions to [[KnightPos]] where 1 big list contains a list for every possible ordering of moves. That would probably then involve moveKnight having a [KnightPos] parameter instead of a KnightPos one, which would then defeat the whole point of monads right?

Any help/thoughts would be greatly appreciated, thanks.

Answer 1

It might help to step back from the Monad concept for a bit when thinking about this code, if you find that plain old list operations are more natural for you. So you can rewrite the example code (with a little bit of cleanup for legibility) as:

type KnightPos = (Int,Int)

moveKnight :: KnightPos -> [KnightPos]  
moveKnight (c,r) = filter legal candidates where
    candidates = [(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)]
    legal (c',r') = c' `elem` [1..8] && r' `elem` [1..8]

in3 :: KnightPos -> [KnightPos]
in3 start = concatMap moveKnight (concatMap moveKnight (moveKnight start))

canReachIn3 :: KnightPos -> KnightPos -> Bool
canReachIn3 start end = end `elem` in3 start

The secret sauce is in concatMap. As you probably know already, it's synonymous with >>= in the List monad, but it might be more helpful right now to think of it as mapping a function of type KnightPos -> [KnightPos] over a list [KnightPos] to yield a list of lists [[KnightPos]], and then flattening the result back into a single list.

Okay, so now that we've dispensed with monads for the moment, let's look back at the puzzle... Let's say your initial KnightPos is (4,4), and you want to track all possible sequences of moves from that position. So define another type synonym:

type Sequence = [KnightPos]

Then you'd want moveKnight to operate on these sequences, finding all possible moves from the last position in the sequence:

moveKnight :: Sequence -> [Sequence]

So starting from a sequence [(4,4)], we'd get the list of sequences: [[(4,4), (6,3)], [(4,4), (6,5)], [(4,4), (2,3)], ... ]. Then I think the only change you'd need to make to in3 is to fix its type signature accordingly:

in3 :: Sequence -> [Sequence]

I don't think the actual implementation changes. Finally, you'll want canReachIn3 to look something like:

canReachIn3 :: KnightPos -> KnightPos -> [Sequence]

I'm leaving the implementation detail out here on purpose since I don't want to ruin the puzzle for you entirely, but I'm hoping I've illustrated the point here that there isn't anything particularly "special" about a list, or a list of lists, or whatever. All we've really done is substituted a function of type KnightPos -> [KnightPos] with a new function of type Sequence -> [Sequence] -- pretty much the same shape. So fill in the implementations of each function using whatever style feels natural, and then once you have it working, go back to the monadic style, replacing concatMap with >>= and so on.

Answer 2

I would suggest making KnightPos a data structure capable of holding not only the current potion, but also the KnightPos that it came from:

data KnightPos = KnightPos {history :: Maybe KnightPos, position :: (Int,Int) }

You then need to implement the Eq and Show classes, and fix moveKnight so that it returns this structure with its history set appropriately:

moveKnight :: KnightPos -> [KnightPos]  
moveKnight p@KnightPos{position = (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 $ KnightPos (Just p) (c',r') 

Make sure you understand the last line of this function.

The function in3 should now work without modification. I wrote a new function,pathIn3 :: KnightPos -> KnightPos -> [[KinghtPos]] that returns all possible paths from start to end in 3 monadic statements.

Spoiler Alert

pathIn3 :: KnightPos -> KnightPos -> [[KnightPos]]
pathIn3 start end = do
p <- in3 start
guard (p == end)
return $ getHistory p