Haskell Monad Functions

Question

我正在阅读Haskell教程，并给出了这段代码来移动国际象棋中的骑士:

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 

一个练习是修改函数，使canReachIn3告诉你，如果有可能到达终点位置，你可以采取什么行动。

这个教程基本上没有练习，所以我对这样的基本东西有困难…我正在考虑将所有3个函数的返回值更改为[[KnightPos]]，其中一个大列表包含每个可能的移动顺序的列表。这可能会涉及moveKnight使用[KnightPos]参数而不是KnightPos参数，这就会破坏monad的整体意义，对吧?

Answer 1

在考虑这段代码时，如果您发现普通的旧列表操作对您来说更自然，那么从Monad概念退一步可能会有所帮助。因此，您可以将示例代码重写为:

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

秘诀在于concatMap。您可能已经知道，它是List单子中的>>=的同义词，但是现在将它看作是将KnightPos -> [KnightPos]类型的函数映射到列表[KnightPos]上以产生列表[[KnightPos]]的列表，然后将结果平放回单个列表可能会更有帮助。

好了，现在我们已经暂时放弃了单子，让我们回头看看这个谜题…假设你的初始KnightPos是(4,4)，你想要追踪从那个位置开始的所有可能的移动序列。所以定义另一个类型同义词:

type Sequence = [KnightPos]

然后你想让moveKnight对这些序列进行操作，从序列的最后一个位置找到所有可能的移动:

moveKnight :: Sequence -> [Sequence]

所以从序列[(4,4)]开始，我们会得到序列列表:[[(4,4), (6,3)], [(4,4), (6,5)], [(4,4), (2,3)], ... ]。然后我认为您需要对in3进行的唯一更改是相应地修复其类型签名:

in3 :: Sequence -> [Sequence]

我不认为实际的实现改变了。最后，您将希望canReachIn3看起来像:

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

我故意在这里留下实现细节，因为我不想完全破坏你的谜题，但我希望我已经说明了一点，即列表或列表的列表或其他任何东西都没有特别"特殊"的地方。我们所做的只是将KnightPos -> [KnightPos]类型的函数替换为Sequence -> [Sequence]类型的新函数——形状几乎相同。因此，使用任何感觉自然的样式填充每个函数的实现，然后一旦您使其工作，就返回到一元样式，将concatMap替换为>>=，等等。

Answer 2

我建议让KnightPos成为一个数据结构，不仅能够保存当前药水，还能够保存它来自的KnightPos:

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

然后需要实现Eq和Show类，并修复moveKnight，以便它返回具有适当历史设置的结构:

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

确保你理解了这个函数的最后一行。

函数in3现在不需要修改就可以工作。我写了一个新函数pathIn3 :: KnightPos -> KnightPos -> [[KinghtPos]]，它在3个单变量语句中返回从start到end的所有可能路径。

剧透

<引用类>

pathIn3:: KnightPos -> KnightPos -> [[KnightPos]]
pathIn3 start end = do
P <- in3 start
守护(p == end)
返回$ gethhistory p

Answer 3

"这可能会涉及moveKnight有一个[KnightPos]参数而不是KnightPos一个…"不，你不会想这么做的。尽量保持基本的功能。

"……这就破坏了单子的意义，对吧?"好吧，如果你想要所有的排序的，你只是不使用>>=隐含的join在每一步。你可以定义一个函数，返回从给定起始点开始的长度为n的所有路径的列表，出于效率原因，我们可以将这些路径实现为传递位置的列表，顺序相反。

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

第一次移动(或零)

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

，然后对于任意数量的移动，此时您可以再次使用>>=来连接由直接递归产生的类似尝试的结构到一个移动列表列表:

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

可能有更好的方法来做到这一点，但它实际上不会"破坏"单子的全部意义。

Answer 4

我正在阅读教程，我的解决方案是稍微改变函数in3和canReachIn3

in3 :: KnightPos -> [[KnightPos]]
in3 start = do
    first <- moveKnight start
    second <- moveKnight first
    third <- moveKnight second
    return [start, first, second, third]
canReachIn3 :: KnightPos -> KnightPos -> [[KnightPos]]
canReachIn3 start end = filter (elem end) $ in3 start

in3的结果包含list所有可能的路径