Clojure 中的集合与数据结构

map、vector、set 和列表是 Clojure 提供的基本数据类型。Clojure 为它们提供了便利的字面量：

• ‘(a b :name 12.5) ;; 列表
• [‘a ‘b :name 12.5] ;; vector
• {:name “Hello” :age 31} ;; map
• #{1 2 3} ;; set

Clojure 中的数据结构有两个特色：

1. 数据结构首先是依据抽象来用的，而不是依据具体的的实现细节来用的。

2. 数据结构是 不可改变的而且是持久的

抽象

多态性

seq 总是产生一个集合类的顺序视图——称为一个 序列 。

conj 总是向给定的集合类添加新的值。

显然，seq 和 conj 对于它们所操作的集合类型来说是多态的。

对于 vector 来说，conj 把一个值附加到 vector 后面；对于列表来说，则是附加到前面；对于 map 来说，就把一个键值对附加到 map 里，如果键已经存在，就替换对应的值，否则，就向这个 map 添加一个新的键值对。

seq 为 vector、set、列表提供了符合直觉的顺序视图，并把 map 也包括进来，map 的顺序视图是包含 map 里面所有键值对（以[key value]形式表示）的一个列表。

into 是建立在 seq 和 conj 之上的，这意味着 into 能自动用于任何至此 seq 和 conj 的值。

Clojure 集合中会实现如下几个主要抽象：

• Collection

• Sequence

• Associative

• Indexed

• Stack

• Set

• Sorted

集合：Collection

Clojure 所有的数据结构都实现了 Collection 抽象。如下是 Collection 的核心函数：

• conj
• seq 获取集合的顺序视图
• count
• empty 获取一个和所提供集合类型一样的空集合
• = 用来判断两个或多个集合是否相等

conj 会保证对于所有的集合类型，它都会高效地把元素添加进去。

count 保证对于所有集合操作耗时都是高效的（序列除外，因为序列的长度可能是未知的）。

序列：Sequence

Sequence 接口定义了一个获取并且遍历各种集合的一个 顺序视图 的一种方法。这个集合可以是另一个集合，也可以是某个函数的一个返回值。

除了 Collection 接口提供的一些函数，Sequence 还提供了一些额外接口：

• seq 函数返回给传入参数的一个序列。
• first、rest 以及 next 提供了遍历序列的一个方法。
• lazy-seq 创建一个内容是一个表达式结果的惰性序列。

可以用 seq 产生有效值的类型称为可序列的类型：

• 所有的 Clojure 集合类型
• 所有的 Java 集合类型（即 java.util.* ）
• 所有的 Java map
• 所有的 java.lang.CharSequence，包括 String
• 实现了 java.lang.Iterable 的任意类型
• 数组
• nil （或者是 Java 方法返回的 null）
• 任何实现了 clojure.lang.Seqable 接口的类型

seq 对于任何 nil 或者任何类型的空集合都返回 nil。

如果操作的结果是空的话，那么 rest 始终返回一个空序列，但是 next 则返回 nil。原因在于 next 始终会强制实例化尾巴的第一个元素。

序列不是列表，它们在很多方面上是不同的：

1. 要计算一个序列的长度是比较耗时的。

2. 序列的内容可能是惰性的，而只有在真的要用到序列中值的时候才会去实例化。

3. 一个生成序列的函数可能生成一个无限惰性序列，所以也就是不可数的。

而列表则是会保存它的长度，是所以要获取列表长度的方法是非常高效的。而获取序列长度的唯一办法是遍历这个序列。

创建序列

一般来说，一个序列是从一个集合生成而来，要么是通过 seq 函数直接创建，要么通过其他函数（比如 map）间接调用 seq。

但有两种方法可以直接创建一个序列：cons 和 list*。

• cons 接收两个参数，第一个参数是一个值作为新序列的头，第二个参数是一个集合，作为新序列的尾巴：

  (cons 0 (range 1 5))
  ;=> (0 1 2 3 4)
  

• list* 只是一个帮助函数，来简化多个值来创建序列的需求：

  (list* 0 1 2 3 4 (range 4 10))
  ;=> (0 1 2 3 4 5 6 7 8 9)
  

惰性序列

在 Clojure 中，一个集合的具体内容可以是惰性生成的。访问一个惰性序列的过程称为实例化；当一个惰性序列中的元素都被计算的时候，这个序列就被完全实例化了。

可以通过宏 lazy-seq 来创建一个惰性序列，这个宏接收任意返回值是一个可序列化的表达式。

如果需要完全实例化一个惰性序列并且保持这个序列的所有元素，可以使用 doall ，如果并不需要惰性序列的具体内容，那么应该使用 dorun。

一旦惰性序列的一个元素被实例化之后，只要保持了对这个序列的引用，那么这个元素就会一直保持着了。也就是，只要保持了对序列的一个引用，那么序列中的元素就不能被垃圾回收。

Associative

关系型数据结构 Associative 接口所抽象的是把一个 key 和一个 value 关联起来的数据结构。这个接口包含 4 个操作：

• assoc，向集合中添加一个新的 key 到 value 的映射
• dissoc，从集合中移除一个从指定 key 到 value 的映射
• get，从集合中找出指定 key 的 value
• contains?

最正宗的关系型数据结构是 map。

assoc 和 dissoc 可以一次性添加/去除多个键值对。

除了 map 之外，get 和 assoc 也支持 vector 进行操作。

get 还能操作操作 set，如果一个 key 在 set 中存在的话，那么会返回它，否则返回 nil。

find 跟 get 更类似，只是它返回的不是 key 所对应的 value，而是返回一个键值对——如果 map 里面包含指定的 key 的话，或者返回 nil 如果不包含这个 key 的话。

索引集合：Indexed

Indexed 接口提供了操作下标的各种函数。这个接口里面只有一个函数： nth，它就跟 get 类似。不同之处在于，它们对于越界的下标的处理：nth 会抛出异常，而 get 则是返回 nil。

nth 和 get 的意义是很不一样的。首先，nth 只能接收数字作为查询的 key（下标），它可以作用于很多有“下标”概念的值：vector、列表、序列、Java 数组、Java 列表、字符串、正则表达式的匹配数组等等，而 get 则更通用：它可以操作任何关系型的值，在处理 vector 的时候，它可以把下标当作 key。

当传给 get 一个不支持的参数类型，它可以返回 nil 而不是抛出异常，nth 则直接抛出异常。

栈：Stack

• conj 把一个值添加到栈中
• pop 获取栈顶的值，并且移除这个值
• peek 获取栈顶的值，但是不移除这个值

列表和 vector 都可以当作栈用，在这两种集合中，栈顶都是 conj 可以高效添加元素的另外一端。

set

set 接口需要 disj 来从 set 里面移除一个元素。

有序集合：Sorted

实现 sorted 抽象的集合保证集合内的值被以特定的顺序保存，这个顺序可以通过一个词或者一个特定的 comparator 接口来定义。这个接口包含以下函数：

• rseq 函数可以在 常量时间 内 反序 地返回一个集合的元素。

• subseq 可返回一个集合的某一个区间内的元素的序列。

• rsubseq 和 subseq 类似，但是返回的元素是反序的。

只有 map 和 set 实现了 sorted 接口。没有字面量来表示 sorted 的集合，要创建 sorted 集合可以用 sorted-map 和 sorted-set 来创建有序的 map 和 set。如果要提供自己的谓词或者比较器来定义 排序 规则的话，可以使用 sorted-map-by 和 sorted-set-by。

compare 函数定义默认排序：正序。它支持所有的 Clojure 标量及顺序集合，它会按照字典排序法来在每一层对元素进行排序。

compare 不止支持字符串、数字以及顺序集合：它支持任何实现了 java.lang.Comparable 接口的值。

集合本身也是函数。集合的 key （通常）也是函数。

some 函数在一个序列里搜索 第一个 能够符合指定谓词的元素。

filter 返回一个惰性序列，惰性序列的内容就是那些满足指定谓词的元素。

remove 和 filter 的作用正正好相反，它把符合谓词的元素从集合中去掉，返回所有不符合谓词要求的元素。

数据结构的类型

列表： List

Clojure 中的列表是单向链表。

列表不支持 get 操作，因为列表上无法达到 get 亚线性的性能要求。

可以使用 list? 来测试一个集合是不是列表。

'(1 2 3)
=> (1 2 3)

vector

vector 是一种顺序数据结构。

vector? 可以测试一个值是不是 vector。

set

不包含重复元素。

map

keys 和 vals 乐意很方便地返回一个 map 的所有的键和值。

group-by 函数可以很方便地根据一个 key 函数把一个集合分成多组。