Clojure集合背后的数据结构是什么？

Question

我最近听了Rich Hickey对软件工程广播的采访.在访谈期间,Rich提到Clojure的藏品是作为树木实施的.我希望用另一种语言实现持久性数据结构,并希望了解如何实现集合和Clojure的其他持久性数据结构.

在以下场景中,每个点的树会是什么样子？

1. 创建集 {1 2 3}

2. 建立联盟{1 2 3}和{4}

3. 创建的差异{1 2 3 4}和{1}

我想了解如何产生的三组({1 2 3},{1 2 3 4},和{2 3 4})股权结构,而"删除"被如何处理.

我还想知道节点可能拥有的最大分支数.Rich在访谈中提到树木很浅,所以大概是分支因子大于2.

Answer 1

你可能需要阅读Phil Bagwell的作品.他对数据结构的研究是Clojure,Haskell和Scala持久数据结构的基础.

Phil在Clojure/Conj上有这样的演讲:http://www.youtube.com/watch？ v = K2NYwP90bNs

还有一些论文:

• 快速功能列表,散列列表,Deques和可变长度数组
• 理想的哈希树
• 来自菲尔的更多信息

您还可以阅读Chris Okasaki的Purely Functional Data Structures.这篇博文讲述了这本书:http://okasaki.blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html

Answer 2

你应该阅读Clojure编程,它非常详细地介绍了这一点,包括图片.简而言之,集合是深度优先搜索树木.我们可以这样展示你的例子:

(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 3

我喜欢SCdF的图纸和解释,但是如果你想要更深入,你应该阅读关于Clojure 高阶数据结构的优秀系列文章.它详细解释了Clojure的地图是如何工作的,而Clojure的集合只是其地图上的一个薄层:#{:a :b}实现为环绕{:a :a, :b :b}.