在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)) 检查原子

Answer 1

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

(if (seq coll)
  ...
  )

这nil?是不必要的,因为nil来自非返回值seq的保证是seq,因此既不是nil也不false是真的.

如果你想先处理这个nil案子,你可以改成ifto if-not或seqto empty?; 后者是作为seqwith 的组合实现的not(这就是为什么它不是写作的惯用(not (empty? xs)),参见文档字符串empty?).

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

最后,coll?检查它的参数是否是Clojure持久集合(实例clojure.lang.IPersistentCollection).这是否是对"非原子"适当的检查取决于代码是否需要处理Java数据结构为非原子(通过互操作):比如(coll? (java.util.HashSet.))是false按原样(coll? (into-array [])),但你可以叫seq上两个.在新的模块化contrib中有一个函数调用seqable?in core.incubator,它承诺确定是否(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 coll)是测试集合是否为空的惯用语(根据Michal的好答案)
• if-let with(seq coll)自动处理nil和empty collection case
• 您可以使用解构来命名第一个和下一个元素,以便在函数体中使用

请注意,一般情况下,如果可能的话,最好使用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