交错列表功能

Question

让我们说我有两个功能:

f :: [a] -> b
g :: [a] -> c

我想写一个与此相当的函数:

h x = (f x, g x)

但是当我这样做时,对于大型列表,我不可避免地会耗尽内存.

一个简单的例子如下:

x = [1..100000000::Int] 
main = print $ (sum x, product x)

我理解这种情况是因为列表x存储在内存中而没有被垃圾回收.这将是最好的,而不是f与g工作有关x的,那么,"平行".

假设我不能改变f和g,也不要打一个单独的副本x(假设x生产成本很高)我怎么能写h,而不会在内存不足的问题？

Answer 1

简短的回答是你不能.由于您无法控制f和g,因此无法保证函数按顺序处理其输入.这样的函数也可以在产生最终结果之前将整个列表保存在存储器中.

但是,如果您的函数表示为折叠,则情况会有所不同.这意味着我们知道如何逐步应用每个步骤,因此我们可以在一次运行中并行化这些步骤.

关于这个领域有很多资源.例如:

• Haskell:我可以在同一个懒惰列表上执行多次折叠而不将列表保留在内存中吗？
• 经典美丽折叠
• 更美丽的折叠拉链

消耗具有适当定义的空间边界的一系列值的模式通常使用管道类库(例如管道,迭代器或管道)来解决.例如,在管道中,您可以将计算总和与产品的组合表示为

import Control.Monad.Identity
import Data.Conduit
import Data.Conduit.List (fold, sourceList)
import Data.Conduit.Internal (zipSinks)

product', sum' :: (Monad m, Num a) => Sink a m a
sum'     = fold (+) 0
product' = fold (*) 1

main = print . runIdentity $ sourceList (replicate (10^6) 1) $$
                                zipSinks sum' product'

Answer 2

您可以使用多个线程来f x并行评估g x。

例如

x :: [Int]
x = [1..10^8]

main = print $ let a = sum x
                   b = product x
               in a `par` b `pseq` (a,b) 

这是利用 GHC 并行运行时通过同时执行两件事来防止空间泄漏的好方法。

或者，您需要将f和融合g到单通道中。