我想创建一个可以折叠多种输入的通用函数(请参阅 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_
)的数据上定义它,它并不能回答最初的问题。
最佳答案
因此,我们的目标是使用 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''
当然,这个等式推理不会告诉您任何有关您感兴趣的性能属性的信息。
关于haskell - 如何使用foldr/foldl定义foldM(如果可能的话)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12880989/