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)，该字段可以在骑士的三个动作中从该字段到达)。

是否有可能(如果是的话-如何做到这一点)将该函数转换为

inNMoves :: (Num a) => KnightPos -> a -> [KnightPos]

所以它也以移动的次数作为参数，而不是被绑定到确切的3跳？

Answer 1

由于这个练习是关于列表Monad的，所以不要去想你知道的关于列表的内容，而是把自己限制在Monad的结构上。所以那会是

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

也就是说，move获取一个Pos，并在一些一元上下文中返回关于Pos事物的内容，m。(就列表而言，“上下文”为“任意多重性+排序”。但尽量不要去想)。

另外，我们不要在这里讨论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

单自同态的合成

很明显，m Pos -> m Pos可以按照您的意愿按顺序执行，因为它是一个从类型到自身的函数(我认为它可以称为单自同态，因为该类型是monad)。

让我们写一个函数，做两个动作。

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

或者以无意义的方式(只考虑转换，而不是转换对象)：

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

对于一般情况(由整数n参数化的移动次数)，我们只需要一些由函数链接运算符.连接的moveM。如果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是单一事物，而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类型的有效表达式。当使用(>=>)时，monads的可组合性变得更加明显。

我们可以使用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的早期定义进行比较:而不是将函数与(.)和基本大小写id组合起来，而是将箭头与(>=>)和基本case return组合起来。好处是我们不必将给定的Pos注入m Pos。

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

Answer 2

使用直接递归：

inNMoves :: KnightPos -> Int -> [KnightPos]
inNMoves start 0 = return start
inNMoves start n = do
  first <- moveKnight start
  inNMoves first (n - 1)

但是正如注释中提到的:您可以使用内置函数来实现这一点。例如：

inNMoves start n = (foldl (>>=) . return) start (replicate n moveKnight)

甚至完全没有意义：

inNMoves = (. flip replicate moveKnight) . foldl (>>=) . return

Answer 3

请注意，concatMap moveKnight具有[Knight] -> [Knight]类型，并将返回可从输入位置到达的位置。

知道了这一点，您可以使用：

iterate (concatMap moveKnight)

若要生成无限个位置集列表，下一组位置是通过从上一组中的位置移动来获得下一组位置的。

例如：

iterate (concatMap moveKnight) [(1,2)]
  = [ [(1,2)],               -- the initial list
      [(3,1),(3,3),(2,4)],   -- after one iteration
      [(5,2),(1,2),(4,3),(2,3), ... -- after two iterations
      ...
    ]

现在in3可能被写成

in3 xs = moves !! 3
  where moves = iterate (concatMap moveKnight) xs