Haskell:用do-notation定义foldM

Question

我对在do块中定义foldM感到困惑，主要是因为它的递归。foldM的标准定义如下：

foldM             :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM _ a []      =  return a
foldM f a (x:xs)  =  f a x >>= \fax -> foldM f fax xs

我理解这个定义；f a x的结果递归地传递到一个新的foldM函数中，直到列表为空。以下是do-block中foldM的定义(从我的uni课程材料中复制)：

foldM _ z []     = return z
foldM f z (x:xs) = do r <- foldM f z xs
                      f r x

我知道do块的定义基本上是绑定(>>=)操作的语法糖。然而，我似乎不能理解这个定义是如何工作的。我发现do块中的递归整体上非常令人困惑。r得到了什么？当每次递归调用都向foldM传递z时，递归行r <- foldM f z xs怎么可能是正确的呢？是否应该像f z x一样传递递归更新的参数，就像在带有(>>=)的foldM定义中那样

Answer 1

后一个变体从右到左评估列表上的操作，而另一个变体从右到左评估列表上的操作。让我们称后者为foldMDo，这样我们就可以将它们分开：

foldM             :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM _ a []      =  return a
foldM f a (x:xs)  =  f a x >>= \fax -> foldM f fax xs

foldMDo _ z []     = return z
foldMDo f z (x:xs) = do r <- foldMDo f z xs
                      f r x

如果我们使用它们来打印一个列表，区别是显而易见的：

ghci> foldM (\_ y -> print y) () [1..10]
1
2
3
4
5
6
7
8
9
10

ghci> foldMDo (\_ y -> print y) () [1..10]
10
9
8
7
6
5
4
3
2
1

因此，让我们对do变体进行去垃圾处理：

do r <- foldMDo f z xs
   f r x

等同于

foldMDo f z xs >>= \fzxs -> f fzxs x

让我们将这个与相邻的另一个进行比较：

(1) f a x          >>= \fax  -> foldM f fax  xs
(2) foldMDo f z xs >>= \fzxs ->       f fzxs x

我们可以将其与具有显式let...in的foldl和foldr进行比较

foldr f a (x:xs) = let acc = foldr f a xs
                   in f a acc
foldl f a (x:xs) = let acc = f a x
                   in foldr f acc xs

uni材质看起来像foldr，而默认材质看起来像foldl，这与求值顺序一样。

为了完成任务，让我们添加foldM的do版本

foldM f a (x:xs) = do fax <- f a x
                      foldM f fax xs

TL;DR

你的uni课程材料没有实现foldM，因为它不是从左到右的评估，而是从右到左的评估。本质上，