Clojureのセットの背後にあるデータ構造は何ですか？

Question

私は最近Rich Hickey's interview on Software Engineering Radioに耳を傾けました。インタビュー中RichはClojureのコレクションがツリーとして実装されていると述べました。永続的なデータ構造を別の言語で実装したいと思っており、セットとClojureの他の永続的なデータ構造がどのように実装されているかを理解したいと思います。

次のシナリオでは、各ポイントでツリーはどのように見えますか？

1. セットを作成します{1 2 3}

2. 私はどのように理解したい{1 2 3 4}と{1}

の違いを作成{1 2 3}と{4}

の和集合を作成します。 3つのセットが生成される（{1 2 3},{1 2 3 4}、および{2 3 4}）は構造を共有し、どのように「削除」が処理されるかを示します。

また、ノードが持つ可能性のある分岐の最大数についても知りたいと思います。リッチはインタビューで木が浅いと言いました。おそらく分枝因子は2よりも大きいでしょう。

Answer 1

おそらくPhil Bagwellの作品を読む必要があります。データ構造に関する彼の研究は、Clojure、HaskellおよびScala永続データ構造の基盤です。

のClojure/CONJでフィルすることで、この話があります：http://www.youtube.com/watch?v=K2NYwP90bNs

は、いくつかの論文もあります

• Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays
• Ideal Hash Trees
• More from Phil here

することができますまた、を読むクリス・オカサキ著。このブログの記事では、本について語ります。http://okasaki.blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html

Answer 2

は、ここでの出発点です：https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashSet.java

あなたはそれがPersistentHashMapの面で実装されます見ることができます。

Answer 3

あなたは本当にClojure Programmingを読むべきです、それは写真を含むこれを非常に詳細にカバーします。簡単に言えば、コレクションはツリーを通じた深さの最初の検索です。私たちは、このようなあなたの例を表示することができます。これらは単なる指標であることを

(def x #{1 2 3}) 

x 
| 
| \ 
|\ 3 
1 \ 
    2 

(def y (conj x 4)) 

x y 
|/\ 
| \ 4 
|\ 3 
1 \ 
    2 

(def z (difference y #{1})) 

x y 
|/\ 
| \ 4 
|\ 3 
1/\ 
z- 2 

注意を、私はこれは正確にはClojureが内部で使用レイアウトであることは言いませんよ。しかしそれは要点です。

Answer 4

私はSCdFの図面と説明が気に入っていますが、もっと深く探しているのなら、Clojureのデータ構造に関する優れた一連の記事をHigher-Orderにお読みください。これは、Clojureのマップの仕組みを詳しく説明しており、Clojureのセットはマップ上の単なる薄いレイヤーです。#{:a :b}は、{:a :a, :b :b}のラップとして実装されています。