在 Clojure 中递归集合的惯用方法

发布于 2025-01-03 18:53:16 字数 1073 浏览 2 评论 0原文

我试图了解 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) 深入挖掘集合
（不是 (coll? xs)) 检查原子

原文

I'm trying to understand what is the idiomatic way in Clojure to recurse through a tree or a list represented by a Clojure list (or another collection type).

I could write the following to count the elements in a flat collection (ignore the fact that it's not tail-recursive):

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

Now in Scheme or CL all the examples only ever do this over lists, so the idiomatic base case test in those languages would be (nil? xs). In Clojure we'd like this function to work on all collection types, so is the idiomatic test (nil? (seq xs)), or maybe (empty? xs), or something completely different?

The other case I'd like to consider is tree traversal, i.e. traversing through a list or vector that represents a tree, e.g. [1 2 [3 4].

For example, counting the nodes in a tree:

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

Here we use (not (coll? tree)) to check for atoms, whereas in Scheme/CL we'd use atom?. We also use (nil? (seq tree)) to check for an empty collection. And finally we use first and rest to destructure the current tree to the left branch and the rest of the tree.

So to summarise, are the following forms idiomatic in Clojure:

(nil? (seq xs)) to test for the empty collection
(first xs) and (rest xs) to dig into the collection
(not (coll? xs)) to check for atoms

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

音盲 2025-01-10 18:53:16

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

(if (seq coll)
  ...
  )

nil? 是不必要的，因为非 nil 返回值seq 保证是一个 seq，因此既不是 nil 也不是 false，因此是 true。

如果您想先处理nil情况，可以将if更改为if-not或seq为空？;后者被实现为 seq 和 not 的组合（这就是为什么编写 (not (empty? xs)) 并不符合惯用语，参见空？的文档字符串）。

至于 first / rest ——记住 rest 的严格变体 next 很有用，使用这比将 rest 包装在 seq 中更惯用。

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

The idiomatic test for a non-empty seqable is (seq coll):

(if (seq coll)
  ...
  )

The nil? is unnecessary, since a non-nil return value from seq is guaranteed to be a seq and thus neither nil nor false and therefore truthy.

If you want to deal with the nil case first, you can change the if to if-not or seq to empty?; the latter is implemented as a composition of seq with not (which is why it is not idiomatic to write (not (empty? xs)), cf. the docstring of empty?).

As for first / rest -- it's useful to remember about the strict variant of rest, next, the use of which is more idiomatic than wrapping rest in a seq.

Finally, coll? checks if its argument is a Clojure persistent collection (an instance of clojure.lang.IPersistentCollection). Whether this is an appropriate check for "non-atoms" depends on whether the code needs to handle Java data structures as non-atoms (via interop): e.g. (coll? (java.util.HashSet.)) is false, as is (coll? (into-array [])), but you can call seq on both. There is a function called seqable? in core.incubator in the new modular contrib which promises to determine whether (seq x) would succeed for a given x.

回复收藏 0 原文

差↓一点笑了 2025-01-10 18:53:16

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

(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 和空集合情况
您可以使用解构来命名第一个和下一个函数

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

I personally like the following approach to recurse through a collection:

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

Features:

(seq coll) is idiomatic for testing whether a collection is empty (as per Michal's great answer)
if-let with (seq coll) automatically handles both the nil and empty collection case
You can use destructuring to name the first and next elements as you like for use in your function body

Note that in general it is better to write recursive functions using recur if possible, so that you get the benefits of tail recursion and don't risk blowing up the stack. So with this in mind, I'd actually probably write this specific function as follows:

(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

回复收藏 0 原文

~没有更多了~