Haskell：在do-notation中定義foldM

Question

我很困惑在do-block中定義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函數，直到列表爲空。這裏是一個做塊的foldM定義（從我的UNI課程材料複製）：

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

我知道do塊的定義基本上是綁定(>>=)操作語法糖。但是，我似乎無法理解這個定義是如何工作的。我發現do-blocks中的遞歸非常混亂。什麼給r？遞歸線r <- foldM f z xs如何通過foldM傳遞z每次遞歸調用？不應該像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 

那麼，讓我們desugar的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 

我們可以比較，爲foldl和foldr有明確let...in：

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 

單向材料看起來像foldr，而默認的一個看起來像foldl，因爲它與評估順序預期相同。

而完成，讓我們添加do版本的foldM的：

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

TL; DR

你的單教材沒有實現foldM，因爲它不會做從左正確的評估，而是從右到左。本質上，