Haskell：Monad的Monad

Question

我正在学习Haskell，对于Monad这个概念我有些困惑。虽然我知道它是什么，但在某些情况下我还是遇到了问题。在学习LYAH时，我遇到了一个练习，要计算骑士（象棋中的角色）在3次移动后所能到达的位置。我们使用了列表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')

这个函数可行，如果我把我的位置传给这个函数，它就可以成功地计算出可能的未来位置，但现在我想在其中实现Writer monad，以便我可以获取到达此点的详细信息。 所以我写了这个函数，

假设，

type KnightRoute = Writer [KnightPos] KnightPos

moveKnight' :: KnightPos -> [KnightRoute]
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 $ toKr (c',r') (c,r)
 where toKr pos oldpos = Writer (pos,[oldpos])

如果我提供一个KnightPos，它可以工作，但使用单子，我无法从KnightRoute中提取KnightPos以便另一次执行该函数...

*Main> let a = moveKnight' (2,4) !! 0
*Main> runWriter a
((4,3),[(2,4)])
*Main> a >>= moveKnight'

<interactive>:4:7:
Couldn't match type ‘[]’ with ‘Writer [KnightPos]’
Expected type: KnightPos -> Writer [KnightPos] KnightRoute
  Actual type: KnightPos -> [KnightRoute]
In the second argument of ‘(>>=)’, namely ‘moveKnight'’
In the expression: a >>= moveKnight'

我明白为什么它不起作用了，我从我的Writer中提取了(4,3)，但是我将其传递给了KnightPos'。但是KnightPos'返回一个KnightRoute列表，而我需要一个KnightRoute，这是一个逻辑错误，但我不知道该怎么做。是否有一种使用Monads的简单方法来解决这个问题？

提前感谢 :)

- Bryce Tichit

---

请注意，使用Writer或WriterT与列表作为日志单子是相当低效的（二次时间），因为您不断地向右添加。差异列表或更专业的容器是更好的选择。 - leftaroundabout

我最近学习到了这个，确实使用差分列表似乎更高效。无论如何，我们应该始终将差分列表作为日志单子使用，因为它只是更快的一种方法。 - Bryce Tichit

Answer 1

这种“两个单子的组合”在Haskell中非常常见。幸运的是，该语言足够灵活，我们可以很好地抽象出它。

从数学上讲，您想要的是两个函子的组合。通常使用transformers的概念来表达，而不是使用新类型。例如，您可以使用WriterT单子变换器，而不是直接使用Writer单子。 WriterT w [] a与[Writer w a]基本相同，因此在您的情况下，您可以使用：

import Control.Monad.Trans.Class
import Control.Monad.Trans.Writer

moveKnight'' :: KnightPos -> WriterT [] [KnightPos] KnightPos
moveKnight'' (c,r) = do
   (c',r') <- lift [(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])
   tell [(c,r)]
   return (c',r')

- leftaroundabout

---

谢谢，它可以工作！我会更深入地研究单子变换器。我之前不知道它们 :) - Bryce Tichit

Answer 2

你可以写

你可以写

a' :: Int -> KnightRoute
a' i = a >>= \p -> moveKnight' p !! i

在这里，i 用于消除作者内部的列表。而且，由于惰性求值，你可以将 Int -> a 转换为 [a]：

asList :: (Int -> a) -> [a]
asList f = map f [1..]

那么，a' 的所有路由列表如下：

a's :: [KnightRoute]
a's = asList a'

把所有东西放在一起：

moveKnight :: KnightRoute -> [KnightRoute]
moveKnight k = map (\i -> k >>= \p -> moveKnight' p !! i) [1..]

- effectfully

---

嘿，非常感谢你的回答。很抱歉我没有清楚地理解...你是写了伪代码吗？因为你将变量名“a”用作单子但从未定义它，所以我看不到它的含义。也许是我弄错了 :) - Bryce Tichit

@Bryce Tichit，不用谢。a 的意思是你的 a：let a = moveKnight' (2,4) !! 0，也就是说这只是一个例子。实际的函数 moveKnight 可以适用于任何你提供的 KnightRoute。 - effectfully

我现在明白这是一种非常聪明的方式，因为它使用了延迟计算，我喜欢这表明Haskell是多么强大 :) - Bryce Tichit