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

Question

我想创建一个折叠广泛输入的泛型函数(请参阅使单个函数在列表,ByteStrings和文本(以及可能的其他类似表示)上工作).正如一个答案所暗示的那样,ListLike就是为了这个.它的FoldableLL类为任何可折叠的东西定义了一个抽象.但是,我需要一个monadic折叠.所以我需要foldM用foldl/ 来定义foldr.

到目前为止,我的尝试失败了.我试着定义

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)

它会占用所有内存并失败.

我有一种感觉,问题是monadic计算是按错误的顺序组成的 - ((... >>= ...) >>= ...)而不是(... >>= (... >>= ...))到目前为止我没有找到如何解决它.

---

解决方法:由于ListLike自曝mapM_,我构造foldM上ListLikeS按缠绕蓄能器进入状态单子:

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

所以,我们的目标是重新实现foldM使用两种foldr或foldl.应该是哪一个？我们希望懒惰地处理输入并允许输入infinte列表,这排除了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''

当然,这种等式推理并不能告诉您关于您感兴趣的性能属性的任何信息.