Haskell Monad Functions

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.

---

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.

---

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

---

"That would probably then involve moveKnight having a [KnightPos] parameter instead of a KnightPos one..." No, you wouldn't want to do that. Keep the functions as basic as possible.

"...which would then defeat the whole point of monads right?" Well, if you want all orderings of moves, you just don't in every move use the join implied in >>= . You might define a function returning a list of all paths of length n from a given starting point, where we may implement those paths as list of the positions passed, for efficiency reasons in reverse order.

waysFrom :: KnightPos -> Int -> [[KnightPos]]

First for one move (or zero)

waysFrom start 0 = [[start]]
waysFrom start 1 = map (t -> [t, start]) $ moveKnight start

and then for arbitrary numbers of moves, at which point you can use again use >>= to join the trie-like structure resulting from straightforward recursion to a list of move lists:

waysFrom start n = waysFrom start (n-1) >>= (w -> [t:w | t<-moveKnight$head w])

there may be a better way to do this, but it wouldn't actually "defeat" the whole point of monads.

链接地址: http://www.djcxy.com/p/43356.html

上一篇: 在Haskell中合并monad

下一篇: Haskell Monad函数