Haskell 递归以 'do' 表示法

Question

我正在阅读本教程 http://learnyouahaskell.com/a-fistful-of-monads并偶然发现了这个定义:

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 = do   
    first <- moveKnight start  
    second <- moveKnight first  
    moveKnight second  

我有一个关于函数 in3 的问题(这需要棋盘上的一对坐标 (Int,Int) 并生成一个字段列表 [(Int,Int)] 可以在骑士的 3 次移动中从该字段到达。是否可能(如果是的话 - 如何这样做)将该功能改造成 inNMoves :: (Num a) => KnightPos -> a -> [KnightPos]以便它还以移动次数作为参数，而不是恰好绑定(bind) 3 次跳跃？

Answer 1

由于这个练习是关于 List Monad 的，尽量不要去想你对 List 的了解，而是将自己限制在 monad 的结构上。所以那将是

move :: Monad m => Pos -> m Pos

即， move需要一个 Pos并给你一些关于 Pos 的东西某些 monadic 上下文中的事物 m . (在列表的情况下，“上下文”是“任意多重性+排序”。但尽量不要考虑它)。

还有，先不说 do这里只是使用 (>>=) 的语法糖.出于本说明的目的，您需要知道如何使用 (>>=) 将 do 转换为表达式。 .
(>>=)有签名 m a -> (a -> m b) -> m b .我们需要的实例是 m Pos -> (Pos -> m Pos) -> m Pos .你看我们已经实例化了 a和 b这里到 Pos .您也可以识别中间部分 (Pos -> m Pos)正在 move在这里签名。所以使用 (>>=)并给它 move作为第二个参数，我们可以创建一个 m Pos -> m Pos 类型的函数.

moveM :: Monad m => m Pos -> m Pos
moveM mp = mp >>= move

单子(monad)自同态的组成

很明显 m Pos -> m Pos可以按您希望的顺序执行，因为它是从类型到自身的函数(我认为这可以称为 monad 内同态，因为类型是 monad)。

让我们编写一个执行两次移动的函数。

move2M :: Monad m => m Pos -> m Pos
move2M mp = moveM (moveM (mp))

或者以 pointfree 风格(只考虑转换，而不考虑转换后的对象):

move2M :: Monad m => m Pos -> m Pos
move2M = moveM . moveM

对于一般情况(由整数 n 参数化的移动次数)，我们只需要一些 moveM s 由函数链操作符 . 连接.所以如果 n 是 3，我们想要 moveM . moveM . moveM .以下是如何以编程方式执行此操作:

nmoveM :: Monad m => Int -> m Pos -> m Pos
nmoveM n = foldr1 (.) (replicate n moveM)  -- n "moveM"s connected by (.)

这里出现一个问题:移动0次的结果是什么？ foldr1对于 n 的值未定义<= 0. 定义 nmoveM 0 很有意义到“什么都不做”。换句话说，恒等函数， id .

nmoveM :: Monad m => Int -> m Pos -> m Pos
nmoveM n = foldr (.) id (replicate n moveM)

在这里，我们使用了 foldr而不是 foldr1这需要一个额外的“基本案例”， id .

现在我们基本上有了我们想要的东西，但是类型签名并不适合 100%:我们有一个 m Pos -> m Pos ，但我们想要 Pos -> m Pos .这意味着，给定 Pos ，我们首先必须将其嵌入上下文 m ，然后执行 nMoveM .这个嵌入运算符(我认为它可以称为初始代数)是 return (类型 Monad m => a -> m a)

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = nmoveM n . return

让我们一次写下所有内容，这样您就可以充分享受简洁的魅力。

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = foldr (.) id (replicate n move) . return

箭头的组成

使用 (>>=)实际上通常有点不干净，因为它是如此不对称:它需要一个 m a和一个 a -> m b .换句话说，它有点过于关心转换后的对象，而只关心我们案例的转换。这使得组合转换变得不必要地困难。这就是为什么我们不得不加入 . return : 这是 Pos的初始转换至 m Pos ，这样我们就可以自由组合任意数量的 m Pos -> m Pos .

使用 (>>=)导致以下模式:

ma >>= f_1 >>= f_2 >>= ... >>= f_n

哪里 ma是 monad 和 f_i是 a -> m b 类型的“箭头” (通常 a = b)。

有一个更好的变体， (>=>) ，它结合了两个 a -> m b按序列键入箭头，并返回另一个箭头。

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)

在这里，我们没有不必要地关注变换后的对象，而只关注变换及其组成。

现在让我们同意 move实际上是这样一个箭头( Pos -> m Pos )。所以

move >=> move >=> move >=> move >=> move

仍然是 Pos -> m Pos 类型的有效表达式.使用 (>=>) 时，monad 的可组合特性变得更加明显。 .

我们可以重写 nmoves使用 (>=>)像这样:

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = foldr1 (>=>) (replicate n move)  -- n "move"s connected by >=>

同样，我们使用了 foldr1 ，我们在问“是什么让 0 次连续移动”？它必须是相同的类型， Pos -> m Pos ，答案是 return .

nmoves :: Monad m => Int -> Pos -> m Pos
nmoves n = foldr (>=>) return (replicate n move)

将此与我们之前对 nmoves 的定义进行比较在 monad 自同态世界中:代替函数与 (.) 结合使用和基本案例 id ，我们现在将箭头与 (>=>) 结合起来和基本案例 return .好处是我们不必注入(inject)给定的 Pos至 m Pos .

什么更有意义取决于您的情况，但通常情况下 (>=>)比 (>>=)干净多了.