4

我想制作一个通用函数，可以折叠各种输入（请参阅使单个函数适用于列表、字节字符串和文本（可能还有其他类似的表示形式））。正如一个答案所建议的那样，ListLike就是为了这个。它的FoldableLL类为任何可折叠的东西定义了一个抽象。但是，我需要一个单子折叠。所以我需要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)

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

我有一种感觉，问题在于一元计算是以错误的顺序组成的——就像((... >>= ...) >>= ...)不是，(... >>= (... >>= ...))但到目前为止我还没有找到解决方法。

解决方法：由于ListLike暴露mapM_，我通过将累加器包装到状态单子中来构建 s foldM：ListLike

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_）的数据上定义它。

4

1 回答 1

8

所以目标是foldM使用foldror重新实现foldl。应该是哪一个？我们希望延迟处理输入并允许无限列表，这排除了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''

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

于 2012-10-14T10:04:53.480 回答