のドキュメントをData.Set見ると、ツリーへの要素の挿入がO（log（n））であると言及されていることがわかりました。ただし、参照透過性ではO（n）に前のツリーの完全なコピーを作成する必要があるため、直感的にはO（n * log（n））（またはO（n）？）であると予想します。
(:)たとえば、ここでは完全なリストをコピーする必要がないため、O（n）の代わりにO（1）にすることができることを理解しています。新しいリストは、コンパイラーによって、最初の要素と古いリストへのポインターになるように最適化できます（これはコンパイラーであり、言語レベルではないことに注意してください）。ただし、値をに挿入するData.Setには、リストの最適化に似たものがあるとは思えないほど、私には非常に複雑に見えるリバランスが必要です。Set docsで参照されている論文を読んでみましたが、質問に答えることができませんでした。
では、要素を二分木に挿入するには、（純粋に）関数型言語でO（log（n））を使用するにはどうすればよいでしょうか。
Set要素を挿入するためにa の完全なコピーを作成する必要はありません。内部的には、要素はツリーに格納されます。つまり、挿入のパスに沿って新しいノードを作成するだけで済みます。手つかずのノードは、 の挿入前バージョンと挿入後バージョンの間で共有できますSet。そして、Deitrich Eppが指摘したように、バランスの取れたツリーO(log(n))では、挿入のパスの長さです。(肝心なところが抜けててすいません。)
タイプTreeが次のようになっているとします。
data Tree a = Node a (Tree a) (Tree a)
| Leaf
...そしてTree、次のようながあるとします
let t = Node 10 tl (Node 15 Leaf tr')
... ここでtlとtr'は、いくつかの名前付きサブツリーです。12ここで、このツリーに挿入したいとします。さて、それは次のようになります。
let t' = Node 10 tl (Node 15 (Node 12 Leaf Leaf) tr')
サブツリーtlとtr'は と の間で共有されてtおり、 のサイズが 3 よりもはるかに大きくなる場合でも、t'3 つの新しいサブツリーを作成するだけで済みます。Nodest
編集：リバランス
リバランスに関しては、次のように考えてください。空のツリーがあるとします。すでにバランスが取れています！ここで、要素を挿入するとします。すでにバランスが取れています！ここで、別の要素を挿入するとします。まあ、奇数があるので、そこでは大したことはできません。
ここがトリッキーな部分です。別の要素を挿入するとします。これには、左または右の 2 つの方法があります。バランスかアンバランスか。バランスが取れていない場合は、ツリーの回転を明確に実行してバランスを取ることができます。バランスが取れている場合は、すでにバランスが取れています。
ここで注意すべき重要なことは、常にリバランスを行っているということです。要素を挿入することを決定したツリーがごちゃごちゃしているわけではありませんが、その前にバランスを取り直し、挿入が完了した後に混乱を残します。
ここで、要素を挿入し続けるとします。木はバランスを崩しますが、それほどではありません。そして、それが起こった場合、最初にそれをすぐに修正し、次に修正はO(log(n))バランスの取れたツリーにある挿入のパスに沿って発生します。リンク先の論文の回転は、回転を実行するためにツリー内の最大 3 つのノードに接触しています。O(3 * log(n))そのため、リバランス時に作業を行っています。それはまだO(log(n))です。
コメントで dave4420 が言ったことをさらに強調するために(:)、一定時間で実行することに関与するコンパイラーの最適化はありません。独自のリスト データ型を実装し、単純な非最適化 Haskell インタープリターで実行することもできますが、それでも O(1) です。
リストは、初期要素とリスト (または基本ケースでは空)として定義されます。ネイティブ リストと同等の定義は次のとおりです。
data List a = Nil | Cons a (List a)
したがって、要素とリストがあり、 を使用してそれらから新しいリストを作成したいCons場合、コンストラクターが必要とする引数から直接新しいデータ構造を作成するだけです。のようなことを行うときに文字列を調べたりコピーしたりする必要がなくなるのと同様に、末尾のリストを調べる必要さえありません(コピーすることは言うまでもありません) Person "Fred"。
これがコンパイラの最適化であり、言語レベルの最適化ではないと主張するとき、あなたは単に間違っています。この動作は、リスト データ型の言語レベルの定義に直接従います。
同様に、項目と 2 つのツリー (または空のツリー) として定義されたツリーの場合、項目を空でないツリーに挿入するときは、左または右のサブツリーに挿入する必要があります。要素を含むそのツリーの新しいバージョンを構築する必要があります。つまり、新しいサブツリーを含む新しい親ノードを構築する必要があります。しかし、もう一方のサブツリーをたどる必要はまったくありません。そのまま新しい親ツリーに入れることができます。バランスの取れたツリーでは、共有できるツリーの半分になります。
この推論を再帰的に適用すると、実際にはデータ要素のコピーはまったく必要ないことがわかります。挿入された要素の最終位置までのパスに必要な新しい親ノードだけがあります。新しい各ノードには、アイテム (元のツリーのアイテム参照と直接共有)、変更されていないサブツリー (元のツリーと直接共有)、および新しく作成されたサブツリー (その構造のほとんどすべてを元のツリーと共有) の 3 つが格納されます。木）。バランスの取れたツリーには O(log(n)) 個のものが存在します。