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)))

最近更新于0001-01-01