Clojure-JVM上的函数式编程语言(2) 集合 作者: R. Mark Volkmann

  原帖地址：http://java.ociweb.com/mark/clojure/article.html#Collections

  作者：R. Mark Volkmann

  译者：RoySong

集合（Collections）

    Clojure提供了list, vector, set 和map集合类型。Clojure同样可以采用任何Java集合类，但这并不经常出现，因为Clojure本身的集合更适合于函数式编程一些。

 

    Clojure的集合类型拥有完全不同于Java集合的特性。它们都是不可变的、多相的、持久化的。不可变意味着集合的内容不能够被改变。多相意味着集合 可以包含任意类型的对象。持久化意味着在集合的新版本创建时，旧版本依然被保存起来。Clojure采用了一种高效的方式来实现这个，即新旧版本共享内 存。举个例子，一个新版本的map包含了上千个键值对，但比起旧版本来只改变了其中一个键值对，在共享内存的情况下，只需要消耗一点点额外的内存就可以创 建新的版本。

 

    存在很多核心函数来操作各种类型的集合...实在是太多以至于无法在这儿详细描述。它们的一个小子集将在接下来被描述。记住一点，Clojure的集合是不可变的，没有函数能够改变它们。与之替代的，有很多函数采用 persistent data structures 的特性高效地从一个已存在集合创建出一个新的来。同样的，一些函数操作某个集合（比如：vector）而返回另一个类型的集合（比如：LazySeq ），它们也拥有不同的特性。

 

警告：这一节包含学习Clojure集合的重要信息，然而，它有些单调无味，呈现出的是一个接一个的函数操作各种类型的集合。如果睡意弥漫，就跳到下一节的开头，以后再来看这一段算了。

 

    count 函数计算任意类型的集合包含的元素数量，例子如下：

(count [19 "yellow" true]) ; -> 3

 

    conj 函数，是conjoin的简写，能够为某个集合添加一个或者多个元素。新元素被添加到什么位置取决于集合的类型。这将在我们接触到特定集合类型时来解释。

 

    reverse 函数能够将集合中的元素倒序排列：

(reverse [2 4 7]) ; -> (7 4 2)

 

    map函数为某集合的每个元素提供一个接受单一参数的指定处理函数，返回一个 lazy sequence。如果被处理的集合提供了每个元素，它同样也可以提供接受多参数的函数。如果这些集合拥有不同个数的元素，函数只会按照最短集合的长度来处理每个元素，其他集合中比最短集合长的元素都会被舍弃。举个例子：

; The next line uses an anonymous function that adds 3 to its argument.
(map #(+ % 3) [2 4 7]) ; -> (5 7 10)
(map + [2 4 7] [5 6] [1 2 3 4]) ; adds corresponding items -> (8 12)

 

    apply函数会将某个集合的所有元素作为参数传给指定的函数，并返回指定函数的返回值。例子；

(apply + [2 4 7]); -> 13

 

    有很多函数是从集合中检索出某个特定值，举例如下：

(def stooges ["Moe" "Larry" "Curly" "Shemp"])
(first stooges) ; -> "Moe"
(second stooges) ; -> "Larry"
(last stooges) ; -> "Shemp"
(nth stooges 2) ; indexes start at 0 -> "Curly"

 

    也有很多函数是从集合中检索出特定的多个值，举例如下；

(next stooges) ; -> ("Larry" "Curly" "Shemp")
(butlast stooges) ; -> ("Moe" "Larry" "Curly")
(drop-last 2 stooges) ; -> ("Moe" "Larry")
; Get names containing more than three characters.
(filter #(> (count %) 3) stooges) ; -> ("Larry" "Curly" "Shemp")
(nthnext stooges 2) ; -> ("Curly" "Shemp")

 

    有很多断言函数来测试集合中每个值是否满足某种条件，并返回布尔结果。它们都是“短路运算”，只会对返回结果所必需的元素求值。举例如下：

(every? #(instance? String %) stooges) ; -> true
(not-every? #(instance? String %) stooges) ; -> false
(some #(instance? Number %) stooges) ; -> nil
(not-any? #(instance? Number %) stooges) ; -> true

Lists

    Lists是一种有序集合。当从开头添加新元素或者移除元素时（常数时间），list的表现是完美的。然而在根据索引获取某个元素时（采用nth）性能表现不佳（线性时间），而且没有高效的方式来通过索引改变集合元素。

    下面是几种创建同样list的方式：

(def stooges (list "Moe" "Larry" "Curly"))
(def stooges (quote ("Moe" "Larry" "Curly")))
(def stooges '("Moe" "Larry" "Curly"))

 

    some函数可以被用来确定某个集合是否包含指定的元素，它接受某个断言函数和某个集合作为参数。

或许定义某个断言函数来找出集合中是否存在某个指定元素确实是乏味的，实际上并不鼓励这种做法。

在list中查找某个确定元素是一种线性操作。采用set来代替list明显更高效且简单。

不管怎样，下面的例子展示了如何查找：

(some #(= % "Moe") stooges) ; -> true 
(some #(= % "Mark") stooges) ; -> nil 
; Another approach is to create a set from the list
; and then use the contains? function on the set as follows.
(contains? (set stooges) "Moe") ; -> true

 

    conj 和 cons函数都可以将额外的元素添加到原有list上面去创建一个新的list。 remove函数创建一个新的list，里面仅包含原list中执行断言函数返回false结果的元素。例子如下：

(def more-stooges (conj stooges "Shemp")) -> ("Shemp" "Moe" "Larry" "Curly")
(def less-stooges (remove #(= % "Curly") more-stooges)) ; -> ("Shemp" "Moe" "Larry")

 

    into 函数创建一个包含两个list所有元素的新list。例子如下：

(def kids-of-mike '("Greg" "Peter" "Bobby"))
(def kids-of-carol '("Marcia" "Jan" "Cindy"))
(def brady-bunch (into kids-of-mike kids-of-carol))
(println brady-bunch) ; -> (Cindy Jan Marcia Greg Peter Bobby)

 

    peek 和 pop 函数能够将list当作栈来操作，它们都操作list的开始或者头元素。

 

Vectors

    Vector也是有序集合。当从结尾处添加或者删除元素时（常数时间），vecor的表现很完美。这意味着采用conj函数来添加元素比 cons要更加高效。在vector中通过索引来检索（采用nth）或者改变（采用 assoc）元素的表现都很高效（常数时间）。函数定义时采用vector来作为参数列表。

 

    这是一些创建vector的方法：

(def stooges (vector "Moe" "Larry" "Curly"))
(def stooges ["Moe" "Larry" "Curly"])

 

    除非特别需要从头部或者开始去添加或者移除元素才采用list之外，一般场合下，vector的表现都要优于list。这主要是由于vector的语法[...]要比list的语法 '(...)更加动人一点。它不会在函数、宏或者特殊form的调用中造成困扰。

 

    get函数在vector中根据索引检索出对应的元素。在之后的展示中，它同样在map中根据key检索出对应的值。

索引从0开始。get函数和nth函数很类似。它们俩都可以接受一个可选参数作为索引越界时的返回值。

如果没有这个参数，而索引越界了，get函数会返回nil，而nth函数会抛出一个异常。例子如下：

(get stooges 1 "unknown") ; -> "Larry"
(get stooges 3 "unknown") ; -> "unknown"

 

    assoc函数操作vector和map。当它应用于vector时，会创建一个替换掉指定索引元素的新vector。

如果指定的索引正好等于vector的元素个数，则会把新元素添加到vector的尾部。

如果指定的索引大于vector元素的个数，则会抛出一个 IndexOutOfBoundsException。

例子如下：

(assoc stooges 2 "Shemp") ; -> ["Moe" "Larry" "Shemp"]

 

    subvec函数会返回一个已存在vector的子集，其中的元素排序仍保留。它接受一个vector参数，

一个起始索引参数，一个可选的结束索引参数。如果结束索引参数被省略，

结果子集的末尾就是原来vector的末尾。新的结果vector同原来的vector共享结构。

 

    之前所有作用于list的代码示例都同样可以作用于vector上，peek 和 pop 函数同样可以作用在vector上，但操作的是集合的尾部，而不像作用在list上操作的是集合的头部。 conj 函数会创建一个尾部添加了新元素的vector。 cons 函数则会创建一个头部添加了新元素的vector。

 

sets

    set是元素唯一性的集合。当集合中元素不允许重复且不需要按次序添加时，比起list和vector来，set是较好的选择。Clojure支持两种类型的set，有序的和无序的。添加到有序set的元素不能彼此比较，否则会抛出一个ClassCastException。下面是创建set的数种方式：

(def stooges (hash-set "Moe" "Larry" "Curly")) ; not sorted
(def stooges #{"Moe" "Larry" "Curly"}) ; same as previous
(def stooges (sorted-set "Moe" "Larry" "Curly"))

 

    contains?函数可以作用于set和map上面。当它作用于set上面时，用于确定set是否包含某特定元素。这比采用 some 函数在list或者vector检索元素要简单多了，见如下示例：

(contains? stooges "Moe") ; -> true 
(contains? stooges "Mark") ; -> false 

 

   set能够当作函数使用，参数是它的元素，如果采用这种方式，它返回的是指定的元素或者nil。这提供了一个非常紧凑的方式来检阅集合中是否包含某指定元素。例子如下：

(stooges "Moe") ; -> "Moe"
(stooges "Mark") ; -> nil 
(println (if (stooges person) "stooge" "regular person"))

 

    上面展示的作用于list的conj 和 into 函数同样可以作用于set。不过只有有序set才能定义添加新元素的位置。


 

    disj 函数创建一个新的set，内容是移除了当前set的一个或者多个元素。例子如下：


(def more-stooges (conj stooges "Shemp")) ; -> #{"Moe" "Larry" "Curly" "Shemp"}
(def less-stooges (disj more-stooges "Curly")) ; -> #{"Moe" "Larry" "Shemp"}

 

    同样在clojure.set 命名空间中包含了如下函数： difference , index , intersection , join , map-invert , project , rename , rename-keys , select 和 union。其中的某些函数是作用于map而不是set上的。

 

Maps

    map存储key以及对应的值，其中key和值都能够是任何类型。通常map的key采用关键字，值则基于结对的key采用有序便于获取的方式存储。

 

    下面是创建map的数种方式，以棒冰的颜色做为key，口味做为值，都采用关键字来存储它们之间的关系。采用逗号分隔可以帮助理解，这些逗号是可选的，在编译和运行时会被当作空白来处理。

(def popsicle-map
  (hash-map :red :cherry, :green :apple, :purple :grape))
(def popsicle-map
  {:red :cherry, :green :apple, :purple :grape}) ; same as previous
(def popsicle-map
  (sorted-map :red :cherry, :green :apple, :purple :grape))

 

    map也可以当作函数使用，参数是其中的key。同样地，在某些情况下，key也可以当作函数使用，参数是其所属的map。但是，只有关键字类型的key可以这么使用，String和Integer 类型的key则不能。下面是几种有效的方式来获取绿色棒冰的口味，应该是apple：

(get popsicle-map :green)
(popsicle-map :green)
(:green popsicle-map)

 

    contains?函数可以作用于set和map。当它用于map时，它会检索map中是否存在对应的key。 keys 函数会返回指定map的所有key，并封装成一个序列。而 vals 函数则返回指定map的所有值序列。如下所示：

(contains? popsicle-map :green) ; -> true
(keys popsicle-map) ; -> (:red :green :purple)
(vals popsicle-map) ; -> (:cherry :apple :grape)

 

    assoc函数 可以作用于vector和map。

当它作用于map上时，它会创建一个新的map比原有map增加了任意数量的键值对。

如果新增的键值对在原有map中有已经存在的key，则对应的值会被替换成新的值。例子如下：

(assoc popsicle-map :green :lime :blue :blueberry)
; -> {:blue :blueberry, :green :lime, :purple :grape, :red :cherry}

 

    dissoc函数第一个参数是map，后面可以跟任意数量map中的key做为参数。

它返回的是一个新的map，其中包含原map移除掉所有参数key对应键值对后剩下的元素。

如果指定的参数key在map中没有，则会被忽略掉，例子如下：

(dissoc popsicle-map :green :blue) ; -> {:purple :grape, :red :cherry}

 

    如果在序列的上下文中使用map，map会象clojure.lang.MapEntry序列对象一样来处理。可以采用 doseq 和 destructuring 函数来联合处理map中所有键值对的迭代，在下面的章节中会讲到。下面的例子遍历了popsicle-map，并将key绑定在 color 上面，值绑定在flavor上。然后用name函数返回了关键字的字符串名字。

(doseq [[color flavor] popsicle-map]
  (println (str "The flavor of " (name color)
    " popsicles is " (name flavor) ".")))

 

    上面代码的输出结果是：

The flavor of green popsicles is apple.
The flavor of purple popsicles is grape.
The flavor of red popsicles is cherry.

 

    select-keys函数接收一个map以及一个key的序列做为参数，

返回一个新map包含原map中对应参数key序列的元素。

如果参数key序列中有不属于map的key，则不加理会。例子如下：

(select-keys popsicle-map [:red :green :blue]) ; -> {:green :apple, :red :cherry}

 

    conj函数将一个map的所有键值对添加到另一个map中去，如果目标map中的key存在于添加的map中，

那么目标map中这个key的值会被覆盖掉。

 

    map中的值也可以是map，并且可以嵌套任意层次。计算嵌套的值是非常容易的。同样地，改变map的嵌套值创建新map也很容易。

 

    为了证明这一点，我们来创建一个描述人的map。它拥有一个address key，对应的值是一个描述地址的map。它还拥有一个employer key，对应的值当中包含一个address 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-in函数接收一个map参数和一个key序列参数，它返回的key序列中最后一个key对应的值，

而会把之前的key都当作嵌套的路径。而 ->宏和 reduce函数可以同样达到这个目的。

这些都在下面的例子中得到证明，我们将从person map中获取到 employer的city值－－"Creve Coeur"。

(get-in person [:employer :address :city])
(-> person :employer :address :city) ; explained below
(reduce get person [:employer :address :city]) ; explained below

 

    -> 宏，被称为“thread”宏，调用了一系列的函数，将每个函数的结果做为参数传递给下个函数。

比如下面两条操作会得到一样的结果：

(f1 (f2 (f3 x)))
(-> x f3 f2 f1)

 

    同样在命名空间clojure.contrib.core中存在 -?> 宏，它跟 -> 的区别在于

如果函数调用链中的某个函数返回nil，则中止调用并返回nil。

这样就避免了抛出一个 NullPointerException。

 

    reduce 函数接收三个参数，第一参数位是一个拥有两个参数的函数f；

第二参数位是一个值val，这个参数是可选的；第三参数位是一个集合coll。

如果val有值，那么val的值和coll的第一个元素被作为参数传给函数f；

如果val没有值，或者说没有val，那么coll的头两个元素被作为参数传给函数f。

这是函数f的第一次执行，这次执行的结果和coll中的下一个元素又会作为参数传给函数f，

这样一直执行下去，直到coll中所有的元素都被处理过。

这个函数类似Ruby中的inject，或者Haskell中的foldl。

 

    assoc-in 函数接收三个参数，一个map，一个key序列和一个新的值。

其中key序列代表map嵌套的路径，函数返回的是一个key序列中最后一个key的值被改变为新的值的map。

举个例子，我们根据person获得一个employer city改变为 "Clayton"，而其他都不变的新map：

(assoc-in person [:employer :address :city] "Clayton")

 

    update-in 函数接受一个map假设为m，一个key序列[k & ks]，一个函数f以及任意数量的参数args。

毫无疑问，key序列仍然是表示map嵌套的路径。

然后，key序列中的最后一个元素对应的值以及参数args将被传给函数f，

f的返回值会作为key序列最后一个key所对应的新值。

update-in 函数返回的就是包含这个新值的新map。举个例子，

我们根据person获取一个 employer zip变为加4位格式的新map：

(update-in person [:employer :address :zip] str "-1234") ; using the str function

 

StructMaps

    StructMaps和正常的map很类似，不过它针对在多个实例间利用相同的key进行了优化，所以它不必重复。它们的用法有点类似Java Beans。在创建时会自动为StructMap生成合适的equals 和 hashCode方法。也能够轻松创建效率高于普通key索引得值的存取器函数。

 

    create-struct 函数，和 defstruct 宏（内部还是调用的 create-struct函数），都可以创建 StructMap。StructMap的key仍然是采用关键字。例子如下：

(def car-struct (create-struct :make :model :year :color)) ; long way
(defstruct car-struct :make :model :year :color) ; short way

 

    struct 函数通过指定的 StructMap创建一个实例。创建实例时指定的值必须要和定义 StructMap时给定的key顺序一致且一一对应。如果后面的key没有对应的值，则它自动对应nil。例子如下：

(def car (struct car-struct "Toyota" "Prius" 2009))

 

    accessor 函数创建一个在实例中根据key获取对应值的访问函数，以避免执行hashmap寻址。例子如下：


; Note the use of def instead of defn because accessor returns
; a function that is then bound to "make".
(def make (accessor car-struct :make))
(make car) ; -> "Toyota"
(car :make) ; same but slower
(:make car) ; same but slower

 

    在StructMap定义时没有指定的key可以添加给实例，但是，实例无法移除 StructMap定义时已经指定了的key。

 

序列(Sequences)

    序列是集合的逻辑视图。很多东西都能够被处理为序列，包括Java集合，Clojure定制的集合，

字符串，流，文件结构和xml树。

 

    很多Clojure函数返回一个延迟序列，这个序列中函数返回结果的元素除非在需要时，否则是不会被求值的。

采用延迟序列的好处在于，在序列创建时没必要去预期这个序列中会有多少元素被实际用到。

返回值是延迟序列的函数包括： cache-seq , concat , cycle , distinct , drop , drop-last , drop-while , filter , for , interleave , interpose , iterate , lazy-cat , lazy-seq , line-seq , map , partition , range , re-seq , remove ,

repeat , replicate , take , take-nth , take-while和 tree-seq。

 

    延迟序列是新手Clojure开发者经常容易混淆的地方。举个例子，下面这段代码会输出什么？

(map #(println %) [1 2 3])

 

    当在REPL中运行时，先输出1，2，3，每个数字占一行，然后在同一行上输出3个nil，这是三次println函数调用

的返回值。REPL总是对输入的表达式完全求值。然而，当这段代码作为某个脚本中的一部分运行时，可能没有任何

输出。这是因为map会把第一个参数函数应用到第二个参数集合中,返回的结果组成一个延迟序列。map函数的文本

说明清晰地指出了它返回的是延迟序列。

 

    有很多种方法让某些元素求值到延迟序列中。提取出一个单独元素的函数，比如：first , second , nth和 last都能

做到这一点。在序列中的元素会被依次求值，所以在被请求的元素之前的元素同样会被求值。举个例子，如果请求的

是最后一个元素，那么这个序列中所有的元素都会被求值。

 

    如果一个延迟序列的头保持在某个绑定中，一旦其中某个元素被求值，它的值就会被缓存起来，因此，如果再次

请求这个元素，它就不会被重新求值。

 

    dorun和 doall函数会强制元素 求值到一个单一延迟序列中， doseq宏，早先在 "Iteration " 章节中讨论过，会强制

元素的求值到一个或者多个延迟序列中。for宏，在同样的章节中讨论过，并不强制求值，而是返回另一个延迟序列。

 

    在执行时仅仅简单地需要一个副作用的情况下，采用doseq或者 dorun函数是合适的。执行的结果不会被保存，这样就能

节省相当的内存。这两个函数的返回值都是nil。而当返回结果需要保存时，采用doall函数就是合适的了，它保持了序列的

头让结果可以被缓存起来，并返回对序列的求值。

 

    下面列表阐明了对延迟序列中的元素强制求值的选项：

 

保留执行结果 抛弃执行结果仅产生副作用 在单一序列上操作 采用列表包含语法操作任意数量的序列

doall	dorun
N/A	doseq

 

    比起dorun来，优先采用doseq函数，因为代码的可读性要高些。它同样更快些，因为在dorun里面对map的调用会

创建一个新的序列。举个例子，下面两行代码会有一样的输出：

(dorun (map #(println %) [1 2 3]))
(doseq [i [1 2 3]] (println i))

 

    如果一个函数创建了一个延迟序列，其中每个元素在求值时都会产生副作用。在大多数场景下，应该采用doall函数

来强制求值其中的元素并返回结果。这样使得出现副作用的时机更加容易预测。否则调用者在多次对延迟序列求值时会

产生重复的副作用。

 

    下面的表达式会在不同行上面都输出1, 2, 3，但是它们拥有不同的返回值。do特殊form应用于此来实现匿名函数中

执行多件事，打印出传入的参数以及返回值。

(doseq [item [1 2 3]] (println item)) ; -> nil
(dorun (map #(println %) [1 2 3])) ; -> nil
(doall (map #(do (println %) %) [1 2 3])) ; -> (1 2 3)

 

    延迟序列使得创建无限序列成为可能，因为在延迟序列中不必对每个拥有的元素求值。例子如下：

(defn f
  "square the argument and divide by 2"
  [x]
  (println "calculating f of" x)
  (/ (* x x) 2.0))

; Create an infinite sequence of results from the function f
; for the values 0 through infinity.
; Note that the head of this sequence is being held in the binding "f-seq".
; This will cause the values of all evaluated items to be cached.
(def f-seq (map f (iterate inc 0)))

; Force evaluation of the first item in the infinite sequence, (f 0).
(println "first is" (first f-seq)) ; -> 0.0

; Force evaluation of the first three items in the infinite sequence.
; Since the (f 0) has already been evaluated,
; only (f 1) and (f 2) will be evaluated.
(doall (take 3 f-seq))

(println (nth f-seq 2)) ; uses cached result -> 2.0

 

    然后我们对上面的程序做个改变，不在绑定中保持延迟序列的头。注意如何将已定义的序列做为函数的返回结果而不是

绑定值。这样就并未缓存集合中元素求值的结果，这样会降低内存占用，但是比起之前的程序来说，对集合中元素的请求

会更加低效。

(defn f-seq [] (map f (iterate inc 0)))
(println (first (f-seq))) ; evaluates (f 0), but doesn't cache result
(println (nth (f-seq) 2)) ; evaluates (f 0), (f 1) and (f 2)

 

    另外一种不在绑定中保持延迟序列头的做法是直接将序列传给一个会对其元素进行求值的函数。例子如下：

(defn consumer [seq]
  ; Since seq is a local binding, the evaluated items in it
  ; are cached while in this function and then garbage collected.
  (println (first seq)) ; evaluates (f 0)
  (println (nth seq 2))) ; evaluates (f 1) and (f 2)

(consumer (map f (iterate inc 0)))