Loading article…
コンピューティングにおいて、永続データ構造または非一時的データ構造とは、変更されても常に以前のバージョンを保持するデータ構造のことです。このようなデータ構造は、操作によって構造が（目に見える形で）その場で更新されるのではなく、常に新しい更新された構造が生成されるため、実質的に不変です。この用語は、Driscoll、Sarnak、Sleator、およびTarjanによる1986年の論文で導入されました。[ 1 ]
データ構造は、すべてのバージョンにアクセスできるが、最新バージョンのみを変更できる場合、部分的に永続的である。すべてのバージョンにアクセスでき、かつ変更できる場合、データ構造は完全に永続的である。また、2 つの以前のバージョンから新しいバージョンを作成できる meld または merge 操作がある場合、データ構造は合流的に永続的と呼ばれる。永続的でない構造は、一時的と呼ばれる。[ 2 ]
これらのタイプのデータ構造は、論理プログラミングや関数型プログラミングで特に一般的です。[ 2 ]これらのパラダイムの言語では、可変データの使用が推奨されない（または完全に禁止される）ためです。
部分的永続性モデルでは、プログラマはデータ構造の以前のバージョンを照会できますが、最新バージョンのみを更新できます。これは、データ構造の各バージョン間に線形順序があることを意味します。 [ 3 ]完全永続性モデルでは、データ構造のどのバージョンに対しても更新と照会の両方が許可されます。ロープデータ構造の場合のように、データ構造の古いバージョンの照会または更新のパフォーマンス特性が低下することが許容される場合があります。[ 4 ]さらに、データ構造は、完全永続性に加えて、同じデータ構造の 2 つのバージョンを組み合わせて、依然として完全永続性を持つ新しいバージョンを形成できる場合、合流的に永続的であると言えます。[ 5 ]
永続的なデータ構造を作成する方法の1つは、プラットフォームが提供する一時的なデータ構造（配列など）を使用してデータをデータ構造に格納し、そのデータ構造全体をコピーすることです。これは、書き込みごとに基となるデータ構造全体をコピーする必要があるため、非効率的な手法であり、最悪の場合にはサイズnの配列のm 回の変更に対するパフォーマンス特性。 コピーオンライトメモリ管理により、更新のコストを削減できます。にここで、Bはメモリブロックサイズ、uは操作で更新されるページ数である。
ファットノード方式では、ノードフィールドに加えられたすべての変更を、フィールドの古い値を消去することなく、ノード自体に記録します。この方式では、ノードが任意に「ファット」になることが許容されます。つまり、各ファットノードは、エフェメラルノードと同じ情報とポインタフィールドに加え、任意の数の追加フィールド値を格納する領域を持ちます。各追加フィールド値には、関連付けられたフィールド名と、指定された値を持つように名前付きフィールドが変更されたバージョンを示すバージョンスタンプがあります。さらに、各ファットノードには、ノードが作成されたバージョンを示す独自のバージョンスタンプがあります。ノードにバージョンスタンプを持たせる唯一の目的は、各ノードがバージョンごとにフィールド名ごとに1つの値のみを含むようにすることです。構造内をナビゲートするために、ノード内の各元のフィールド値にはバージョンスタンプがゼロになっています。
ファットノード方式を使用すると、変更ごとに O(1) のスペースが必要になります。新しいデータを格納するだけです。変更履歴の最後に変更を格納するために、各変更には O(1) の追加時間がかかります。これは、変更履歴が拡張可能な配列に格納されていると仮定した場合の償却時間です。アクセス時には、構造を走査しながら各ノードで正しいバージョンを見つける必要があります。m 回の変更が行われる場合、各アクセス操作には配列内の最も近い変更を見つけるコストによって、処理速度が低下します。あるいは、各ノードでファン・エムデ・ボアス木（ハッシュを使用したスペース効率の良いバージョン）を使用して、アクセス時間を短縮できます。更新時間の増加という代償を伴うが部分的な永続性のみが必要な場合、更新にかかる時間は、ランダム化と償却を除いて、元の桁数に維持できます（ファットノードへの単一の更新にかかる時間は、期待値で償却できるため）。[ 6 ]）。
このメソッドは、データ構造がノードの連結グラフであることを前提としています。更新時には、変更対象となるノードへのパス上のすべてのノードのコピーが作成されます。これらの変更は、データ構造全体に連鎖的に反映される必要があります。つまり、古いノードを指していたすべてのノードは、新しいノードを指すように変更されなければなりません。これらの変更によってさらに連鎖的な変更が発生し、ルートノードに到達するまでこのプロセスが繰り返されます。
m 回の変更では、加算的な検索時間は O(log m) かかります。変更時間と空間は、データ構造内の任意のノードの最大祖先数に、一時データ構造の更新コストを掛けた値によって制限されます。親ポインタのないバランス型二分探索木では、最悪の場合の変更時間計算量は O(log n + 更新コスト) です。ただし、リンクリストでは、最悪の場合の変更時間計算量は O(n + 更新コスト) です。
Driscoll、Sarnak、Sleator、Tarjanは[ 1 ]、ファットノードとパスコピーの技術を組み合わせる方法を考案し、変更ごとにO(1)のアクセス速度低下とO(1)の償却オーバーヘッド（空間と時間）を実現しました。彼らの方法は、各ノードへの入力ポインタが最大d個であるリンクデータ構造を想定しており、dは既知の定数です。
各ノードには、変更ボックスが1つ格納されます。このボックスには、ノードに対する1つの変更（ポインタ、ノードのキー、またはその他のノード固有のデータのいずれかに対する変更）と、その変更が適用された日時を示すタイムスタンプが格納されます。初期状態では、すべてのノードの変更ボックスは空です。
ノードにアクセスするたびに、変更ボックスがチェックされ、そのタイムスタンプがアクセス時刻と比較されます。（アクセス時刻は、対象となるデータ構造のバージョンを指定します。）変更ボックスが空の場合、またはアクセス時刻が変更時刻より前の場合は、変更ボックスは無視され、ノードの通常の部分のみが考慮されます。一方、アクセス時刻が変更時刻より後の場合は、変更ボックスの値が使用され、ノード内の値が上書きされます。
ノードの変更は次のように行われます。（各変更は、1つのポインタまたは類似のフィールドに影響を与えるものと想定されます。）ノードの変更ボックスが空の場合は、変更内容がボックスに格納されます。そうでない場合は、変更ボックスが満たされます。ノードのコピーが作成されますが、最新の値のみが使用されます。変更ボックスを使用せずに、新しいノードに対して直接変更が実行されます。（新しいノードのフィールドの1つが上書きされ、変更ボックスは空のままになります。）最後に、パスのコピーと同様に、この変更がノードの親にカスケードされます。（これには、親の変更ボックスへの入力、または親の再帰的なコピーの作成が含まれる場合があります。ノードに親がない場合（つまり、ルートの場合）、新しいルートがルートのソート済み配列に追加されます。）
このアルゴリズムでは、任意の時刻 t において、時刻 t に対応するデータ構造内には、最大で 1 つの変更ボックスしか存在しません。したがって、時刻 t での変更によってツリーは 3 つの部分に分割されます。1 つの部分には時刻 t より前のデータ、1 つの部分には時刻 t より後のデータ、そして残りの 1 つの部分は変更の影響を受けません。
変更にかかる時間と空間については、償却分析が必要です。変更には償却空間 O(1) と償却時間 O(1) がかかります。その理由を理解するために、ポテンシャル関数ϕを使用します。ここで、ϕ (T) は T 内の完全なライブ ノードの数です。T のライブ ノードとは、現在の時刻 (つまり、最後の変更後) に現在のルートから到達可能なノードのことです。完全なライブ ノードとは、変更ボックスが満杯になっているライブ ノードのことです。
各変更には、 k個のコピーと、それに続く 1 つの変更ボックスが含まれます。k 個のコピーそれぞれについて考えてみましょう。それぞれは O(1) のスペースと時間を要しますが、ポテンシャル関数を 1 つ減らします。(まず、コピーされるノードは満杯で生存している必要があり、ポテンシャル関数に寄与します。ただし、ポテンシャル関数は、古いノードが新しいツリーで到達不可能な場合にのみ減少します。しかし、新しいツリーでは到達不可能であることがわかっているので、アルゴリズムの次のステップでは、ノードの親を変更してコピーを指すようにします。最後に、コピーの変更ボックスが空であることがわかっています。したがって、満杯の生存ノードが空の生存ノードに置き換えられ、ϕ は1 つ減少します。) 最後のステップでは、変更ボックスを埋めます。これには O(1) の時間が要し、ϕ は1 つ増加します。
これらをまとめると、ϕの変化はΔϕ = 1 − kとなる。したがって、このアルゴリズムはO( k + Δϕ ) = O(1)の空間とO( k + Δϕ + 1) = O(1)の時間を必要とする。
パスコピーは、バイナリサーチツリーなどの特定のデータ構造で永続性を実現するための簡単な方法の 1 つです。任意のデータ構造で機能する永続性を実装するための一般的な戦略があると便利です。それを実現するために、有向グラフGを考えます。Gの各頂点vには、ポインタで表される一定数cの出エッジがあると仮定します。各頂点には、データを表すラベルがあります。頂点には、 inedges( v )と定義される、d個のエッジが流入しているとします。G に対して、次の異なる操作を許可します。
上記の操作はいずれも特定の時間に実行され、永続グラフ表現の目的は、任意の時点でのGの任意のバージョンにアクセスできるようにすることです。この目的のために、 Gの各頂点vに対してテーブルを定義します。テーブルにはc列と行。各行には、出力エッジへのポインタに加えて、頂点のデータを表すラベルと操作が実行された時刻tが含まれます。さらに、vへのすべての入力エッジを追跡する配列 inedges( v ) があります。テーブルがいっぱいになると、新しいテーブルが作成されます。行を作成できます。古いテーブルは非アクティブになり、新しいテーブルがアクティブになります。
CREATE-NODE を呼び出すと、新しいテーブルが作成され、すべての参照が null に設定されます。
CHANGE-EDGE( v , i , u ) が呼び出されると仮定すると、考慮すべきケースが 2 つあります。
これはCHANGE-EDGEと全く同じように動作しますが、頂点のi番目のエッジを変更する代わりに、i番目のラベルを変更します。
上記で提案したスキームの効率性を評価するために、クレジットスキームとして定義された引数を使用します。クレジットは通貨を表します。例えば、クレジットはテーブルの支払いに使用できます。この引数は次のように定義されます。
クレジットスキームは常に以下の不変条件を満たす必要があります。各アクティブテーブルの各行には1つのクレジットが格納され、テーブルのクレジット数は行数と同じです。この不変条件がCREATE-NODE、CHANGE-EDGE、CHANGE-LABELの3つの操作すべてに適用されることを確認しましょう。
まとめると、CREATE_NODE の呼び出しとCHANGE_EDGE への呼び出しにより、テーブル。各テーブルにはサイズがあります。再帰呼び出しを考慮しない場合、テーブルを埋めるにはしたがって、一連の操作を完了するために必要な作業量は、作成されたテーブルの数に、各アクセス操作は、また、 m個のエッジとラベルの操作があるため、結論として、CREATE-NODE、CHANGE-EDGE、CHANGE-LABELの任意のnシーケンスとmアクセス操作を完了できるデータ構造が存在する。。
永続化を利用して効率的に解決できる便利なアプリケーションの1つに、次要素検索があります。x軸に平行で互いに交差しないn本の線分があるとします。点pを照会し、 pの上にある線分（存在する場合）を返すデータ構造を構築したいと考えています。まず、単純な方法で次要素検索を解決し、次に永続化データ構造を使用して解決する方法を示します。
まず、無限遠から始まる垂直線分から始め、線分を左から右へ掃引します。これらの線分の終点に到達するたびに一時停止します。垂直線は平面を垂直な帯に分割します。線分がn個ある場合、各セグメントには垂直ストリップがあるため2つの端点。どのセグメントもストリップ内で開始および終了しません。すべてのセグメントは、ストリップに接しないか、完全にストリップを横切ります。セグメントは、上から下へ何らかの順序で並べられたオブジェクトと考えることができます。私たちが気にするのは、私たちが見ている点がこの順序のどこに位置するかです。セグメントの端点をx座標でソートします。各ストリップについて交差する部分集合セグメントを保存します辞書に格納します。垂直線が線分を走査する際、線分の左端点を通過するたびに、それを辞書に追加します。線分の右端点を通過するたびに、それを辞書から削除します。各端点で辞書のコピーを保存し、すべてのコピーをx座標でソートして格納します。このようにして、あらゆるクエリに応答できるデータ構造が得られます。点pの上にある線分を見つけるには、 pのx座標を見て、それがどのコピーまたはストリップに属するかを知ることができます。次に、y座標を見て、その上にある線分を見つけます。したがって、ストリップまたはコピーを見つけるためのx座標のバイナリサーチと、その上にある線分を見つけるためのy座標のバイナリサーチの2つのバイナリサーチが必要です。したがって、クエリ時間はこのデータ構造では、スペースが問題となります。セグメントが、他のどのセグメントの終了よりも前に開始するように構成されていると仮定すると、単純な方法を使用して構造を構築するために必要なスペースは次のようになります。それでは、同じクエリ時間でより優れたメモリ容量を持つ、別の永続データ構造を構築する方法を見ていきましょう。
ナイーブな方法で使用されるデータ構造で実際に時間がかかるのは、ストリップから次のストリップに移動するたびに、ソートされた順序を維持するために使用するデータ構造のスナップショットを取得する必要があるためです。交差するセグメントを取得すると、私たちがどちらか一方が去るか、どちらか一方が入るかのどちらかです。そして、その中には何があるのでしょうか挿入または削除が1つだけの場合、すべてをコピーするのは良い考えではありませんにコツは、各コピーが前のコピーと挿入または削除が 1 つだけ異なるため、変更された部分だけをコピーすればよいということです。T をルートとするツリーがあると仮定します。ツリーにキーkを挿入すると、 kを含む新しいリーフが作成されます。ツリーを再平衡化するために回転を実行すると、kからTへのパスのノードのみが変更されます。ツリーにキーkを挿入する前に、 kからTへのパス上のすべてのノードをコピーします。これで、 k を含まない元のツリーと、 k を含みルートがTのルートのコピーである新しいツリーの 2つのバージョンができました。k からTへのパスをコピーしても挿入時間は定数倍以上増加しないため、永続データ構造への挿入は時間。削除するには、削除によって影響を受けるノードを見つける必要があります。削除によって影響を受ける各ノードvについて、ルートからvへのパスをコピーします。これにより、ルートが元のツリーのルートのコピーである新しいツリーが作成されます。次に、新しいツリーに対して削除を実行します。最終的に、ツリーの 2 つのバージョンが得られます。kを含む元のツリーと、 k を含まない新しいツリーです。削除はルートからvへのパスのみを変更し、適切な削除アルゴリズムは時間で実行されるため、したがって、永続データ構造における削除には挿入と削除のシーケンスごとに、一連の辞書、バージョン、またはツリーが作成されます。それぞれ操作の結果それぞれm個の要素が含まれている場合、各要素の検索は取るこの永続的なデータ構造を使用すると、次の要素の検索問題を解決できます。クエリ時間とスペースの代わりに以下に、次の検索問題に関連する例のソースコードを示します。
純粋関数型データ構造は自動的に永続化されます。おそらく最も単純な永続化データ構造は、単方向連結リスト、またはconsベースのリストでしょう。これは、各要素がリスト内の次の要素への参照を持つ単純なオブジェクトのリストです。リストの末尾（つまり、あるkの最後のk個の要素）を取得し、その前に新しいノードを追加できるため、永続化されます。末尾は複製されず、古いリストと新しいリストの間で共有されます。末尾の内容が不変である限り、この共有はプログラムからは見えません。
赤黒木[ 7 ] 、スタック[ 8 ]、トレアプ[ 9 ]など、多くの一般的な参照ベースのデータ構造は、永続バージョンを作成するために簡単に適応できます。キュー、デキュー、および最小要素を返す追加のO(1)操作minを持つmin-dequesや、準線形、多くの場合対数的な複雑さを持つ追加のランダムアクセス操作を持つランダムアクセスdequesなどの拡張機能など、もう少し手間がかかるものもあります。
不変な（「純粋関数型」の）構造に基づいた永続的なデータ構造は、破壊的な更新（突然変異）を使用し、上記で説明したファットノードまたはパスコピー技術を使用して永続化される構造とは対照的である。
単方向連結リストは、関数型言語における基本的なデータ構造です。[ 10 ] HaskellのようなML派生言語の中には、リスト内のノードが一度割り当てられると、変更できず、コピー、参照、または参照がなくなったときにガベージ コレクタによって破棄されるだけなので、純粋に関数型言語と言えます。（ML 自体は純粋に関数型言語ではありませんが、非破壊的なリスト操作のサブセットをサポートしており、これはSchemeやRacketのようなLisp (リスト処理) 関数型言語の方言にも当てはまります。）
以下の2つのリストを検討してください。
xs = [0, 1, 2] ys = [3, 4, 5]
これらはメモリ上で以下のように表現されます。
ここで、円はリスト内のノードを示し（矢印はノードの2番目の要素を表し、それは別のノードへのポインタである）。
次に、2つのリストを連結します。
zs = xs ++ ys
結果として、以下のメモリ構造が生成されます。
リスト内のノードはxsコピーされていますが、リスト内のノードysは共有されていることに注意してください。その結果、元のリスト（xsおよびys）はそのまま残り、変更されていません。
コピーの理由は、xs（元の値を含むノード2）の最後のノードを の先頭を指すように変更できないためですys。なぜなら、そうすると の値が変更されてしまうからですxs。
二分探索木[ 10 ]を考えてみましょう。この木では、すべてのノードが再帰的不変条件を持ち、左部分木に含まれるすべてのサブノードはノードに格納されている値以下であり、右部分木に含まれるサブノードはノードに格納されている値より大きい値を持つとします。
例えば、データセット
xs = [a, b, c, d, f, g, h]
これは、以下の二分探索木で表すことができるかもしれません。
二分木にデータを挿入し、不変条件を維持する 関数は次のとおりです。
fun insert ( x , E ) = T ( E , x , E ) | insert ( x , s as T ( a , y , b )) = if x < y then T ( insert ( x , a ), y , b ) else if x > y then T ( a , y , insert ( x , b )) else s実行後
ys = insert ("e", xs)以下の構成が生成されます。
2つの点に注目してください。1つ目は、元のツリー（xs）が存続することです。2つ目は、古いツリーと新しいツリーの間で多くの共通ノードが共有されていることです。このような永続性と共有は、有効な参照を持たないノードを自動的に解放する何らかのガベージコレクション（GC）なしでは管理が難しく、これが関数型プログラミング言語でGCがよく見られる理由です。
永続ハッシュ配列マップトライは、更新時に以前のバージョンを保持するハッシュ配列マップトライの特殊なバリアントです。これは、汎用的な永続マップデータ構造を実装するためによく使用されます。[ 11 ]
ハッシュ配列マップドトライは、もともとPhil Bagwellによる2001年の論文「Ideal Hash Trees」で説明されました。この論文では、可変ハッシュテーブルが提示されており、「挿入、検索、削除の時間は小さく一定で、キーセットのサイズに関係なく、操作はO(1)です。挿入、検索、削除操作の最悪時間は小さく保証され、ミスは検索成功よりもコストが低くなります」。[ 12 ]このデータ構造はその後、 Clojureプログラミング言語で使用するためにRich Hickeyによって完全に永続化するように変更されました。[ 13 ]
概念的には、ハッシュ配列マップドトライは、ノードを階層的に格納し、特定の要素へのパスをたどって取得するという点で、一般的なツリーと似た動作をします。主な違いは、ハッシュ配列マップドトライでは、まずハッシュ関数を使用してルックアップキーを（通常32ビットまたは64ビットの）整数に変換することです。次に、その整数のバイナリ表現のスライスを使用して、ツリーの各レベルの疎配列にインデックスを付けることで、ツリーを下るパスが決定されます。ツリーのリーフノードは、ハッシュテーブルの構築に使用されるバケットと同様の動作をし、ハッシュ衝突に応じて複数の候補を含む場合と含まない場合があります。[ 11 ]
永続ハッシュ配列マップトライのほとんどの実装では、実装に32の分岐係数を使用しています。これは、実際には、永続ハッシュ配列マップトライへの挿入、削除、およびルックアップの計算複雑度がO (log n )であるにもかかわらず、ほとんどのアプリケーションでは実質的に定数時間であることを意味します。これは、どの操作でも12ステップ以上かかるようにするには、非常に多くのエントリが必要になるためです。[ 14 ]
Haskellは純粋関数型言語であるため、ミューテーションは許可されません。したがって、関数型セマンティクスを持つデータ構造の以前の状態を保持しないことは不可能であるため、この言語のすべてのデータ構造は永続的です。[ 15 ]これは、データ構造の以前のバージョンを無効にするようなデータ構造への変更は、参照透過性に違反するためです。
Haskellの標準ライブラリには、リンクリスト[ 16 ]、マップ（サイズバランスの取れたツリーとして実装）[ 17 ]、セット[ 18 ]などの効率的な永続実装が含まれています。[ 19 ]
Lispファミリーの多くのプログラミング言語と同様に、Clojureにはリンクリストの実装が含まれていますが、他の方言とは異なり、そのリンクリストの実装は慣例による永続化ではなく、強制的な永続化になっています。[ 20 ] Clojureには、永続ハッシュ配列マップトライに基づく、永続的なベクトル、マップ、セットの効率的な実装もあります。これらのデータ構造は、Javaコレクションフレームワークの必須の読み取り専用部分を実装しています。[ 21 ]
Clojure言語の設計者は、可変データ構造よりも永続データ構造の使用を推奨しています。永続データ構造は値セマンティクスを持ち、安価なエイリアスでスレッド間で自由に共有でき、簡単に作成でき、言語に依存しないという利点があるためです。[ 22 ]
これらのデータ構造は、データ競合を回避するための操作の容易な再試行とアトミックな比較と交換のセマンティクスを可能にするため、 Clojureの並列コンピューティングのサポートの基礎を形成します。[ 23 ]
Elmプログラミング言語はHaskellと同様に純粋関数型言語であり、必然的にすべてのデータ構造が永続的になります。リンクリストの永続的な実装に加え、永続的な配列、辞書、セットも含まれています。[ 24 ]
Elm は、Elm データの永続性を活用する独自の仮想 DOM実装を使用しています。2016 年時点で Elm の開発者は、この仮想 DOM により Elm 言語は人気のJavaScriptフレームワークであるReact、Ember、Angularよりも高速に HTML をレンダリングできると報告しました。[ 25 ]
Javaプログラミング言語は、特に関数型言語ではありません。それにもかかわらず、コア JDK パッケージ java.util.concurrent には、コピーオンライト技術を使用して実装された永続構造である CopyOnWriteArrayList と CopyOnWriteArraySet が含まれています。ただし、Java の一般的な並行マップ実装である ConcurrentHashMap は永続的ではありません。完全に永続的なコレクションは、サードパーティライブラリ[ 26 ]または他の JVM 言語で利用できます。
人気のJavaScriptフロントエンドフレームワークであるReactは、 Fluxアーキテクチャを実装する状態管理システムとよく併用されます。[ 27 ] [ 28 ]その代表的な実装の一つがJavaScriptライブラリのReduxです。ReduxライブラリはElmプログラミング言語で使用されている状態管理パターンに触発されており、すべてのデータを永続的なものとして扱うことをユーザーに義務付けています。[ 29 ]その結果、Reduxプロジェクトでは、特定のケースでは、強制的かつ効率的な永続データ構造のためのライブラリを使用することを推奨しています。これにより、通常のJavaScriptオブジェクトを比較したりコピーを作成したりする場合よりもパフォーマンスが向上すると報告されています。[ 30 ]
永続データ構造のライブラリの 1 つです。Immutable.js は、Clojure と Scala によって利用可能になり普及したデータ構造に基づいています。[ 31 ] Redux のドキュメントでは、強制的な不変性を提供できる可能性のあるライブラリの 1 つとして言及されています。[ 30 ] Mori.js は、Clojure と同様のデータ構造を JavaScript にもたらします。[ 32 ] Immer.js は、「現在の状態を変更することによって次の不変の状態を作成する」という興味深いアプローチをもたらします。 [ 33 ] Immer.js は、効率的な永続データ構造ではなくネイティブの JavaScript オブジェクトを使用するため、データサイズが大きい場合にパフォーマンスの問題が発生する可能性があります。
Prolog の項は本質的に不変であるため、データ構造は通常、永続的なデータ構造になります。そのパフォーマンスは、Prolog システムが提供する共有とガベージ コレクションに依存します。[ 34 ]非グラウンド Prolog 項への拡張は、探索空間の爆発のため、常に実行可能とは限りません。遅延目標は、この問題を軽減する可能性があります。
しかしながら、一部の Prolog システムでは setarg/3 のような破壊的な操作が提供されており、コピーの有無や状態変化のバックトラックの有無など、さまざまな種類がある。setarg/3 が制約ソルバーのような新しい宣言的レイヤーを提供する目的で使用されているケースもある。[ 35 ]
Scalaプログラミング言語は、「オブジェクト関数型スタイル」を使用してプログラムを実装するために、永続データ構造の使用を推奨しています。[ 36 ] Scalaには、リンクリスト、赤黒木、Clojureで導入された永続ハッシュ配列マップドトライなど、多くの永続データ構造の実装が含まれています。 [ 37 ]
永続データ構造は、データ構造の連続するバージョンが基となるメモリを共有するように実装されることが多いため[ 38 ]、このようなデータ構造を人間工学的に使用するには、一般的に参照カウントやマークアンドスイープなどの自動ガベージコレクションシステムが必要になります[ 39 ]。永続データ構造を使用するプラットフォームによっては、ガベージコレクションを使用しないという選択肢もありますが、そうするとメモリリークが発生する可能性がある一方で、場合によってはアプリケーション全体のパフォーマンスにプラスの影響を与えることもあります[ 40 ] 。
{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク){{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）