インテリジェント純粋に機能的なセット

Question

ユニオン、交差点、および相違点で構成される設定計算は、多くの場合、さまざまな方法で表現できます。ある答えに達するのに必要な計算量を最小限にしようとする理論や具体的な実装はありますか？

例えば、アモルファス材料のシミュレーションで原子を分解して隣のシェルに分解しようとすると、最初に実際に適用されました。ここで、最初のシェルは特定の起点原子のすぐ隣にあり、ない最初のシェルまたはその前のいずれかの最初のシェルの隣接している原子：

nth 0 = singleton i 
nth 1 = neighbors i 
nth n = reduce union (map neighbors (nth(n-1))) - nth(n-1) - nth(n-2) 

これを解決するために、多くの異なる方法があります。結果を構成する間に各セットのメンバシップを段階的にテストしたり、3つの隣接シェルの結合を計算したり、交差を使用して、最も外側にある2つのシェルを削除することができます。実際には、大きな中間セットの構築を必要とするソリューションは遅くなります。おそらくインテリジェントセット実装は、評価される式を構成し、次にそれを評価して性能を向上させるためにそれを最適化する（例えば中間セットのサイズを縮小する）ことができる。そのような実装は存在しますか？

Answer 1

あなたの質問は、すぐにthis paperに記載されているハスケルのストリーム融合のことを私に思い出させました。一般的な原則は簡単に要約することができます：リストを保存する代わりに、リストを作成する方法を保存します。リスト変換関数はリストジェネレータで直接操作されます。つまり、すべての演算が中間構造なしでデータの単一世代に融合します。その後、操作を合成したら、ジェネレータを実行してデータを生成します。

あなたの質問に対する答えは、計算を融合し中間のデータ構造を取り除く同様のインテリジェントなメカニズムが必要な場合は、セットを「共構造」に変換する方法を見つける必要があるということですそれを紙と呼んでいます）がセットを生成し、それを直接操作してから、実際にセットを生成します。

このコンセプトの背後には、紙のヒントはありますが、決して綴られないという非常に深い理論があると思います。私がやっていることとは非常に関係しているので、 、あまりにも！