初学 Clojure 集合与数据结构

Question

这个很重要，不需要多说，clojure 提供了 vector、list、queue、set、map 这几种数据结构，来看看它们的基本操作。

---

非写入硬盘的数据持久化

这里说的数据持久化，指的是不变量，即值是不能被改变的。值的不可变，使得我们不需要担心值更新所带来的不确定性，在并发场景下不需要花费过多精力维护数据的准确性。

;声明list
(def lst1 (list 1 2 3 4))
;添加新元素，它重新生产一个“新列表”
(def lst2 (conj lst 5));=(5 1 2 3 4)
;lst引用依旧指向(1 2 3 4)
lst1 ;=(1 2 3 4)

为达到值的不可变，而创建一个新值，可能会对此认为这实在浪费内存空间，每次改变值都要重新复制一份出来。

其实不是的，用过git的伙伴都知道，即使在文件里加个空格都会生成一个新的版本号，clojure对值的管理与此有一些类似。假如你对lst1做任何增删改，所有元素都会存在于它原本的历史版本中，并且每个版本间都共享结构元素。元素5存在于lst2这个版本中，(1 2 3 4)则lst1与lst2共享。所有版本会形成一棵数，管理map也是如此，只不过版本树会更加复杂。

它叫做向量，不叫数组

在clojure我们管它叫vector，不叫array，尽管都以数字作为索引，它是不可变，它的字面量是[]。

如何创建向量呢？

;我们可以这样创建一个vector，直接使用字面量
(def vec1 [1 2 3 4 5])
;用vec来引入某个集合的元素，如果是个map，vec2会是个多维向量，至少二维
(def vec2 (vec (range 5)))
;显然，是往一个vector塞另外一个集合
(def vec3 (into vec1 (range 6 10)))

可以限制vector为基础数据类型的集合，只要使用vector-of函数即可，支持:int、:long、:float、:double、:byte、:short、:boolean、:char这些基础类型。

(into (vector-of :int) [Math/PI 2 1.4]);=[3 2 1]
(into (vector-of :char) [100 102 104]);=[\d \f \h]
(into (vector-of :boolean) [false true 1 nil]);=[false true true false]
(into (vector-of :long) ["string" "number" 10000])
;=ClassCastException java.lang.String cannot be cast to java.lang.Number

有索引，自然可以用下标获取元素，有nth、get、向量自身作为函数三种方式，每种都有那么一点不同。

(def nil_vec nil)
(def empty_vec [])
(def char_vec [\a \b \c \d \f])

(nth nil_vec 3);=nil
(nth empty_vec 3);=IndexOutOfBoundsException
(nth char_vec 3);=\d
;支持not find参数，找不到元素则返回该实参
(nth char_vec 100 :no!);=:no!

(get nil_vec 3);=nil
(get empty_vec 3);=nil
(get char_vec 3);=\d
;同上
(get char_vec 100 :no!);=:no!

;clojure有个奇妙的特性，就是集合本身可以作为函数，返回自己内部的元素
(nil_vec 3);=NullPointerException
(empty_vec 3);=IndexOutOfBoundsException
(char_vec 3);=\d
;然而，它并不支持上面两种方式支持的not find参数

以上三种并没有那个最好，更多时候需要具体到业务场景，又或者依据个人喜好。

那么来看看怎么修改元素。

(def num_vec [1 2 3 4 5])
;直接修改对于下标的元素
(assoc num_vec 2 "string");=[1 2 "string" 4 5]
;这个则是使用一个函数去改变对应下标的元素
(update num_vec 2 * 100);=[1 2 300 4 5]

;遇到多维向量，也提供了get-in、assoc-in、update-in三个函数改变或获取被嵌套的元素
(def num_vec2 [[1 2 3] [4 5 6] [7 8 9]])
(get-in num_vec2 [1 2]);=6
(get-in num_vec2 [1 6]);=nil
;支持not find参数
(get-in num_vec2 [1 6] :no!);=:no!
(assoc-in num_vec2 [1 2] \s);=[[1 2 3] [4 5 \s] [7 8 9]]
;追加到最后一项，如果[1 4]以上则会抛出IndexOutOfBoundsException
(assoc-in num_vec2 [1 3] \s);=[[1 2 3] [4 5 6 \s] [7 8 9]]
(update-in num_vec2 [1 2] * 100);=[[1 2 3] [4 5 600] [7 8 9]]
(update-in num_vec2 [1 3] * 100);=NullPointerException

vector提供了三个函数，使其支持栈操作，分别是peek返回栈顶、pop除去栈顶、conj推入栈，由于vector是不可变的，所以并不像以往的pop和push完全一样。

(def my_stack [1 2 3 4 5])
(peek my_stack);=5
(pop my_stack);=[1 2 3 4]
(conj my_stack \s);=[1 2 3 4 5 \s]

是 Lisp 都喜欢的 list

list是单链表结构，即每个节点都有指向下一个节点的指针，且知道距离末端的长度，它同样不可变，添加删除都发生在最左端。

我们可以这样创建list：

(list 1 2 3 4 4)
'(1 2 3 4)

也提供了conj和cons两种方式添加元素，两者返回的结果有所不同，神奇的是，连参数顺序都不一样！！

;conj返回的结果与它的第一个参数同构，意思是传入seq返回seq，传入list返回list
;yep!'(1 2)是个list
(list? (conj '(1 2) 3));=true
(seq? (conj '(1 2) 3));=true
;(range 2)是个seq
(list? (conj (range 2) 3));=false
(seq? (conj (range 2) 3));=true

;cons则返回seq，不过第二参数传入list还是seq
(list? (cons 3 '(1 2)));=false
(seq? (cons 3 '(1 2)));=true
(list? (cons 3 (range 2)));=false
(seq? (cons 3 (range 2)));=true

;在对list操作的话，conj无疑是最正确的最为高效的

对list的取值函数first、next和rest，完全可以把list作为栈使用。

(def nil_list nil)
(def empty_list '())
(def one_item_list '(1))
(def num_list '(1 2 3 4 5))

(first nil_list);=nil
(first empty_list);=nil
(first num_list);=1
;若无则返回nil
(next nil_list);=nil
(next empty_list);=nil
(next one_item_list);=nil
(next num_list);=(2 3 4 5)
;若无则返回空list
(rest nil_list);=()
(rest empty_list);=()
(rest one_item_list);=()
(rest num_list);=(2 3 4 5)

;list是可以使用pop和peek的，但由于已经提供了上面三个函数，而且当pop用在empty_list会抛出异常，所以强烈建议用first、next和rest

强调一点，list 不支持索引查找！

集合！不能有重复元素！

set，即集合，与数学上的集合同样有三种特性-确定性、互异性、无序性，没有薛定谔的元素，也没有重复的元素，也没有先后关系的元素（这还说不定呢）。

怎么创建set？

(set [1 2 3 4]);=#{1 4 3 2}
(set {:a 1 :b 2});=#{[:b 2] [:a 1]}
(def num_set #{1 4 3 2})
(def entry_set #{[:b 2] [:a 1]})

(set [1 2 3] '(1 2 3));=#{[1 2 3]}，vector视同为list
(set [] {} #{} ());=#{[] {} #{}}

查询获取set内元素！

;set作为函数
(#{1 2 3 4} 3);=3
(get #{:a :b :c} :d);=nil

;contains?查询元素是否存在
(contains? #{:a :b :c :d} :d);=true
(contains? #{:a :b :c :d} :e);=false

;顺序集合sorted-set
(sorted-set :c :d :a :b);=#{:a :b :c :d}
(sorted-set [1 2] [4 5] [2 3]);=#{[1 2] [2 3] [4 5]}
;sorted-set在默认情况下，对元素类型有潜在的混淆，比如number与string无法一起排序，添加元素时也容易出现类型混淆
(sorted-set "a" 1 2 "0");=ClassCastException java.lang.String cannot be cast to java.lang.Number

`contains?`这个函数实际上是查找健值是否存在，这就表明set实际上也是map实现的，而它的键值与值相同。在这补充一点，set与vector都是基于map实现，但`contains?`在vector是无效的，因为它是以索引为键值，故`(contains? [:a :b :c] 2)`才能返回true，按元素值查找始终返回false。

关于set的集合计算没打算讲，见clojure.set/intersection、clojure.set/union、clojure.set/difference的API。

map！重中之重！

map可能是clojure被应用最广的数据结构，不管你是否知情，比如用set时实际上用了map。

有几样map，hash-map、array-map和sorted-map，不同的创建方式，返回也会是不同类型的map。

;直接用字面量创建map，它是个array-map
(def a_array_map {:a 1 :b 2 :c 3 :d 4})
(class a_array_map);=clojure.lang.PersistentArrayMap
;显示创建array-map
(array-map :a 1 :b 2);={:a 1, :b 2}
;用zipmap创建也是个array-map，在clojure 1.2则是个hash-map
(zipmap [:a :b :c] [1 2 3]);={:a 1, :b 2, :c 3}

;hash-map创建一个HashMap
(def a_hash_map (hash-map :a 1 :b 2 :c 3 :d 4));={:c 3, :b 2, :d 4, :a 1}
(class a_hash_map);=clojure.lang.PersistentHashMap
(apply hash-map [:a 1 :b 2 :c 3 :d 4]);={:c 3, :b 2, :d 4, :a 1}

hash-map的键值是无法指定顺序的，array-map则是按照插入顺序，只有sorted-map的键值能依照默认或我们提供的特定顺序进行排序。不过有一点，因为sorted-map键值需要遵循特定顺序，所以对键值的类型也有所限定，不再像其他两个类型的map一样支持异构。

(sorted-map :d 1 :a 3 :o 9 :c "d");={:a 3, :c "d", :d 1, :o 9}
;键值类型不一致而无法比较，会直接抛出异常
(sorted-map :d 1 :a 3 :o 9 "d" "d");=ClassCastException clojure.lang.Keyword cannot be cast to java.lang.String
;可以自定义比较器来创建sorted-map，即sorted-map-by函数
(sorted-map-by
  #(let [[x y]
         (map (fn [z]
                (Integer/valueOf (last (.split z "-")))) [%1 %2])]
     (compare x y)) "tom-12" :BJ "jim-24" :GZ "anj-6" :SZ);={"anj-6" :SZ, "tom-12" :BJ, "jim-24" :GZ}

获取map的某个值也是用get，map本身也可以作为函数且接受一个参数，键值(只能为keyword类型)同样可以作为函数且接受一个map。

(def person {
             :name "Mark Volkmann"
             :address {
                       :street "644 Glen Summit"
                       :city "St. Charles"
                       :state "Missouri"
                       :zip 63304}
             :employer {
                        :name "Object Computing, Inc."
                        :address {
                                  :street "12140 Woodcrest Executive Drive, Suite 250"
                                  :city "Creve Coeur"
                                  :state "Missouri"
                                  :zip 63141}}})

(get person :name);="Mark Volkmann"
(get (get person :employer) name);="Object Computing, Inc."

(person :name);="Mark Volkmann"
((person :employer) :name);="Object Computing, Inc."

(:name person);="Mark Volkmann"
(:name (:employer person));="Object Computing, Inc."
;因为键值作为函数，所以可以当作组合函数而使用'->'宏；反之，map作为函数则不行。
;第一个参数是第二个参数的实参，获取到子map后传递到给后面的键值
(-> person :employer :name);="Object Computing, Inc."

给 map 修改添加键值对的函数与 set 说到的几个函数一样，assoc-in、update-in 和 assoc。

(assoc-in person [:employer :address :city] "Clayton")
;如果键值不存在，则新添进去
(assoc-in person [:employer :address :phone] "13700000000")
(update-in person [:employer :address :zip] str "-1234")

;需要注意一点，当map的键值是数字类型时，在有序map和hashmap或arraymap上做assoc操作结果是有可能不同的。(在《clojure编程乐趣》有说到)
(assoc {1 :int} 1.0 :float);={1 :int, 1.0 :float}
;有序集合中，键值相等则认为是同一个
(assoc (sorted-map 1 :int) 1.0 :float);={1 :float}