03.小火汁，没想到你也是序列
在上一节中，我们粗略的概览了 Clojure 的复合类型，在这一节以及下一节中，我们会更加深入这个主题。首先，我们会对 Clojure 中序列的概念做一个简单的介绍。然后我们会引入高阶函数的概念——Clojure 大量使用了高阶函数作为操作序列的工具。接着我们会列举一些 Clojure 中各种常用的序列操作函数。
在本章节的最后，我们会动手实现两个函数——一个 compress 函数，用于对序列进行“压缩”；一个 count-map 函数，用于对序列中重复出现的值进行计数。
一切皆序列？
上一节我们提到的字符串、列表、向量、映射表、集合之间并不是毫无关联的——它们有一个共同的抽象：序列（seq）。我们可以用函数 seq 将一个复合结构转化成序列：
(class (seq "abc"))
;=> clojure.lang.StringSeq
(class (seq [1 2 3]))
;=> clojure.lang.PersistentVector$ChunkedSeq
序列并没有底层的实现，而是一个抽象的接口。序列拥有三个基本操作：
- (first seq) ——返回序列的第一项
- (**rest***seq*) ——返回除第一项以外的余项
- (cons elem seq) ——返回一个新序列，将 elem 添加到 seq 的前面
(def nums [1 2 3])
(first nums) ;=> 1
(rest nums) ;=> (2 3)
(cons 0 nums) ;=> (0 1 2 3)
可以看到，任何一个可以切割成头尾两部分的对象都可以是序列。我们再举几个序列的例子：
- 一个字符串（字符序列）
- 孙悟空的妖怪女朋友们（谢罪序列）
- 野兽先辈是女生的 114514 种假说（恶 臭 序 列）
- 全体自然数的集合（无限长序列）
- 系统中的状态变化（惰性序列）
可以看到，序列是一个非常抽象的概念，除了能够表示像向量这样的集合以外，序列还能表示各种存在先后顺序的事物。我们将一个可以转化为序列的结构称作可序化结构。
有了序列我们就可以实现各种通用的算法，而不用针对每种特定的序列单独实现了。
值得一提的是，对空列表、空向量等对象调用 seq 函数时，将会返回 nil。我们之前提到过空列表（’( )）、空向量（[ ]）等对象的真值是 true，这在实现一些算法时很不方便，而使用 seq 就能解决这个问题：
;无法正常工作的my-empty
(defn my-empty? [xs] (if xs true false))
;=> #'user/my-empty?
(my-empty? [])
;=> true
;使用seq修复这个bug
(defn my-empty? [xs] (if (seq xs) true false))
;=> #'user/my-empty?
(my-empty? [])
;=> false
将一个复合结构转化成 seq 再进行操作，是一种 Clojure 的惯用法。
高阶函数
Clojure 提供了一组用于操作序列的高阶函数，所谓高阶函数就是满足下面两个条件中至少一个的函数：
- 接受一个函数作为参数的函数
- 返回一个函数作为返回值的函数
我们在 Java 中常用的一些设计模式，如策略模式，实际上就是使用面向对象的方式实现高阶函数的效果。
使用高阶函数操作数据结构已经被证明是一种行之有效的方法。包括 C++、Java、C#在内的许多语言都已经加入了使用高阶函数操作数据的接口（如 Java8 引入的 Stream 和 C#的 Linq）。
在过程式的编程思想中，我们通常使用循环来操作数据结构。下面看几个 Java 中的例子：
// 列表求和
public static int sum(List<Integer> ints) {
int acc = 0;
for (int n : ints) {
acc += n;
}
return acc;
}
// 找出列表中所有的正整数
public static List<Integer> filterPos(List<Integer> ints) {
List<Integer> temp = new ArrayList<>();
for (int n : ints) {
if (n > 0) {
temp.add(n);
}
}
return temp;
}
// 将列表中所有的整数翻倍
public static List<Integer> doubled(List<Integer> ints) {
List<Integer> temp = new ArrayList<>();
for (int n : ints) {
temp.add(2 * n);
}
return temp;
}
下面让我们找出循环中存在的问题，然后循序渐进的过渡到高阶函数的世界。
我们先从 sum 开始，sum 现在工作的很好：
List<Integer> ints = Arrays.asList(1, 2, 3, 4);
System.out.println(sum(ints));
//-> 10
但现在我们又有了新的需求，我们要对这个列表进行累乘。对于循环来说，我们没有办法，只好重新写一个新的静态方法：
public static int product(List<Integer> ints) {
int acc = 1;
for (int n : ints) {
acc *= n;
}
return acc;
}
现在让我来描述一下我是如何实现 product 的：首先我将 sum 的方法体整！个！拷！贝！下！来！，然后将变量 acc 的初始值改成 1，接着将+=改成*=，product 就完成了。
你或许已经意识到了：sum 和 product 有着惊人的相似程度，那么，有没有办法对它们进行抽象呢？
让我们把视线转回 Clojure，看看 Clojure 是怎么做的：
(defn sum [xs] (reduce + 0 xs))
(defn product [xs] (reduce * 1 xs))
(def ints [1 2 3 4])
(sum ints) ;=> 10
(product ints) ;=> 24
reduce 就是我们想要的抽象，它表示“规约”操作，所谓规约就是把一系列值“压缩”成一个值，诸如累加、累乘都是规约。我们可以试着自己实现一个 reduce：
(defn myreduce [fn acc xs]
(if-let [[head & tail] (seq xs)]
(recur fn (fn acc head) tail)
acc))
(myreduce + 0 [1 2 3 4]) ;=> 10
myreduce 接受 3 个参数，fn 表示一个二元函数（比如（+）、（*）等），acc 表示累积量的初始值，xs 表示传入的可序化结构。
if-let 是 if 和 let 的结合体，myreduce 首先会判断(seq xs)是否为 nil，然后：
- 如果不为 nil，则对 seq 进行解构，分成头尾两部分。之后将 seq 的第一项（头部）和 acc 使用函数 fn 结合，然后对 myreduce 进行递归。
- 如果为 nil，说明容器中所有的元素都已经消耗完毕，此时 acc 就是我们求得的结果了。
通过 reduce，我们成功的将一种常见的循环结构进行了抽象，变成了一个可复用的高阶函数。
现在再来看看那个循环写法的例子，filterPos 和 doubled 静态方法实际上也代表着两种常见的循环结构：过滤（filter）和映射（map）。来看看 Clojure 中如何实现它们：
(defn filter-pos [xs]
(filter pos? xs))
(defn doubled [xs]
(map #(* % 2) xs))
(filter-pos [1 -1 -2 3 4]) ;=> (1 3 4)
(doubled [1 2 3 4]) ;=> (2 4 6 8)
来看看 map 和 filter 应该如何实现，其结果可能会让你大吃一惊：
(defn mymap [f xs]
(seq (reduce #(conj %1 (f %2)) [] xs)))
(defn myfilter [pred xs]
(seq (reduce #(if (pred %2) (conj %1 %2) %1) [] xs)))
(mymap str [1 2 3]) ;=> ("1" "2" "3")
(myfilter pos? [1 -1 2 -2]) ;=> (1 2)
reduce 看起来没有我们想象的那么简单——map 和 filter 居然也可以使用 reduce 实现！这是怎么回事呢？让我们对比一下循环版本的 sum 和 doubled 的实现：
public static int sum(List<Integer> ints) {
int acc = 0; // ①
for (int n : ints) {
acc += n;// ②
}
return acc;
}
public static List<Integer> doubled(List<Integer> ints) {
List<Integer> temp = new ArrayList<>(); // ①
for (int n : ints) {
temp.add(2 * n); // ②
}
return temp;
}
比较一下两处 ① 和两处 ②，我们可以发现，doubled 实际上也是一种规约操作，只不过规约之后的结果仍是一个列表。在 sum 中，我们使用（+）作为累加器，而在 doubled 中，累加器的效果是将一个变换后的值添加到列表的尾部。
在 Clojure 中，如果我们想在向量尾部添加元素，可以使用 conj 函数：
(conj [1 2 3] 4) ;=> [1 2 3 4]
！注：conj 函数也可以对其他容器使用，但是添加元素的方式视容器而定，对于向量来说 conj 是在尾部添加元素；对于 list 来说则是在头部添加元素。
因此，我们可以使用 reduce+conj 来不断累积列表，比如：拷贝整个列表：
;拷贝列表
(reduce conj [] [1 2 3]) ;=> [1 2 3]
;反转列表
(reduce #(cons %2 %1) [] [1 2 3]) ;=> (3 2 1)
而 map 和 filter 只不过是在这个累积列表的过程中，加上映射和过滤的操作。
太多括号了？
现在让我们实现这样一个需求：
- 输入一个整数列表
- 去掉其中的负数
- 将每一项加一
- 最后求和
我们可以活用刚才学到的高阶函数的知识：
(defn filter-pos-inc-sum [xs]
(reduce + 0
(map inc
(filter pos? xs))))
(filter-pos-inc-sum [1 2 -1 -2 3]) ;=> 9
emmm，这个函数确实工作的很好，但是可读性不佳——首先，括号嵌套了太多层，显得不太优雅。其次，map 明明是比 reduce 先发生的，但在我们的函数中，却是先写 reduce 在写 map。我们可以使用-»宏改善我们的代码：
(defn filter-pos-inc-sum [xs]
(->> xs
(filter pos?)
(map inc)
(reduce + 0)))
(filter-pos-inc-sum [1 2 -1 -2 3]) ;=> 9
-»宏将一个个函数串联成一条“流水线”，xs 首先会被 filter“加工”（也就是说，xs 被传递给函数的最后一个参数），其结果会被传递给 map，最后是 reduce。可以看到，在使用了-»宏之后，filter、map 和 reduce 被组织到了同一层次当中，而不是一个嵌套的调用结构。
除了操作数据结构以外，-»也可以用于数学计算之类的地方：
(->> 1114514
(+ 1919)
(/ 810))
;=> 90/12930
-»还有一个亲戚->宏，不过它只能使用接受一个参数的函数作为“管道”：
(-> 25 Math/sqrt int inc str) ;=> "6"
序列操作一览
了解了高阶函数的概念之后，让我们来看看 Clojure 提供了哪些序列操作。
构造序列
除了最常用的 seq 函数以外，Clojure 还提供了一些其他的构造序列的函数。
range函数用于表示一个区间（左闭右开）：
(range start? end step?)
(range 5) ;=> {0 1 2 3 4)
(range 2 10) ;=> (2 3 4 5 6 7 8 9)
(range 0 10 2) ;=> (0 2 4 6 8)
repeat函数用于不断重复某一个值：
(repeat "+1") ; 无限+1，就和你的复读机群友一样
;=> ...永远不会停下
(repeat 3 "hello")
;=> ("hello" "hello" "hello")
repeat 还有一个亲戚repeatedly，不同之处在于 repeatedly 接受一个无参函数，通过不断重复调用这个函数来构建序列。这很适合用来构造随机数序列：
(defn rand-int-seq [max]
(repeatedly #(rand-int max)))
(->> (rand-int-seq 10)
(map #(+ % 10)) ;=>随机数取值范围为[10, 20)
(take 10)
)
iterate 函数用于构造一个生成器：
(iterate fnext seed)
使用 iterate 构造的序列满足以下条件：
- 序列的首项为 seed
- 设序列的低 n-1 项为 x，那么序列的第 n 项为(fnext x)
在之前的章节中我们已经试过使用 iterate 表示全体自然数的集合，现在让我们来看一个稍复杂的例子：构造一个斐波那契数列。
(def fib
(letfn [(fnext [[a b]] [b (+ a b)])] ;定义局部函数
(->> (iterate fnext [0 1])
(map first))))
(take 10 fib)
;=> (0 1 1 2 3 5 8 13 21 34)
这段代码不是特别直观，我们先将(map first)去掉，看看这个“半成品”是什么样子的：
(take 10
(iterate
(fn [[a b]] [b (+ a b)])
[0 1]))
;=> ([0 1] [1 1] [1 2] [2 3] [3 5] [5 8] [8 13] [13 21] [21 34] [34 55])
可以看到，fib 首先生成了一个二维的序列，其首项是斐波那契数列的两个初值，0 和 1 。fib 序列的后一项的第一个值是前一项的第二个值，而第二个值则可以通过序列的前一项求和得到。之后我们对 fib 的半成品进行了 map，只取其第一项就得到了斐波那契数列。
之所以这么实现是因为计算 fib 的第 n 项需要用到第 n-1 和 n-2 项两个值。
cycle函数用于对一个序列进行无线循环：
(def zero-one [0 1])
(take 10 (cycle zero-one))
;=> (0 1 0 1 0 1 0 1 0 1)
concat函数用于连接多个序列：
;字母表序列
(defn range-char [begin end]
(map char
(range (int begin) (inc (int end)))))
(def charset
(concat
(range-char \A \Z)
(range-char \a \z)))
charset
;=> (\A \B \C ...\Z \a \b \c ...\z)
interleave使用交错的方式将多个容器合并成一个：
(interleave natural-nums charset)
;=> (0 \A 1 \B 2 \C ... 49 \x 50 \y 51 \z)
如你所见，interleave 可以将无限序列和有限序列交织在一起，当其中一个序列被消耗完毕时就会停止。
interleave 的亲戚interpose将一个分隔符插入到序列的每两项之间，我们可以使用 interpose 在字符串中间插入男魂（♂）从而让它变得哲 ♂ 学
(defn philosophize [s]
(apply str (interpose \♂ s)))
(philosophize "幻想乡")
;=> "幻♂想♂乡"
类似的还有使用分隔符连接字符串的join函数：
(join " " ["Hello" "World"])
;=> "Hello World"
每一种 Clojure 容器都有一个对应的函数用来构造它们，这些函数都接受任意参数：
(list & elems)
(vector & elems)
(hash-set & emels)
(hash-map & keys-values)
通过 apply 函数我们可以让一个序列在各个容器间转换：
(apply hash-map [:a 1 :b 2 :c 3])
{:c 3, :b 2, :a 1}
vector 和 hash-set 分别有一个亲戚 vec 和 set，它们不接受可变参数，而是接受一个容器：
(set [:a :b :c])
;=> #{:c :b :a}
(vec {:a 1, :b 2, :c 3})
;=> [[:a 1] [:b 2] [:c 3]]
过滤、截取序列
Clojure 中常用的过滤函数 filter 我们在上文中已经介绍过了，这里不再赘述。
remove与 filter 相反，去掉序列中满足谓词的元素
(remove even? (range 10))
;=> (1 3 5 7 9)
take函数截取序列的前 n 项，如果 n 大于序列的总长度，则返回整个序列：
(take 3 natural-nums)
;=> (0 1 2)
take-while截取前 n 个满足条件的元素
(take-while #(< % 10) natural-nums)
;=> (0 1 2 3 4 5 6 7 8 9)
drop、drop-while与 take 相反，舍弃序列的前 n 项
(drop 5 (range 10))
;=> (5 6 7 8 9)
split-at在给出的索引处将序列切成两份
(split-at 5 (range 10))
;=> [(0 1 2 3 4) (5 6 7 8 9)]
split-with接受一个谓词 pred，将序列分成(take-while pred coll)和(drop-while pred coll)两份
(split-with #(< % 3) (range 10))
;=> [(0 1 2) (3 4 5 6 7 8 9)]
序列谓词
序列谓词用于判断序列是否满足一定的条件。
**every?**判断是否序列的所有项都满足谓词
(every? pos? [0 1 2]) ;=> true
(every? pos? [-1 1 2]);=> false
some用于判断序列中是否存在满足谓词的元素
(some pos? [-1 1 2]) ;=> true
(some pos? [-1 -2 0]) ;=> nil
注意，some 不以问号结尾，并且在没有任意项满足条件时返回 nil（而不是 false），这是因为尽管 some 总是被当做谓词使用，但其本身并非谓词：
;identity总是返回其参数本身
(some identity [nil false 1 2 3])
;=> 1
实际上 some 的运作方式是挨个对元素调用传入的函数，当找到第一个返回值不为 nil 或 false 的项 x 时，返回 f(x)。之所以(some pos? [-1 1 2])返回 true 是因为 pos？本身就返回布尔值。
**not-every?**行为与 every 相反，如果存在不满足谓词的元素则返回真，否则返回假；not-any则与 some 相反，当所有元素都不满足谓词时才返回真，这里不再赘述。
序列变换
常用的序列变换操作 map 和 reduce 已经在上文中介绍过了，这里不再赘述。
map 有一个特点就是它永远无法改变序列的总长度，但mapcat可以做到。顾名思义，mapcat 就是 map + concat。
(defn uncompress [coll]
(mapcat (fn [[x n]] (repeat n x)) coll))
(uncompress [[:a 2] [:b 3] [:c 4]])
;=> (:a :a :b :b :b :c :c :c :c)
有趣的是，mapcat 也可以用来实现 map、filte，这证明 mapcat 是一个非常强大的函数
(defn mymap [f coll]
(mapcat #(cons (f %) nil) coll))
(defn myfilter [pred coll]
(mapcat (fn [x] (if (pred x) (cons x nil) nil)) coll))
sort函数和其他语言的牌序函数没什么不同：
(sort [4 1 3 2])
;=> (1 2 3 4)
sort 函数能够接受一个谓词作为比较方法：
(sort > [4 1 3 2])
;=> (4 3 2 1)
sort-by 会先对容器中的元素调用一个函数 fn，根据 fn 的结果来进行排序
(def scores [
{:name "Khellendros", :score 100}
{:name "KMR", :score 114514}
{:name "Jack", :score 80}
])
(sort-by :score > scores)
;=> ({:name "KMR", :score 114514} {:name "Khellendros", :score 100} {:name "Jack", :score 80})
上面的代码会根据每个人的成绩降序排列 scores 序列。
group-by 能够对序列进行分组，首先对序列中的每一项调用一个函数 f，然后将返回值相同的项放在同一个组里，以 f 的返回值作键：
(group-by identity [:a :a :b :c :b]) ;=> {:a [:a :a], :b [:b :b], :c [:c]} partition用于将序列分为 n 个一组：
(partition 2 (range 10))
;=> ((0 1) (2 3) (4 5) (6 7) (8 9))
计数函数 count-map
我们先从一个简单的例子开始：统计序列中相同的元素的数量：
(count-map [:a :b :a :c :a :b])
;=> ([:a 3], [:b 2], [:c 1])
我们可以使用 group-by 对序列进行分组，得到一个映射表，然后用 map 和 count 将映射表的 value 转换成长度：
(defn count-map [coll]
(->> coll
(group-by identity)
(map (fn [[k vs]] [k (count vs)]))))
压缩函数 compress
当我们需要处理大量数据时，最好先对数据进行压缩在进行运算。compress 就是一个简单的压缩算法。他会将邻接的 n 个相同的元素 x 压缩成 x n 的形式：
(compress [:a :a :a :a :b :b :b :c :a :a])
;=> (:a 4 :b 3 :c 1 :a 2)
当我们需要将多个元素压缩成 1 个时，我们首先会想到 reduce。
reduce 的本质是对列表进行“累积”，而 compress 需要累积的值有三项：
- 前一个元素的值
- 前一个元素已累积的数量
- 已完成压缩的序列
有了思路之后我们就能写下 cmpr 函数：
;x-前一个元素
;n-前一个元素已积攒的l数量
;acc-已完成压缩的序列
;elem-当前元素
(defn cmpr [[x n acc] elem]
(if (= x elem)
[x (inc n) acc] ;如果x与elem相等，增加n的值
[elem 1 (conj acc x n)] ;否则开始积攒elem，将x和n加入已完成压缩序列
))
显而易见的，reduce 的初值应当设为[nil 0 []]。
注意，当 reduce 完成后，序列的最后一项还没有被加进 acc 里面，我们需要进行一个收尾操作：
(defn end-reduce [[x n acc]] (conj acc x n ))
另外记得结果序列的前两项是 nil 0，需要用 drop 2 舍弃它们。
将以上内容整合起来，compress 函数就完成了：
(defn compress [coll]
(letfn [
(cmpr [[x n acc] elem]
(if (= x elem)
[x (inc n) acc]
[elem 1 (conj acc x n)]))
(end-reduce [[x n acc]] (conj acc x n))]
(->> coll
(reduce cmpr [nil 0 []])
end-reduce
(drop 2)))