Difference list とは

コンピュータ科学において、用語差分リストは、リストを表すための2つのデータ構造のうちの1つを参照することができる。これらのデータ構造の1つには2つのリストがあり、それらの2つのリストの違いを表しています。第2のデータ構造は、効率的な連結操作を伴うリストの機能的表現である。第2のアプローチでは、差分リストは単一引数の関数として実装されます。関数は、引数としてリストを取り、そのリストの前に追加します。結果として、第2のタイプの差異リストの連結は、基本的に関数合成として実装され、O(1)である。しかし、もちろん、リストは、最終的には(すべての要素が必要であると仮定して)構築されなければなりません。これは明らかに少なくともO(n)です。