4

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

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 回答