Jade Dungeon

集合类与数据结构

抽象优于实现
访问集合元素的简洁方式
- 习惯用法
- 集合、key以及高阶函数
数据结构的类型
不可变性和持久性
- 持久性与数据共享
  - 持久性图解：列表
  - 持久性图解：map、vector、set
- 易变集合
元数据
- 添加元数据
- 修改元数据
用Clojure的集合来小试牛刀
- 标识符和循环引用
- 思维方式的改变：从命令式到函数式
  - 自己动手实现经典游戏：Conway's Game of Life
  - 迷宫生成

抽象优于实现

数据结构是依据抽象来用的，面不是依据实现细节来用的。
数据结果是不要变的，而且是持久的。

常用的集合类型字面量：

'(a b :name 12.5)       ;; list

['a 'b :name 12.5]      ;; vector

{:name "Chas" :age 31}  ;; map

#{1 2 3}                ;; set

多态性性可以让函数以不同类型集合为参数：

seq操作为目标集合生成一个序列。
conj给集合增加一个成员。

适用于向量：

(def v [1 2 3])        ;= #'user/v
(conj v 4)             ;= [1 2 3 4]   注意加在最后面
(conj v 4 5)           ;= [1 2 3 4 5]
(seq v)                ;= (1 2 3)

适用于映射：

(def m {:a 5 :b 6})    ;= #'user/m
(conj m [:c 7])        ;= {:a 5, :c 7, :b 6}
(seq m)                ;= ([:a 5] [:b 6])

适用于set：

(def s #{1 2 3})       ;= #'user/s
(conj s 10)            ;= #{1 2 3 10}
(conj s 3 4)           ;= #{1 2 3 4}
(seq s)                ;= (1 2 3)

适用于列表：

(def lst '(1 2 3))     ;= #'user/lst
(conj lst 0)           ;= (0 1 2 3)    注意元素加在最前面
(conj lst 0 -1)        ;= (-1 0 1 2 3)
(seq lst)              ;= (1 2 3)

这样，如果有新的函数是基于seq和conj实现的，那个这个新的函数可以应用在任何支持seq和conj的数据结构上。

集合的合并函数into是基于seq和conj实现的，所有支持这两个函数的类型都可以支持into：

(seq v)                       ;= (1 2 3)
(into v [4 5])                ;= [1 2 3 4 5]

(seq m)                       ;= ([:a 5] [:b 6])
(into m [[:c 7] [:d 8]])      ;= {:a 5, :c 7, :b 6, :d 8}

(into #{1 2} [2 3 4 5 3 3 2]) ;= #{1 2 3 4 5}   集合里元素不重复

(into [1] {:a 1 :b 2})        ;= [1 [:a 1] [:b 2]] 映射的每个元素加入序列

很多Clojure的集合只实现了对应接口的一小部分，没有实现的部分抛NotImplementedException，这样不用实现全部接口方法也可以用。

Clojure主要抽象类型：

Collection
Sequence
Associative
Indexed
Stack
Set
Sorted

集合：Collection

所有数据结构的抽象，核心函数有：

用conj来添加一个元素。
用seq取得顺序的视图。
有count获取元素个数。
用empty生成一个同类型的空集。
用=判断两个或多个集合是否相等。

不同的子类对同一个函数会有不同的行为。

empty函数

empty函数以一个信任作为参数，返回值是与参数类型相同的空集合。

例子，交换集合顺序的程序，empty用来创建相同类型的空集合：

(defn swap-pairs [sequential]
  (into (empty sequential)
        (interleave
          (take-nth 2 (drop 1 sequential))
          (take-nth 2 sequential))))
    
(swap-pairs (apply list (range 10)))   ;= '(8 9 6 7 4 5 2 3 0 1) 
(swap-pairs (apply vector (range 10))) ;= [1 0 3 2 5 4 7 6 9 8]

例子：返回新的映射，根据函数f生成每一项新的值：

(defn map-map [f m]
  (into (empty m)
        (for [[k v] m] [k (f v)])))
  
(map-map inc (hash-map :z 5 :a 0 :c 6))    ;= {:z 6 :a 1 :c 7}
(map-map inc (sorted-map :z 5 :a 0 :c 6))  ;= {:a 1 :c 7 :z 6}

根据参数的类型是有序的还是无序的映射，返回的结果也是同样的类型。

序列：Sequence

可以用来生成序列的类型：

所有Clojure的集合类型。
所有的clojure.lang.Seqable。
数组。
nil或是Java的null。
所有的Java集合类型：java.util.*。
所有的Java Map。
所有的java.lang.CharSequence，包括String、StringBuffer、 StringBuilder、java.nio.CharBuffer。
所有的java.lang.Iterable。

用一些类型只能用来生成一次序列：

iterator-seq从java.lang.Iterator生成一次序列。
enumerator-seq从java.lang.Enumerator生成一次序列。

序列提供的接口：

seq返回参数的序列视图。
lazy-seq返回一个表达式结果的惰性序列，一般当参数不是一个集合而是一个函数时用得比较多。
first、rest、next用来遍历序列。

(seq "Clojure")                                ;= (\C \l \o \j \u \r \e)
(seq {:a 5 :b 6})                              ;= ([:a 5] [:b 6])
(seq (java.util.ArrayList. (range 5)))         ;= (0 1 2 3 4)
(seq (into-array ["Clojure" "Programming"]))   ;= ("Clojure" "Programming")
(seq [])                                       ;= nil
(seq nil)                                      ;= nil

注意上面seq函数的参数为nil或任何空集的结果都是nil，所以：

(not (empty? []))             ;= false
(not (empty? nil))            ;= false

rest和next在处理空集或是单个元素集合时有区别：

(rest [1])         ;= ()   永远返回空序列
(rest nil)         ;= ()

(next [1])         ;= nil  永远返回nil
(next nil)         ;= nil

对于任何值x，以下表达式都成立：

(= (next x)
   (seq (rest x)))

取序列元素：

(first "clojure")                ;= \c
(rest "clojure")                 ;= (\l \o \j \u \r \e)
(next "clojure")                 ;= (\l \o \j \u \r \e)
(next (next (next "clojure")))   ;= (\j \u \r \e)

rest没有元素时返回的是空序列，next返回nil：

(rest [1])           ;= ()
(next [1])           ;= nil
(rest nil)           ;= ()
(next nil)           ;= nil
(seq (rest nil))     ;= nil

(= (next nil)
   (seq (rest nil))) ;= true

序列不是迭代器

序列是不可变的，按序列生成的迭代器是用来迭代的，而且只能迭代一遍。

range函数从序列中生成迭代器：

(doseq [x (range 3)]
  (println x))
; 0
; 1
; 2

在Clojure的实现中，列表本身就是自身的序列：

(def ll '(1 2 3))

(identical? ll (seq ll))     ;= true

序列不是列表

计算序列的长度比较耗时，而列表有保存长度。
序列有可能是惰性的。
函数可以生成无限长的惰性序列。

对比计算长度的耗时，注意range是惰性求值的：

(let [s (range 1e6)]
  (time (count s)))
; "Elapsed time: 147.661 msecs"
;= 1000000

(let [s (apply list (range 1e6))]
  (time (count s)))
; "Elapsed time: 0.03 msecs"
;= 1000000

创建序列

一般序列都是按业务需求从别的数据结构转成序列的。但也可以按需要通过cons和list*直接创建一个序列。

cons把一个元素作为头加到第二个参数（某集合）上它与conj不同，不管第二个集合是什么类型的：

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

(cons :a [:b :c :d])   ;= (:a :b :c :d)

注意在Clojure中的cons和其他List方言中的不同。而且Clojure中的列表也不是由一个一个的cons单元组成的。

list*用来简化指定多个值来创建序列的操作，以下两个是等价的：

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

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

要注意list*返回的类型不是列表，而是序列抽象。又回到基本原则：基于抽象编程，而不是基于具体的类型编程。

惰性序列

Clojure中办有序列有惰性特性，用lazy-seq生成惰性序列：

(defn random-ints
  "Returns a lazy seq of random integers in the range [0,limit)."
  [limit]
  (lazy-seq
		(println "realizing random number")
    (cons (rand-int limit)        ;; 第一个元素生成一个随机数
          (random-ints limit))))  ;; 后继的元素是递归调用自身

(take 10 (random-ints 50))        ;= (32 37 8 2 22 41 19 27 34 27)

顺序解析始终使用next而不是rest，因为next会强制实例化队列的第一个元素，而rest不会：

user=> (let [[x & rest] (random-ints 50)])
realizing random number
realizing random number
nil

相对地，rest比next更加适合惰性求值：

(def x (next (random-ints 50)))
; realizing random number
; realizing random number

(def x (rest (random-ints 50)))
; realizing random number

doall实例化一个序列的所有元素，并持有所有的值。
dorun适用于只要程序的副作用，并不关心实例化的值的情况。

(dorun (take 5 (random-ints 50)))
; realizing random number
; realizing random number
; realizing random number
; realizing random number
; realizing random number
;= nil

Clojure文档中注明具体的类型和方法是否会惰性求值或是有强制实例化行为，例如，在iterate的描述中强调了返回的序列是惰情的，而且强调参数f不能有副作用：

(doc iterate)
; -------------------------
; clojure.core/iterate
; ([f x])
;   Returns a lazy sequence of x, (f x), (f (f x)) etc.
;   f must be free of side-effects

(doc reverse)
; -------------------------
; clojure.core/reverse
; ([coll])
;   Returns a seq of the items in coll in reverse order. Not lazy.

副作用会有很大的不确定性。有时为了优化性能，即使在只取一个元素的情况下，有些程序会一次性实例化多个元素。

惰性求值的使用场景：处理大量的数据时，拿一小部分，处理，输出，再拿一小部分。

比如以下从句子中剔除元音字母的程序，先把字符串隐式转换为字符序列，再处理输出：

(apply str (remove (set "aeiouy")
             "vowels are useless! or maybe not..."))
;= "vwls r slss! r mb nt..."

repeatedly函数以另一个函数作为参数，返回一个惰性序列：

(repeatedly 10 (partial rand-int 50))  ;= (22 24 24 41 5 30 20 3 41 33)

Clojure的很多核函数，如map、for、filter、take和drop 都可以处理和返回惰性序列。

头保持问题

惰性序列被实例化以后，如果保持对序列头的引用，整个序列都不会被回收，一直占用内存。

比如split-with函数把一个序列分成两部分，符合要求的和不符合要求的：

(split-with neg?             ;; 参数：谓词条件是数字是否是负数
            (range -5 5))    ;; 参数：等分的序列是从-5到5
;= [(-5 -4 -3 -2 -1) (0 1 2 3 4)]

如果数量量很大：

(let [[t d] (split-with #(< % 12) (range 1e8))]
  [(count d) (count t)])
;= #<OutOfMemoryError java.lang.OutOfMemoryError: Java heap space>

程序报出内存不足异常，原因是以上程序执行过程中会生成三个序列：

range生成的序列，数量很大：从\(0\)到\(10^8-1\)。
符合条件的序列t，数量很小：\(0\)到\(11\)。
符合条件的序列d，数量很大：从\(12\)到\(10^8-1\)。

range出来的序列和序列t的头都是同一个（元素0），而(count t)是最后一步操作，所以在最后一步之前程序都保持了range序列的头，整个range序列不会被释放。

如果换了下顺序：

(let [[t d] (split-with #(< % 12) (range 1e8))]
  [(count t) (count d)])

序列t只有前12个元素，count完了12个元素以后，就可以放弃这些引用，再处理(count d)，所以range的前几个元素的内存释放了。

向map或set中插入元素、=函数、count函数，这些都会引起「头保持」问题，因为它们会强制对惰性序列进行完全序列化。

Associative

Associative把一个key和一个value关联起来。相关操作有：

assoc向集合中添加key到value的关联。
dissoc向集合中去掉key到value的关联。
get
contains?

典型的Associative例子是map类型：

(def m {:a 1, :b 2, :c 3})
(get m :b)                    ;= 2
(get m :d)                    ;= nil
(get m :d "not-found")        ;= "not-found"
(assoc m :d 4)                ;= {:a 1, :b 2, :c 3, :d 4}
(dissoc m :b)                 ;= {:a 1, :c 3}

;; 一次添加多个元素
(assoc m
       :x 4 :y 5 :z 6)        ;= {:z 6, :y 5, :x 4, :a 1, :c 3, :b 2}

;; 一次删除多个元素
(dissoc m :a :c)              ;= {:b 2}

vector可以把下标视作key：

(def v [1 2 3])
(get v 1)                      ;= 2
(get v 10)                     ;= nil
(get v 10 "not-found")         ;= "not-found"
(assoc v
       1 4
       0 -12
       2 :p)                   ;= [-12 4 :p]

;; 一个新的下标可以把元素添加加到尾部
(assoc v 3 10)                 ;= [1 2 3 10]

set可以把自身即作为key也作为value：

(get #{1 2 3} 2)                ;= 2
(get #{1 2 3} 4)                ;= nil
(get #{1 2 3} 4 "not-found")    ;= "not-found"

(when (get #{1 2 3} 2)
  (println "it contains `2`!")) ; it contains `2`!

when方法作用是什么？当不为nil或是false的时候执行么？

注意contains?方法是检查是否包含「key」，而不是检查是否包含「值」的：

(contains? [1 2 3] 3)     ;= false   下标作为key
(contains? [1 2 3] 2)     ;= true
(contains? [1 2 3] 0)     ;= true

小心`nil`

key不存在，也没有默认值时，get函数返回的是nil。但要注意有可能value本身就是nil。

find不返回value，而是返回键值对。所以有键值对就是有的，没有的话返回nil。

(find {:ethel nil} :lucy)    ;= nil
(find {:ethel nil} :ethel)   ;= [:ethel nil]

find可以和if-let或when-let一直使用：

(if-let [e (find {:a 5 :b 6} :a)]
  (format "found %s => %s" (key e) (val e)) 
  "not found")                                ;= "found :a => 5"

(if-let [[k v] (find {:a 5 :b 6} :a)]
  (format "found %s => %s" k v) 
  "not found")                                ;= "found :a => 5"

索引集合：Indexed

函数式风格程序一般来说不应该涉及数组的下标操作，否则往往是程序过于复杂的标志。

真要用下标的话，可以用nth函数，越界时nth会抛异常，而get会返回nil：

(nth [:a :b :c] 2)             ;= :c
(get [:a :b :c] 2)             ;= :c

(nth [:a :b :c] 3)             ;= java.lang.IndexOutOfBoundsException
(get [:a :b :c] 3)             ;= nil

(nth [:a :b :c] -1)            ;= java.lang.IndexOutOfBoundsException
(get [:a :b :c] -1)            ;= nil

(nth [:a :b :c] -1 :not-found) ;= :not-found
(get [:a :b :c] -1 :not-found) ;= :not-found

栈：stack

vector和list都可以当作栈来用，相关的操作有：

conj压栈。
pop出栈，对空栈pop会出错。
peek取值，不出栈。

;; list
(conj '() 1)      ;= (1)
(conj '(2 1) 3)   ;= (3 2 1)
(peek '(3 2 1))   ;= 3
(pop '(3 2 1))    ;= (2 1)
(pop '(1))        ;= ()

;; vector
(conj [] 1)       ;= [1]
(conj [1 2] 3)    ;= [1 2 3]
(peek [1 2 3])    ;= 3
(pop [1 2 3])     ;= [1 2]
(pop [1])         ;= []

set

set可以视为退化的map，它的key和value是一样的。disj函数从set中移除一个元素：

(get #{1 2 3} 2)             ;= 2
(get #{1 2 3} 4)             ;= nil
(get #{1 2 3} 4 "not-found") ;= "not-found"

(disj #{1 2 3} 3 1)          ;= #{2}  removed one element

clojure.set包中还有一些很有用的高阶函数，如：subset?、superset?、union、 intersection、project等。

有序集合：sorted

sorted是没有字面量的。只有set和map实现了sorted接口：

分别用sorted-map和sorted-set来创建有序的实例；
如果要自定义排序规则，可以用sorted-map-by和sorted-set-by。

顺序由一个谓词函数或是一个comparator接口定义。sorted接口包括以下函数：

rseq常量时间内反向序列。
subseq返回区间内的子集序列。
rsubseq返回区间内的子集反向序列。

(def sm (sorted-map :z 5 :x 9 :y 0 :b 2 :a 3 :c 4))
;= #'user/sm

sm                           ;= {:a 3, :b 2, :c 4, :x 9, :y 0, :z 5}
(rseq sm)                    ;= ([:z 5] [:y 0] [:x 9] [:c 4] [:b 2] [:a 3])
(subseq sm <= :c)            ;= ([:a 3] [:b 2] [:c 4])
(subseq sm > :b <= :y)       ;= ([:c 4] [:x 9] [:y 0])
(rsubseq sm > :b <= :y)      ;= ([:y 0] [:x 9] [:c 4])

compare函数定义默认的排序方式，支持所有的Clojure标量及顺序集合，支持所有实现了java.lang.Comparable接口的值，包括布尔、关键字、符号。

(compare 2 2)                     ;= 0
(compare "ab" "abc")              ;= -1
(compare ["a" "b" "c"] ["a" "b"]) ;= 1
(compare ["a" 2] ["a" 2 0])       ;= -1

使用比较器和谓词来排序

sort通过谓词来排序。
sort-by除了指定谓词，还要指定按哪个字段来排序。
sort-map-by替换默认的compare比较器。
sort-set-by替换默认的compare比较器。

(sort < (repeatedly 10 #(rand-int 100)))
;= (12 16 22 23 41 42 61 63 83 87)

(sort-by first > (map-indexed vector "Clojure"))
;= ([6 \e] [5 \r] [4 \u] [3 \j] [2 \o] [1 \l] [0 \C])

(sorted-map-by compare :z 5 :x 9 :y 0 :b 2 :a 3 :c 4)
;= {:a 3, :b 2, :c 4, :x 9, :y 0, :z 5}

;; (comp - compare)正好是compare的反顺序
(sorted-map-by (comp - compare) :z 5 :x 9 :y 0 :b 2 :a 3 :c 4)
;= {:z 5, :y 0, :x 9, :c 4, :b 2, :a 3}

比较器对容器的影响

有序的map和set的比较器会影响到两个元素的相等判断。

例，定义比较器，按数字的十进制位数排序：

(defn magnitude
  [x]
  (-> x Math/log10 Math/floor))

(magnitude 100)      ;= 2.0
(magnitude 333)      ;= 2.0
(magnitude 8888)     ;= 3.0
(magnitude 100000)   ;= 5.0

这个比较操作会影响到相等性判断：

500和600都是3位，视为相等，不加入set
500和750都是3位，视为相等，所以删除了500
1000和1239都是4位，判断为存在容器中

(sorted-set-by compare-magnitude 10 1000 500) ;= #{10 500 1000}

(conj *1 600)                                 ;= #{10 500 1000}
(disj *1 750)                                 ;= #{10 1000}
(contains? *1 1239)                           ;= true

所以要修改比较逻辑，只有在两个数字真的相等时才判断相等：

(defn compare-magnitude
  [a b]
  (let [diff (- (magnitude a) (magnitude b))]
    (if (zero? diff)
      (compare a b)
      diff)))

(sorted-set-by compare-magnitude 10 1000 500) ;= #{10 500 1000}
(conj *1 600)                                 ;= #{10 500 600 1000}
(disj *1 750)                                 ;= #{10 500 600 1000}

subseq和rsubseq的截取操作也可以指定比较的方法：

(def ss (sorted-set-by compare-magnitude 10 1000 500 670 1239))
;= #{10 500 670 1000 1239}

(subseq  ss > 500)                           ;= (670 1000 1239)
(subseq  ss > 500 <= 1000)                   ;= (670 1000)
(rsubseq ss > 500 <= 1000)                   ;= (1000 670)

例子，实现牛顿线性插入值：

(defn interpolate
  "Take a collection of points (as [x y] tuples), returning a function
  which is a liner interpolation between bhose points"
  [points]
  (let [results (into (sorted-map) (map vec points))]      ;; 1
    (fn [x]
      (let [[xa ya] (first (rsubseq results <= x))         ;; 2
            [xb yb] (first (subseq  results >  x))]
        (if (and xa xb)                                    ;; 3
          (/ (+ (* ya (- xb x)) (* yb (- x xa)))           ;; 4
             (- xb xa))
          (or ya yb))))))

(map vec points)保证每个点都是用vector表示的，从而可以加入map
这里的两行在已经的点中找到和x最近的两个点。
如果没有相邻的点（只要xa和xb中有一个为nil），则返回(or ya yb) （因为这也是我们唯一知道的值）。
对于一般情况的线性牛顿插值。

访问集合元素的简洁方式

集合本身也是函数。

集合可以接受下标作为参数：

(get [:a :b :c] 2)       ;= :c
(get {:a 5 :b 6} :b)     ;= 6
(get {:a 5 :b 6} :c 7)   ;= 7 可以有默认值
(get #{1 2 3} 3)         ;= 3

等价于：

([:a :b :c] 2)           ;= :c
({:a 5 :b 6} :b)         ;= 6
({:a 5 :b 6} :c 7)       ;= 7  可以有默认值
(#{1 2 3} 3)             ;= 3

对于越界：

(get [:a :b :c] 8)       ;= nil
(nth [:a :b :c] 8)       ;= IndexOutOfBoundsException
([:a :b :c] 8)           ;= IndexOutOfBoundsException

集合的key（通常）也可以作为函数

(get {:a 5 :b 6} :b)     ;= 6
(get {:a 5 :b 6} :c 7)   ;= 7
(get #{:a :b :c} :d)     ;= nil

等价于：

(:b {:a 5 :b 6})         ;= 6
(:c {:a 5 :b 6} 7)       ;= 7
(:d #{:a :b :c})         ;= nil

习惯用法

「关键字」或「符号」一般都是作为字面量出现，所以推荐用它们作为查找函数来使用（因为字面量不可能是null）。

如果一个集合的key不是关键字或是符号类型，那就只能用集合本身或是get或nth 作为查找函数。

集合、key以及高阶函数

不用get方法，直接用高阶函数map取出:name的值：

(map :name [{:age 21 :name "David"}
            {:gender :f :name "Suzanne"}
            {:name "Sara" :location "NYC"}])
;= ("David" "Suzanne" "Sara")

some函数找出第一个符合谓词条件的元素，比如在一个set中找：

(some #{1 3 7} [0 2 4 5 6])         ;= nil
(some #{1 3 7} [0 2 3 4 5 6])       ;= 3

every?函数检查是不是每一个元素都符合条件：

(every? #{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9} "123")     ;= true
(every? #{\0 \1 \2 \3 \4 \5 \6 \7 \8 \9} "abc123")  ;= false

filter过滤出符合条件的元素，返回值是一个惰性的序列：

(filter :age [{:age 21 :name "David"}
              {:gender :f :name "Suzanne"}
              {:name "Sara" :location "NYC"}])
;= ({:age 21, :name "David"})

(filter (comp (partial <= 25) :age)
        [{:age 21 :name "David"}
         {:gender :f :name "Suzanne" :age 20}
         {:name "Sara" :location "NYC" :age 34}])
;= ({:age 34, :name "Sara", :location "NYC"})

remove和filter作用相反，它去掉符合的元素，只剩下不符合的。

注意nil和false

nil或false，有些谓词的判断会有问题。比如remove剔除了5和7，但是剔除不掉元素false：

(remove #{5 7 false} (cons false (range 10)))
;= (false 0 1 2 3 4 6 8 9)

对于nil或false元素，要用contains?来操作而不是用get之类的直接调用：

(remove (partial contains? #{5 7 false})  ;; 谓词条件是包含 5 7 false
        (cons false (range 10)))          ;; (false 0 1 2 3 4 5 6 7 8 9)
;= (0 1 2 3 4 6 8 9)

数据结构的类型

之前介绍了Collection、Sequence、Associative、Indexed、Stack、Set、Sorted 这些基本的抽象。Clojure提供了一些基本的数据结构实现，他们分别都实现了一个或多个的抽象。

列表：list

单向链表，只对链表的头支持高效的访问和修改操作，不支持get操作。

如果没有单引号开头，把第一个元素作为函数调用：

(+ 1 2 3)

有单引号开头，存储数据用的列表：

'(1 2 3)                          ;= (1 2 3)
'(1 2 (+ 1 2))                    ;= (1 2 (+ 1 2)) 内部元素不求值
(list 1 2 (+ 1 2))                ;= (1 2 3)       内部元素求值

list?函数用来检查一个集合是不是列表。

(list? (+ 1 2 3))                 ;= false
(list? '(1 2 3))                  ;= true

vector

顺序结构，可以高效地随机访问。associative、indexed及stack抽象都是用vector实现的。

除了字面量，还可以用函数创建：

vector类似于list，求值每个元素，组成向量。
vec只接收一个参数，把这个参数转为向量。
vector?检查参数是不是vector。

(vector 1 2 3)                    ;= [1 2 3]
(vec (range 5))                   ;= [0 1 2 3 4]

把vector作为元组使用

如果函数要返回多个值，把这些值放到vector里，当元组用：

(defn euclidian-division
  [x y]
  [(quot x y) (rem x y)])

(euclidian-division 42 8)           ;= [5 2]

从元组里取某个部分也很方便：

(let [[q r] (euclidian-division 53 7)]
  (str "53/7 = " q " * 7 + " r))         ;= "53/7 = 7 * 7 + 4"

相比map，元组在使用方面不太灵活：

元组不能表示每个字段的含意。如果忘记了每个字段的意义要找到生成元组的代码，重新读懂每个字段的意义。
创建一个元组必须要一开始就提供所有的字段。

有的时候用元组问题也不大。比如，用元组来表示坐标，一眼就能理解：

(def point-3d [42 26 -7])

表示旅行线路，也不难理解：

(def travel-legs
  [["LYS" "FRA"] ["FRA" "PHL"] ["PHL" "RDU"]])

set

字面量：

#{1 2 3}                       ;= #{1 2 3}
#{1 2 3 3}                     ;= 不能有重复元素，抛异常
;= #<IllegalArgumentException Duplicate key: 3>

构造函数：

(hash-set :a :b :c :d)         ;= #{:a :c :b :d}

把集合转成set：

(set [1 6 1 8 3 7 7])          ;= #{1 3 6 7 8}

set的例子：

(apply str (remove (set "aeiouy") "vowels are useless"))
;= "vwls r slss"

(defn numeric? [s] (every? (set "0123456789") s))

(numeric? "123")               ;= true
(numeric? "42b")               ;= false

map

字面量：

{:a 5 :b 6}           ;= {:a 5, :b 6}

{:a 5 :a 5}           ;= key 不能重复 
                      ;= IllegalArgumentException: Duplicate key:

构造函数hash-map。
apply把hash-map按集合生成map。

(hash-map :a 5 :b 6)               ;= {:a 5, :b 6}
(apply hash-map [:a 5 :b 6])       ;= {:a 5, :b 6}

keys方法取得map中所有的键。
vals方法取得map中所有的值。

(keys m)             ;= (:a :b :c)
(vals m)             ;= (1 2 3)

这两个函数本质上是从map上取得「键值对」，然后把key或val函数映射到每个键值对上：

(map key m)          ;= (:a :c :b)
(map val m)          ;= (1 3 2)

map作为临时的struct

(def playlist
  [{:title "Elephant", :artist "The White Stripes", :year 2003}
   {:title "Helioself", :artist "Papas Fritas", :year 1997}
   {:title "Stories from the City, Stories from the Sea",
    :artist "PJ Harvey", :year 2000}
   {:title "Buildings and Grounds", :artist "Papas Fritas", :year 2000}
   {:title "Zen Rodeo", :artist "Mardi Gras BB", :year 2002}])

这样可以方便地聚合操作，比如把:title作为函数映射到数据上：

(map :title playlist)
;= ("Elephant" "Helioself" "Stories from the City, Stories from the Sea"
;=  "Buildings and Grounds" "Zen Rodeo")

还可以直接解构出需要的字段：

(defn summarize [{:keys [title artist year]}]
  (str title " / " artist " / " year))

用map作为数据结构，以后可以方便地通过defrecord转为更加正式的模型。

map的其他用途

group-by可以方便地给数据分组，比如以数字被模3的结果分组：

(group-by #(rem % 3) (range 10))
;= {0 [0 3 6 9], 1 [1 4 7], 2 [2 5 8]}

按歌手分组：

(def playlist
  [{:title "Elephant", :artist "The White Stripes", :year 2003}
   {:title "Helioself", :artist "Papas Fritas", :year 1997}
   {:title "Stories from the City, Stories from the Sea",
    :artist "PJ Harvey", :year 2000}
   {:title "Buildings and Grounds", :artist "Papas Fritas", :year 2000}
   {:title "Zen Rodeo", :artist "Mardi Gras BB", :year 2002}])

(group-by :artist playlist)
;= {"Papas Fritas" [{:title "Helioself", :artist "Papas Fritas", :year 1997}
;=                  {:title "Buildings and Grounds", :artist "Papas Fritas"}]
;=  ...}

通过juxt函数，可以在两个「列」上创建索引：

(group-by (juxt :col1 :col2) data)

group-by分组以后，还可以进一步生成聚合信息，传统的聚合实现的缺点是要事先加载所有数据：

(into {} (for [[k v] (group-by key-fn coll)]
           [k (summarize v)]))

key-fn是用来分组的函数，summearize是用来聚合的函数。如果数据量很大会占用很多资源。

更好的方案是用group-by对任意种类的数据进行分组，然后用redice函数进行聚合：

(defn reduce-by
  [key-fn f init coll]
  (reduce (fn [summaries x]
            (let [k (key-fn x)]
              (assoc summaries k (f (summaries k init) x))))
    {} coll))

例如结于订单数据：

(def orders
  [{:product "Clock", :customer "Wile Coyote", :qty 6, :total 300}
   {:product "Dynamite", :customer "Wile Coyote", :qty 20, :total 5000}
   {:product "Shotgun", :customer "Elmer Fudd", :qty 2, :total 800}
   {:product "Shells", :customer "Elmer Fudd", :qty 4, :total 100}
   {:product "Hole", :customer "Wile Coyote", :qty 1, :total 1000}
   {:product "Anvil", :customer "Elmer Fudd", :qty 2, :total 300}
   {:product "Anvil", :customer "Wile Coyote", :qty 6, :total 900}])

利用reduce-by算出每个人的总额：

(reduce-by :customer #(+ %1 (:total %2)) 0 orders)
;= {"Elmer Fudd" 1200, "Wile Coyote" 7200}

每种端口的所有客户名字：

(reduce-by :product #(conj %1 (:customer %2)) #{} orders)
;= {"Anvil" #{"Wile Coyote" "Elmer Fudd"}, 
;=  "Hole" #{"Wile Coyote"}, 
;=  "Shells" #{"Elmer Fudd"}, 
;=  "Shotgun" #{"Elmer Fudd"}, 
;=  "Dynamite" #{"Wile Coyote"}, 
;=  "Clock" #{"Wile Coyote"}}

在多个维度分组，每个用户，每种商品各花了多少钱：

(reduce-by (juxt :customer :product) 
  #(+ %1 (:total %2)) 0 orders)
;= {["Wile Coyote" "Anvil"] 900, 
;=  ["Elmer Fudd" "Anvil"] 300, 
;=  ["Wile Coyote" "Hole"] 1000, 
;=  ["Elmer Fudd" "Shells"] 100, 
;=  ["Elmer Fudd" "Shotgun"] 800, 
;=  ["Wile Coyote" "Dynamite"] 5000, 
;=  ["Wile Coyote" "Clock"] 300}

以上返回的结果不是嵌套的。

assoc-in方法可以用嵌套级联的方式按「复合主键」的形式生成嵌套的结构p。

(assoc-in {"a" {"b" 5}}
          ["a" "c"]
					3)                      ;= {"a" {"c" 3, "b" 5}}

(assoc-in [[nil nil nil]
           [nil nil nil]
					 [nil nil nil]] 
          [2 1]
					:on)
;= [[nil nil nil]
;=  [nil nil nil]
;=  [nil :on nil]]

get-in方法在嵌套的数据结构中取得值。

user=> (get-in {"a" {"c" 3, "b" 5}} ["a" "b"])  ;= 5
user=> (get-in {"a" {"c" 3, "b" 5}} ["a"])      ;= {"b" 5, "c" 3}

如果要返回一个嵌套的map，用assoc和隐式调用get （把map作为一个函数来使用的时候）的地方全换成assoc-in和get-in就行了：

(defn reduce-by-in
  [keys-fn f init coll]
  (reduce (fn [summaries x]
            (let [ks (keys-fn x)]
              (assoc-in summaries ks 
                (f (get-in summaries ks init) x))))
    {} coll))

(reduce-by-in (juxt :customer :product) 
  #(+ %1 (:total %2)) 0 orders)
;= {"Elmer Fudd" {"Anvil" 300, 
;=                "Shells" 100, 
;=                "Shotgun" 800}, 
;=  "Wile Coyote" {"Anvil" 900, 
;=                 "Hole" 1000, 
;=                 "Dynamite" 5000, 
;=                 "Clock" 300}}

也可以先拿到不嵌套的结果，再用assoc-in把结果转为嵌套的：

(def flat-breakup 
  {["Wile Coyote" "Anvil"] 900, 
   ["Elmer Fudd" "Anvil"] 300, 
   ["Wile Coyote" "Hole"] 1000, 
   ["Elmer Fudd" "Shells"] 100, 
   ["Elmer Fudd" "Shotgun"] 800, 
   ["Wile Coyote" "Dynamite"] 5000, 
   ["Wile Coyote" "Clock"] 300})

(reduce #(apply assoc-in %1 %2) {} flat-breakup)
;= {"Elmer Fudd" {"Shells" 100, 
;=                "Anvil" 300, 
;=                "Shotgun" 800}, 
;=  "Wile Coyote" {"Hole" 1000, 
;=                 "Dynamite" 5000, 
;=                 "Clock" 300, 
;=                 "Anvil" 900}}

以上代码对每个元素调用的是assoc-in，例如：

(assoc-in {} ["Wile Coyote" "Anvil"] 900)

不可变性和持久性

clojure推荐数据结构不可变性。

持久性与数据共享

不可变数据结构共享数据。

持久性图解：列表

(def a (list 1 2 3))
(def b (conj a 0))        ;= (0 1 2 3)
(def c (rest a))          ;= (2 3)

持久性图解：map、vector、set

assoc和dissoc来添加删除map元素：

(def a {:a 5 :b 6 :c 7 :d 8})
(def b (assoc a :c 0))           ;= {:a 5, :c 0, :b 6, :d 8}
(def c (dissoc a :d))            ;= {:a 5, :c 7, :b 6}

易变集合

只有vector、无序map和无序set有易变版本

transient函数把数据变为可变版本。
persistent!函数把可变数据变为不可变的。

transient和persistent都会在常量时间内返回。

(def v [1 2])             ;= #'user/v
(def tv (transient v))    ;= #'user/tv
(conj v 3)                ;= [1 2 3]

(persistent! tv)          ;= [1 2]
(get tv 0)                ;= IllegalAccessError: Transient used after persistent! call>

生成的元素是可变的：

(def x (transient []))            ;= 根据不可变vector生成一个可变的vector
(def y (conj! x 1))               ;= 添加一个元素，用新的引用y
(count y)                         ;= 1   旧的元素多了一个元素
(count x)                         ;= 1   新的元素也多了一个元素

检查类型是不是易变集合

(defn transient-capable?
  "Returns true if a transient can be obtained for the given collection.
   i.e. tests if `(trasient coll)` will succeed."
  [coll]
  (instance? clojure.lang.IEditableCollection coll))

可变集合支持部分的访问函数

(nth (transient [1 2]) 1)             ;= 2
(get (transient {:a 1 :b 2}) :a)      ;= 1   可变集合也可以作为函数
((transient {:a 1 :b 2}) :a)          ;= 1
((transient [1 2]) 1)                 ;= 2
(find (transient {:a 1 :b 2}) :a)     ;= ClassCastException:

seq不支持可变，因为一个序列可能比数据源存在的时间更长，所以可变集合不适合作为数据源。

可变集合操作过以后就不能再用了

更新可变集合的方法有：conj!、assoc!、dissoc!、disj!、pop!。

这些操作以后，集合就再也不能用了，只能用返回值：

(let [tm (transient {})]
  (doseq [x (range 100)]
    (assoc! tm x 0))     ;; 没有保存返回值，结果丢失
  (persistent! tm))
;= {0 0, 1 0, 2 0, 3 0, 4 0, 5 0, 6 0, 7 0}

可变集合不能组合

persistent!只把最顶层的变为不可变，内层集合不受影响：

(persistent! (transient [(transient {})]))
;= [#<TransientArrayMap clojure.lang.PersistentArrayMap$TransientArrayMap@b57b39f>]

可变集合的值没有意义

在任何情况下，可变集合没有值语言，所以不能用来比较：

(= (transient [1 2]) (transient [1 2]))        ;= 永远为false

可变集合的操作速度更快

Clojure提供了现成的into函数，用来把元素加到一个集合里：

如果要自己实现这样的功能，可以这样：

(defn naive-into
  [coll source]
  (reduce conj coll source))

(= (into #{} (range 500))
   (naive-into #{} (range 500)))  ;= true

但性能比into慢两倍：

(time (do (into #{} (range 1e6))
        nil))                              ; "Elapsed time: 1756.696 msecs"

(time (do (naive-into #{} (range 1e6))
        nil))                              ; "Elapsed time: 3394.684 msecs"

如果在增加元素时先用可变版本，最后再用persistent!把结果持久化，速度会快很多：

(defn faster-into
  [coll source]
  (persistent! (reduce conj! (transient coll) source)))

(time (do (faster-into #{} (range 1e6))
        nil))                              ; "Elapsed time: 1639.156 msecs"

只有vector、无序map和无序set有易变版本实现，所以如果把有序的集合作为 faster-into的参数，会抛异常。

元数据

添加元数据

Clojure的元数据是一个map的形式。
元数据可以关联到任何Clojure数据结构、序列、记录、符号及引用类型。
符号^标注元数据字面量。
meta读取元数据。
元数据只是对数据的备注，所以不会影响数据的打印，或是相等性比较。
元数据也是不可变的，对数据的元数据修改会返回一个新的数据，而原来的数据保持不变。

在应用场景上，要注意不要把元数据当作数据的一部分而是数据的描述。比如描述数据的版本（最后修改的时间）、数据的来源（是数据库还是缓存还是网络）。这样的好处是，只要数据的值相同，元数据备注来自数据库的数据和元数据备注来自缓存的数据在比较操作后的结果是相等的。

(def a ^{:created (System/currentTimeMillis)}
        [1 2 3])

(meta a)                ;= {:created 1322065198169}

对带有元数据的集合操作以后得到的新集合也带有原来的数据结构。

(meta (conj a 500))     ;= {:created 1450017778393}

如果元数据只有key而没有value，那么默认value为false：

(meta ^:private [1 2 3])                ;= {:private true}
(meta ^:private ^:dynamic [1 2 3])      ;= {:dynamic true, :private true}

修改元数据

with-meta把值的元数据完全替换。
vary-meta通过更新函数（一般是assoc）对元数据进行更新。

;; 修改某个key
(def b (vary-meta a assoc :modified (System/currentTimeMillis)))
(meta b)
;= {:modified 1322065229972, :created 1322065198169}

;; 用完全替换修改多个key
(def b (with-meta a (assoc (meta a)
                      :modified (System/currentTimeMillis))))
(meta b)
;= {:modified 1322065210115, :created 1322065198169}

;; 用完全替换为只有一个key
(def b (with-meta a {:modified (System/currentTimeMillis)}))
(meta b)
;= {:modified 1438527156780}

元数据是对值的备注，不会影响值的输出和相等性。

(= a b)                          ;= true
a                                ;= [1 2 3]
b                                ;= [1 2 3]

(= ^{:a 5} 'any-value
   ^{:b 5} 'any-value)           ;= true

对数据值的修改会保留元数据：

(meta (conj a 500))              ;= {:created 1319481540825}

用Clojure的集合来小试牛刀

标识符和循环引用

比如树形结构中节点记录有父节点与子节点的引用，如果是可变类型会在修改时造成问题。

思维方式的改变：从命令式到函数式

利用Clojre的数据结构，转换思维来面向值的编程。

自己动手实现经典游戏：Conway's Game of Life

如果一个生命，其周围的同类生命太少，会因为得不到帮助而死亡；<br/> 如果太多，则会因为得不到足够的生命资源而死亡。 <br/> ——英国数学家约翰·康威

我们可以规定如下的「生存定律」，每个细胞的状态由该细胞及周围八个细胞上一次的状态所决定；

如果周围正好有两个或三个细菌，那么这个的细菌可以活到下一轮。
如果周围正好有三个细菌，且当前位置为空，就生出一个新的细菌（就是无论这个点原来什么样子，这个点现在就有一个细菌了）。
如果周围细菌多于三个或少于两个，当前位置的细菌会死亡。

以非函数式风格实现

repeat方法生成重复元素的列表。

用二维的vector抽象一个棋盘，格子的状态为on或是nil。初始化一个宽为w高为h的棋盘：

(defn empty-board
  "Create a rectangular empty board of the specified width and height."
  [w h]
  (vec (repeat w (vec (repeat h nil)))))

添加格子到棋盘上：

(defn populate
  "Turns `:on` each of the cells specified as [y, x] coordinates."
  [board living-cells]
  (reduce (fn [board coordinates] (assoc-in board coordinates :on))
          board
          living-cells))

(def glider (populate (empty-board 6 6) #{[2 0] [2 1] [2 2] [1 2] [0 1]}))

(pprint glider)
;  [[nil :on nil nil nil nil]
;   [nil nil :on nil nil nil]
;   [:on :on :on nil nil nil]
;   [nil nil nil nil nil nil]
;   [nil nil nil nil nil nil]
;   [nil nil nil nil nil nil]]
;= nil

列出每个周围的8个点：

(defn neighbours [[x y]]
  "List all 8 points around `x y`, except `x+0 y+0`,
   because it is `x y` itself."
  (for [dx [-1 0 1] dy [-1 0 1] :when (not= 0 dx dy)]
    [(+ dx x) (+ dy y)]))

这里用到了

for：遍历序列，多个序列以嵌套的形式遍历。
:when：当条件成立时执行一次；相关的有:while：重复执行赶到条件不符合。

统计周围的点的值为:on：

(defn count-neighbours 
  "Count how many `:on` in neighbours"
  [board loc]
  (count (filter #(get-in board %) (neighbours loc))))

游戏的结果就是扫描每一个点：

(defn indexed-step
  "Yields the next state of the board, 
  using indices to deterine neighbords, liveness, etc."
  [board]
  (let [w (count board)
        h (count (first board))]
    (loop [new-board board x 0 y 0]
      (cond
        (>= x w) new-board                     ;= 处理完最后一行，返回
        (>= y h) (recur new-board (inc x) 0)   ;= 处理完当前行，再处理下一行
        :else 
        (let [new-liveness
              (case (count-neighbours board [x y])
                2 (get-in board [x y])
                3 :on
                nil)]
          (recur (assoc-in new-board [x y] new-liveness) x (inc y)))))))

(-> (iterate indexed-step glider) (nth 8) pprint)
; [[nil nil nil nil nil nil]
;  [nil nil nil nil nil nil]
;  [nil nil nil :on nil nil]
;  [nil nil nil nil :on nil]
;  [nil nil :on :on :on nil]
;  [nil nil nil nil nil nil]]
;= nil

去掉loop操作

优化，用reduce代替loop：

(defn indexed-step2
  [board]
  (let [w (count board)
        h (count (first board))]
    (reduce
      (fn [new-board x]
        (reduce 
          (fn [new-board y]
            (let [new-liveness 
                  (case (count-neighbours board [x y])
                    2 (get-in board [x y])
                    3 :on
                    nil)]
              (assoc-in new-board [x y] new-liveness)))
          new-board (range h)))
      board (range w))))

还可以进一步优化，把两个reduce合并起来：

(defn indexed-step3
  [board]
  (let [w (count board)
        h (count (first board))]
    (reduce
      (fn [new-board [x y]]
        (let [new-liveness 
              (case (count-neighbours board [x y])
                2 (get-in board [x y])
                3 :on
                nil)]
          (assoc-in new-board [x y] new-liveness)))
      board (for [x (range h) y (range w)] [x y]))))

去掉下标操作

接下来考虑如何去掉对下标的操作。

partition函数用来分区：

(partition n coll)
(partition n step coll)
(partition n step pad coll)

可以指定每个分区的大小和分区头之间的步长：

(partition 3 1 [0 1 2 3 4])      ;= ((0 1 2) (1 2 3) (2 3 4))
(partition 3 2 [0 1 2 3 4])      ;= ((0 1 2) (2 3 4))

如果集合的长度不够嗫后一个分区长，那么就丢弃：

(partition 3 3 [0 1 2 3 4])      ;= ((0 1 2))

如果不想丢弃最后一个块，可以指定pad参数用集合来填充：

(partition 3 3 [nil]     [0 1 2 3 4])   ;= ((0 1 2) (3 4 nil))
(partition 3 3 [nil nil] [0 1 2 3 4])   ;= ((0 1 2) (3 4 nil))
(partition 3 4 [nil]     [0 1 2 3 4])   ;= ((0 1 2) (4 nil))
(partition 3 4 [nil nil] [0 1 2 3 4])   ;= ((0 1 2) (4 nil nil))

借助于partition函数，可以很方便地找到[0 1 2 3 4]这个集合中1 2 3 这三个元素的邻居：

(partition 3 1 [0 1 2 3 4])
;= ((0 1 2) (1 2 3) (2 3 4))

0和4的邻居不在结果中，可以在集合两头连接nil，这样这两个元素的邻居也有了：

(partition 3 1 (concat [nil] [0 1 2 3 4] [nil]))
;= ((nil 0 1) (0 1 2) (1 2 3) (2 3 4) (3 4 nil))

这样可以得到用来计算工领居节点的函数window：

(defn window
  "Returns a lazy sequence of 3-item windows 
  centered around each item of coll."
  [coll]
  (partition 3 1 (concat [nil] coll [nil])))

解决了一维序列上的相邻问题，接下来要解决二维上的相邻问题。

以二维数组test-lines为例：

(def test-lines [[ 0  1  2  3  4] 
                 [ 5  6  7  8  9] 
                 [10 11 12 13 14] 
                 [15 16 17 18 19]])

如果把window应用到一个有n行的集合，得到的就是n个元组。每个元组中的三个元素分别是代表：

第\(n-1\)行。
第\(n\)行。
第\(n+1\)行。

(def line-neighbours (window (repeat nil) test-lines))

;= [[(repeat nil)     [ 0  1  2  3  4] [ 5  6  7  8  9]] 
; 	[[ 0  1  2  3  4] [ 5  6  7  8  9] [10 11 12 13 14]] 
; 	[[ 5  6  7  8  9] [10 11 12 13 14] [15 16 17 18 19]] 
; 	[[10 11 12 13 14] [15 16 17 18 19] (repeat nil)]]

每一行都是由三个长度为\(m\)的序列组成的元组，用map操作把这三个列表映射到vector 函数上，依次从三个元组里各取一个出来，就变成了\(m\)个长度为3的元组的序列了。

(def line-heads
  ((fn [[left mid right]]
     (map vector left mid right))
   line-neighbours))
   
;= ([nil  0   5] [nil  1   6] [nil  2   7] [nil  3   8] [nil  4   9])
;  ([  0  5  10] [  1  6  11] [  2  7  12] [  3  8  13] [  4  9  14])
;  ([  5 10  15] [  6 11  16] [  7 12  17] [  8 13  18] [  9 14  19])
;  ([ 10 15 nil] [ 11 16 nil] [ 12 17 nil] [ 13 18 nil] [ 14 19 nil])

注意map在映射时要同时从三个列表里各取一个元素，所以取的次数是按最短的那个列表决定的，所以line-neighbours中要用(repeat nil) 来补足长度。

然后再次把这个window函数作用到一个包含元组的元组，就可以给每个格子创建一个 3 \(\times\) 3的邻居：

(def line-neighbours
  (window line-heads))

;= ((nil         [nil 0   5] [nil  1   6]) 
;   ([nil 0 5]   [nil 1   6] [nil  2   7]) 
;   ([nil 1 6]   [nil 2   7] [nil  3   8]) 
;   ([nil 2 7]   [nil 3   8] [nil  4   9]) 
;   ([nil 3 8]   [nil 4   9] nil         ))
;  ((nil         [ 0  5  10] [  1  6  11]) 
;   ([0 5 10]    [ 1  6  11] [  2  7  12]) 
;   ([1 6 11]    [ 2  7  12] [  3  8  13]) 
;   ([2 7 12]    [ 3  8  13] [  4  9  14]) 
;   ([3 8 13]    [ 4  9  14] nil         ))
;  ((nil         [ 5 10  15] [  6 11  16]) 
;   ([5 10 15]   [ 6 11  16] [  7 12  17]) 
;   ([6 11 16]   [ 7 12  17] [  8 13  18]) 
;   ([7 12 17]   [ 8 13  18] [  9 14  19]) 
;   ([8 13 18]   [ 9 14  19] nil         ))
;  ((nil         [10 15 nil] [ 11 16 nil]) 
;   ([10 15 nil] [11 16 nil] [ 12 17 nil]) 
;   ([11 16 nil] [12 17 nil] [ 13 18 nil]) 
;   ([12 17 nil] [13 18 nil] [ 14 19 nil]) 
;   ([13 18 nil] [14 19 nil] nil        ))

把以上步骤结合起来：

(defn cell-block
  "Creates a sequence of 3x3 windows from a triple of 3 sequence"
  [[left mid right]]
  (window (map vector
               (or left (repeat nil)) mid (or right (repeat nil)))))

两个or操作是为了把window产生的nil填充成一个序列的nil，不然map会在任何一个参数为空时结束。

还有一种方法是在partition调用时增加一个pad参数来简化代码：

(defn window
  "Returns a lazy sequence of 3-item windows 
  centered around each item of coll."
  ([pad coll]
   (partition 3 1 (concat [pad] coll [pad])))
  ([coll]
   (window nil coll)))

(defn cell-block
  "Creates a sequence of 3x3 windows from a triple of 3 sequence"
  [[left mid right]]
  (window (map vector left mid right)))

在每个3 \(\times\) 3的块中，计算所有的:on数目（排除中间那一点），根据数量决定中间这一点是不是:on：

(defn liveness
  "Returns the liveness (nil or :on) of the center cell for the next step"
  [block]
  (let [[_ [_ center _] _] block]
    (case (- (count (filter #{:on} (apply concat block)))
             (if (= :on center) 1 0))  ;; count number of :on expect center
      2 center
      3 :on
      nil)))

生成一行中的每一个格子：

(defn step-row 
  "Yields the next step of the center now"
  [rows-triple]
  (vec (map liveness (cell-block rows-triple))))

生成所有的行：

(defn indexed-free-step
  "Yields the next state of the board"
  [board]
  (vec (map step-row (window (repeat nil) board))))

新的index-free-step和老的indexed-step结果应该是相同：

(= (nth (iterate indexed-step glider) 8) 
   (nth (iterate indexed-free-step glider) 8))

更加函数式地实现方式

之前的实现方案都是迭代棋盘上的每一个格子，这次换一个思路，迭代每一个现有的细胞。

每个细胞影响的范围是\(3 \times 3\)的范围，用neighbours函数标记出每个细胞的范围，再用frequencies函数统计这些范围重叠的地方：

重叠次数大于3或小于2的格子没有细胞。
重叠次数等于2的格子保持原状。
重叠次数等于3的格子一定会有细胞。

(defn step
  "Yields the next state of the world"
  [cells]
  (set (for [[loc n] (frequencies (mapcat neighbours cells))
             :when (or (= n 3) (and (= n 2) (cells loc)))]
         loc)))

这样就可以在一个无限大小的棋盘上模拟每一轮的变化，然后在要输出的时候，用populate函数把所有的点放到指定的棋盘上：

(->> (iterate step cells)
     (drop 8)
     first
     (populate (empty-board 6 6))
     pprint)

现在整个算法的的中心在neighbours函数，这个函数的算法定义了整个格子的拓扑结构。实现不同版本的neighbours函数可以支持不同的棋盘：环形、六边形、N维的的棋盘。

然后再结合对step的调整，让它更加通用：以一个高阶函数stepper，作为创建step 函数的工厂：

(defn stepper 
  "Returns a step function for Life-like cell automata.
  neighbours takes a location and return a sequential collection
  of locations. survive? and birth? are predicates on the number
  of living neighbours."
  [neighbours birth? survive?] 
  (fn [cells]
    (set (for [[loc n] (frequencies (mapcat neighbours cells))
               :when (if (cells loc) (survive? n) (birth? n))]
           loc))))

这样，对于：四边形棋盘周围有三个生出新细胞、两个三个细胞可以活下去的规则实现为：

(def seq-step
  (stepper neighbours #{3} #{2 3}))

如果要实现H.B2/S34规则（六边形的棋盘，2个邻居时新生，2、3、4个邻居存活）：

(defn hex-neighbours
  [[x y]]
  (for [dx [-1 0 1] dy (if (zero? dx) [-2 2] [-1 1])] 
    [(+ dx x) (+ dy y)]))

(def hex-step 
  (stepper hex-neighbours #{2} #{3 4}))

迷宫生成

Wilson迷宫算法是一个雕刻算法，从全是墙的地图上雕出迷宫来：

没有路：

+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+

去掉几面墙，有打通道路：

+-+-+-+
|     |
+ +-+ +
| | | |
+ +-+ +

具体算法：

随机选择一个坐标，标记为已经访问过了。
如果所有坐标都访问过了，就返回迷宫。
如果还有没有访问的坐标，随机选择一个还没有访问过的坐标，然后随机遍历，直到遇到一个已经访问过的坐标，如果在一个随机遍历过程中经过一坐标多次，那么记住每次离开这个坐标的方向。
标记所有经过的坐标为已访问，然后根据每个坐标的最后「离开方向」把墙拆了。
回到第二步重复。

如果以矩阵来表示迷宫，每个元素以bitset表示每个格子的哪些墙还在。这里有一个问题是：相邻的两个格子共用同一面墙，所以这里的数据有冗余。除了墙以下，还需要记录每个坐标离开的方向。

坐标用vector来表示，形式：[x y]。
用一个set来表示「已访问」标记。
一堵墙位于两个格子之间，所以可以用两个坐标来表示一面墙，如：[0 0] [0 1]。因为墙的表示与两个格子的表示顺序无关，所以用set表示：#{[0 0] [0 1]}。
因为迷宫也是一系列的墙，所以也可以保存为一个set。
任何顺序性的集合都可以「遍历」，如Clojure中的vector或list。
离开的方向以vector表示，如：[from to]。

实现：

(defn maze
  "Returns a random maze carved out of walls; Walls is a set of
  2-item set like `#{a b}` where a and b a locations.
  The returned maze is a set of the remaining walls"
  [walls]
  (let [paths (reduce (fn [index [a b]]                                ;; 1
                        (merge-with into index {a [b] b [a]}))
                      {} (map seq walls))                              ;; 2
        start-loc (rand-nth (keys paths))]                             ;; 3
    (loop [walls walls
           unvisited (disj (set (keys paths)) start-loc)]              ;; 4
      (if-let [loc (when-let [s (seq unvisited)] (rand-nth s))]        ;; 5
        (let [walk (iterate (comp rand-nth paths) loc)                 ;; 6
              steps (zipmap (take-while unvisited walk) (next walk))]  ;; 7 8
          (recur (reduce disj walls (map set steps))                   ;; 9
                 (reduce disj unvisited (keys steps))))
        walls))))