8

2つの機能が与えられたとしましょう：

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

fandを変更できずg、別のコピーを作成したくないx場合 (作成に費用がかかると仮定) 、メモリ不足の問題に遭遇することなくxどのように書き込むことができますか?h

4

3 に答える 3

12

簡単に言えば、できません。fとを制御できないためg、関数が入力を順番に処理するという保証はありません。このような関数は、最終結果を生成する前にリスト全体をメモリに保存しておくこともできます。

ただし、関数が折り畳みで表現されている場合は状況が異なります。これは、各ステップを段階的に適用する方法を知っていることを意味するため、これらのステップを 1 回の実行で並列化できます。

この分野に関する多くのリソースがあります。例えば：

適切に定義された空間境界を持つ一連の値を消費するパターンは、より一般的には、 conduit、iteratees、またはpipesなどのパイプのようなライブラリで解決されます。たとえば、conduitでは、合計と積の計算の組み合わせを次のように表現できます。

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'
于 2013-06-05T08:08:18.577 に答える