haskell - 如何使用foldr/foldl定义foldM(如果可能的话)？

Question

我想创建一个可以折叠多种输入的通用函数(请参阅 Making a single function work on lists, ByteStrings and Texts (and perhaps other similar representations) )。如one answer suggested ，ListLike就是为了这个。它的FoldableLL类定义了任何可折叠的东西的抽象。但是，我需要一个单子(monad)折叠。所以我需要根据 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)

它耗尽了所有内存并失败。

我有一种感觉，问题在于单子(monad)计算是以错误的顺序组成的 - 例如 ((... >>= ...) >>= ...) (... >>= (... >>= ...)) 但到目前为止我还没有找到如何修复它。

<小时/>

解决方法:由于 ListLike 公开 mapM_，我在 ListLike 上构造了 foldM通过将累加器包装到状态单子(monad)中来实现:

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从哪里来呢？它不会是传递给 foldM 的初始 a – 如果列表不为空，当 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''

当然，这个等式推理不会告诉您任何有关您感兴趣的性能属性的信息。