6

以下があるとしましょう。

l = map f (map g [1..100])

そして、私たちはやりたいです:

head l

したがって、次のようになります。

head (map f (map g [1..100]))

ここで、この最初の要素を取得する必要があります。map次のように定義されています。

map f l = f (head l) : (map f (tail l))

したがって、次のようになります。

f (head (map g [1..100]))

そして、再度適用しました:

f (g (head [1..100]))

その結果、

f (g 1)

単純に怠惰なため、中間リストは形成されません。

この分析は正しいですか?そして、次のような単純な構造を使用します。

foldl' ... $ map f1 $ map f2 $ createlist

「リストの融合」がなくても、中間リストが作成されることはありますか? (怠惰はそれらを簡単に排除すべきだと思います)。


リストを保持する理由を確認できる唯一の場所は、そうしたかどうかです。

l' = [1..100]
l = map f (map g l')

を他の場所で使用する場合、保持したいl'場所。ただし、l'上記の場合、コンパイラーが上記のリストを保存するよりも再計算する方が速いことに気付くのはかなり簡単です。

4

2 に答える 2

7

あなたのmap例では、リストセルが作成され、すぐにガベージコレクションされます。リストフュージョンでは、GC やサンクの操作 (どちらも無料ではない) は必要ありません。

于 2012-06-08T08:45:43.780 に答える
7

Fusion は、中間データ構造が高価な場合に最もメリットがあります。渡される構造が遅延しており、シーケンシャルにアクセスされる場合、構造は比較的安価になる可能性があります (リストの場合のように)。

  • 怠惰な構造の場合、フュージョンはサンクを作成する一定の要因を取り除き、すぐにそれをガベージ コレクションします。
  • 厳密な構造の場合、融合はO(n)作業を削除できます。

したがって、最大の利点は、厳密な配列および同様の構造の場合です。ただし、遅延リストを融合しても、サンクとして割り当てられる中間構造が少なくなるため、データの局所性が向上するため、依然として有利です。

于 2012-06-08T11:49:40.043 に答える