よくある、単純なデータ構造から始めましょう。苗字、名前、および考えるのに使っているプログラミング言語を保持する Person を考えます。

これで、Person 型の値 javaDierk を生成すれば自動的に不変データになるのです！

実際には、ここで登場している言語機能は二つあります。

ここまでで、三つの相異なる Person 型の値が得られました。変更のたびに新しいコピーが生成されています。あたかも「セッター」のように見える部分は、むしろ コピーコンストラクタ のような働きをします。

しかし、三つのコピーが存在するものの、以下の図で表されるような 構造の共有 (structural sharing) が自動的に行われています。

我々が扱うものは 結果的 には値であるため、例として上に挙げた String だけでなく、任意の値を 常に 安全に共有することができます。このような性質は、どんな種類であれ静かに忍び寄る可変性を許してしまうと達成できなかったであろうことに注意しましょう。

しかし、本当に巨大なデータを保持していて、かつそれに対して本当に多数の変更を行う場合はどうでしょう？ はい、それでは試してみましょう。データ型 D の値がフィールド x を持ち、x は百万個の文字列 (おそらく遅延評価の対象) を含むと仮定します。さらに別のフィールド y を百万回更新するとしましょう。このとき、百万個のコピーが生成されますが、先にガベージコレクションの対象になってしまうことを防ぐため、おかしなことですがすべてのコピーをそれぞれ保持しておきます。

このような上記を逸したシナリオでも、メモリ消費は、下記画像の虫眼鏡内に見えている青いグラフの右端の小さな山の分だけでしかありません。

文字列のリスト は単独の文字列と同じく不変であり、したがってすべての D のコピーの間で安全に共有できるということに注意しましょう。

不変データ構造は、シングルスレッド環境において API 提供側と使用側で共有するだけでなく、並行実行 や大規模な 並列計算 においても安全に共有可能であることは言うまでもありません。

そのために支払うわずかな追加コストは、一時メモリが少し多めに必要になることと、ガベージコレクションのための余分な時間がいくらか必要になるということだけです。

何重にも入れ子になったデータ構造のコピーや比較は、高コストな操作として知られています。不変データ構造は多くの場合、参照ひとつのみをコピーすることでこの負担を軽減することができます。「コピーコンストラクタ」と呼ばれる仕組みはその良い例です。与えられた値をセットする際には、最も浅い参照のみがコピーされますが、それでもやはり ディープコピー になります。

Frege で使用される標準的なデータ構造はすべて不変です。オブジェクト指向業界から来た人にとって、これは驚くべきことでしょう。例えば、連想配列はいつもその要素を変更することで使用してきました。むしろそれこそが連想配列の主目的だと思っているかもしれませんね！ 今回はその世界観を考え直す良い機会です。参考文献を調べると、この件について情報や気付きが得られるでしょう。

ここで、dierk が現在、考えるのに使っている言語は何でしょう？ 三種類の参照のうちどれが使用されるのでしょうか？ 各時点で「最新版」の Person を一つだけ保持したほうがよいのではないでしょうか？ このような例については先の記事で扱います。また、可変な状態によって不変データ構造が破壊されることを防ぐ Frege の「からくり」についても説明することになるでしょう。