Clojure通过集合递归的习惯方式

Question

我想了解Clojure通过Clojure列表（或其他集合类型）表示的树或列表进行递归的习惯方式。

我可以写下面的计算在平面集合中的元素（忽视的事实是它不是尾递归）：

(defn length 
    ([xs] 
    (if (nil? (seq xs)) 
     0 
     (+ 1 (length (rest xs)))))) 

现在计划或CL所有的例子永远只能这样做了列表，所以这些语言的惯用基本情况测试将是(nil? xs)。在Clojure中，我们希望这个函数可以在所有类型的集合上工作，例如地理测试(nil? (seq xs))，或者(empty? xs)，或者完全不同的东西？

我想考虑的另一种情况是遍历树，即遍历表示树的列表或向量，例如树。 [1 2 [3 4]。

例如，在一棵树的计算节点：

(defn node-count [tree] 
    (cond (not (coll? tree)) 1 
     (nil? (seq tree)) 0 
     :else (+ (node-count (first tree)) (node-count (rest tree))))) 

这里我们使用(not (coll? tree))检查原子，而在方案/ CL，我们会使用atom?。我们还使用(nil? (seq tree))来检查一个空集合。最后，我们使用first和rest将当前树解构到左侧分支和树的其余部分。

所以总结一下，有以下几种形式Clojure中惯用：

• (nil? (seq xs))来测试空收集
• (first xs)和(rest xs)钻进去收集
• (not (coll? xs))检查原子

Answer 1

非空seqable的惯用测试是(seq coll)：

(if (seq coll) 
    ... 
) 

的nil?是不必要的，因为来自seq非nil返回值被保证是SEQ并且因此既不nil也不false因此truthy。

如果你想先处理nil情况下，您可以更改if到if-not或seq到empty?;后者实现为seq与not的组合（这就是为什么编写(not (empty? xs))，比较empty?的文档字符串的原因）。

至于first/rest - 它要记住的rest，next严格的变种，它的使用比在seq包装rest更地道是非常有用的。

最后，coll?检查它的参数是否是Clojure持久集合（clojure.lang.IPersistentCollection的实例）。这是否适合检查“非原子”取决于代码是否需要将Java数据结构作为非原子处理（通过互操作）：例如， (coll? (java.util.HashSet.))为false，与(coll? (into-array []))一样，但您可以拨打seq。 core.incubator中有一个叫做seqable?的函数在新的模块化contrib中，它承诺确定(seq x)对于给定的x是否会成功。

Answer 2

我个人很喜欢下面的方法通过集合递归：

(defn length 
    "Calculate the length of a collection or sequence" 
    ([coll] 
    (if-let [[x & xs] (seq coll)] 
     (+ 1 (length xs)) 
     0))) 

特点：

• （SEQ科尔）是惯用用于测试集合是否为空（按米哈尔的伟大答案）
• if-let with（seq coll）自动处理零收集和空收集案例
• 您可以使用destruc图灵正如你在函数体

需要注意的是，一般最好是使用recur如果可能的话写递归函数，使您获得尾递归和唐的好处喜欢使用到名字的第一个和下一个元素没有风险吹起堆栈。所以考虑到这一点，我实际上可能写如下具体功能：

(defn length 
    "Calculate the length of a collection or sequence" 
    ([coll] 
    (length coll 0)) 
    ([coll accumulator] 
    (if-let [[x & xs] (seq coll)] 
     (recur xs (inc accumulator)) 
     accumulator))) 

(length (range 1000000)) 
=> 1000000