Clojure中递归遍历集合的惯用方式

Question

我试图理解在Clojure中遍历树或由Clojure列表（或其他集合类型）表示的列表的惯用方式。

我可以编写以下内容来计算平面集合中的元素数量（忽略它不是尾递归的事实）:

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

现在在Scheme或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)) 来检查原子，在Scheme/CL中我们会使用atom?。 我们还使用(nil? (seq tree)) 来检查空集合。 最后，我们使用 first 和 rest 来解构当前树到左分支和其余部分。

因此，总结一下，在Clojure中以下形式是否习惯用语：

• (nil? (seq xs)) 用于检测空集合
• (first xs) 和 (rest xs) 用于深入集合
• (not (coll? xs)) 用于检查原子

- liwp

Answer 1

seqable序列的非空惯用测试为(seq coll)：

(if (seq coll)
  ...
  )

nil?是不必要的，因为seq返回非nil值保证是序列，因此既不是nil也不是false，因此为真值。如果您想首先处理nil情况，可以将if更改为if-not或将seq更改为empty?；后者是将seq与not组合实现的（这就是为什么编写(not (empty? xs))不如读取empty?的文档字符串）。关于first/rest——记住严格变体next，它的使用比在seq中包装rest更符合习惯用法。最后，coll?检查其参数是否为Clojure持久集合（即clojure.lang.IPersistentCollection的实例）。对于“非原子”是否适用此检查取决于代码是否需要处理Java数据结构作为非原子（通过Interop）：例如(coll? (java.util.HashSet.))为false，(coll? (into-array []))也是如此，但两者都可以调用seq。在新的模块化贡献中core.incubator中有一个名为seqable?的函数，它承诺确定是否会针对给定的x成功调用(seq x)。

- Michał Marczyk

---

感谢您的回答。关于 rest/next，您的意思是我应该在递归调用中使用 (length (next xs))，因为我无论如何都会在集合上调用 seq？至于 coll?，此时我只对本机Clojure集合类型感兴趣，所以 coll? 对我来说就足够了。 - liwp

不客气。我主要是指直接在rest的返回值上调用seq（例如，(if-let [new-xs (seq (rest xs))] ...)），这种习语明确使用(next xs)，并且使用rest进行recur只有在下一次迭代中可能实际不调用seq时才有意义。在你的length函数中，我可能仍然会使用next来尽可能清晰地表明该函数是严格的，但我认为这并没有太大差别。 - Michał Marczyk

Answer 2

我个人喜欢用以下方法对集合进行递归：

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

特点：

• (seq coll)是惯用的方式，用于测试集合是否为空（根据Michal的好答案）
• if-let与(seq coll)一起使用，自动处理nil和空集合的情况
• 您可以使用解构将第一个和下一个元素命名为您喜欢的名称，以便在函数体中使用

请注意，通常最好使用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

- mikera

---

不错！我想集中讨论集合递归惯用语而不涉及尾调用，因此我有意不使用“recur”。 - liwp

@mikera 这对于懒惰的无限序列有效吗？（例如，出于明显原因，使用map作为示例）。我的理解是向量不是懒惰的，所以(if-let [[x＆xs]（seq coll）]会崩溃，对吗？（如果是这样，有什么解决方法）？ - Dax Fohl

这种技术对于惰性无限序列来说效果还不错，但只要你不保留头部引用。如果你保留了序列开头的引用，垃圾回收器就无法移除任何内容，最终你会耗尽内存。 - mikera