Haskell Monad 函数

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]]，其中 1 个大列表包含每个可能的排序的列表移动。这可能会涉及 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]]，然后将结果展平回单个列表。

好的，现在我们已经暂时放弃了 monad，让我们回顾一下这个难题......假设您的初始 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 -> 类型的新函数[序列]——形状几乎相同。因此，使用任何感觉自然的风格填充每个函数的实现，然后一旦你让它工作，回到单子风格，用 >>= 替换 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 开始结束 = do
p <- in3 开始
守卫（p == 结束）
返回 $ getHistory 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

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

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 的结果包含列出所有可能的路径。