如何使用foldr/foldl定義foldM（如果可能的話）？

Question

我想要製作一個通用函數，可以在各種輸入上進行摺疊（請參閱Making a single function work on lists, ByteStrings and Texts (and perhaps other similar representations)）。由於one answer suggested，ListLike只是爲此。它的FoldableLL類定義了一個可摺疊的抽象。但是，我需要一個單一的摺疊。所以我需要根據foldl/foldr來定義foldM。

到目前爲止，我的嘗試失敗了。我試圖定義

foldM'' :: (Monad m, LL.FoldableLL full a) => (b -> a -> m b) -> b -> full -> m b 
foldM'' f z = LL.foldl (\acc x -> acc >>= (`f` x)) (return z) 

但是它在大輸入上運行內存不足 - 它構建了一個很大的未計算的計算樹。例如，如果我傳遞一個大文本文件到

main :: IO() 
main = getContents >>= foldM'' idx 0 >> return() 
    where 
    -- print the current index if 'a' is found 
    idx !i 'a' = print i >> return (i + 1) 
    idx !i _ =   return (i + 1) 

它吃掉所有內存並失敗。

我有一種感覺，問題是單子計算的順序是錯誤的 - 例如((... >>= ...) >>= ...)而不是(... >>= (... >>= ...))，但到目前爲止我還沒有找到如何解決這個問題。

---

解決方法：由於ListLike暴露mapM_，我就ListLike S按包裝累加器進入狀態單子構建foldM：

modifyT :: (Monad m) => (s -> m s) -> StateT s m() 
modifyT f = get >>= \x -> lift (f x) >>= put 

foldLLM :: (LL.ListLike full a, Monad m) => (b -> a -> m b) -> b -> full -> m b 
foldLLM f z c = execStateT (LL.mapM_ (\x -> modifyT (\b -> f b x)) c) z 

雖然這適用於大型數據集精緻，它不是很不錯。如果可以在FoldableLL（沒有mapM_）的數據上定義它，它不會回答原始問題。

Answer 1

因此，我們的目標是使用foldr或foldl重新實現foldM。它應該是哪一個？我們希望輸入被懶惰地處理並允許無限列表，這就排除了foldl。所以foldr會是。

所以這裏是從標準庫中定義的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 

的是要記住的是foldr其參數只需在列表取代[]和:（ListLike摘要過這一點，但它仍然作爲一個指導原則）。

那麼[]應該換成什麼？很明顯用return a。但a從哪裏來？它不會是最初的a傳遞給foldM - 如果列表不爲空，則當foldr到達列表末尾時，累加器應該已經改變。因此，我們用一個函數取代[]，函數使用累加器並將其返回到底層monad：\a -> return a（或簡單地return）。這也給出foldr將計算的東西的類型：a -> m a。

我們應該用什麼來代替:？它需要是一個函數b -> (a -> m a) -> (a -> m a)，獲取列表的第一個元素，處理後的尾部（當然是懶洋洋地）以及當前的累加器。我們可以通過從上面的代碼中獲取提示來了解它：它將是\x rest a -> f a x >>= rest。因此，我們的foldM實施將是（調整型變量的代碼匹配它們上面）：

foldM'' :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a 
foldM'' f z list = foldr (\x rest a -> f a x >>= rest) return list z 

事實上，現在你的程序會消耗隨意性較大輸入，吐出的結果，當您去。

我們甚至可以歸納地證明這些定義在語義上是相等的（儘管我們可能應該採用聯合誘導或誘導來迎合無限列表）。

我們要展示

foldM f a xs = foldM'' f a xs 

所有xs :: [b]。對於xs = []我們

foldM f a [] 
≡ return a  -- definition of foldM 
≡ foldr (\x rest a -> f a x >>= rest) return [] a -- definition of foldr 
≡ foldM'' f a [] -- definition of foldM'' 

，並假設我們有它xs，我們展示它x:xs：

foldM f a (x:xs) 
≡ f a x >>= \fax -> foldM f fax xs --definition of foldM 
≡ f a x >>= \fax -> foldM'' f fax xs -- induction hypothesis 
≡ f a x >>= \fax -> foldr (\x rest a -> f a x >>= rest) return xs fax -- definition of foldM'' 
≡ f a x >>= foldr (\x rest a -> f a x >>= rest) return xs -- eta expansion 
≡ foldr (\x rest a -> f a x >>= rest) return (x:xs) -- definition of foldr 
≡ foldM'' f a (x:xs) -- definition of foldM'' 

當然這個等式推理並不告訴你關於性能特性任何你有興趣。