3

我正在随机阅读 Clojure 源代码，我看到分区函数是根据递归定义的，而不使用 "recur"：

(defn partition
  ... ...
  ([n step coll]
     (lazy-seq
       (when-let [s (seq coll)]
         (let [p (doall (take n s))]
           (when (= n (count p))
             (cons p (partition n step (nthrest s step))))))))
  ... ...)

这样做有什么理由吗？

4

3 回答 3

7

分区是惰性的。递归调用partition发生在 a 的主体内lazy-seq。因此，它不会立即被调用，而是在一个特殊的 seq-able 对象中返回，以便在需要时进行评估并缓存迄今为止实现的结果。堆栈深度限制为一次调用一次。

没有lazy-seq 的recur 可以用来创建一个急切的版本，但你不希望像在核心版本中那样在不确定长度的序列上使用它。

于 2014-01-11T23:37:30.457 回答
4

以@A.Webb 的回答和@amalloy 的评论为基础：

recur不是调用函数的简写，也不是函数。这是执行尾调用优化的一种特殊形式（在另一种语言中您将称之为语法）。

尾调用优化是一种允许在不破坏堆栈的情况下使用递归的技术（没有它，每个递归调用都会将其调用帧添加到堆栈中）。它还没有在 Java 中本地实现，这就是为什么recur在 Clojure 中用于标记尾调用的原因。

递归使用lazy-seq是不同的，因为它通过将递归调用包装在闭包中来延迟递归调用。这意味着对根据（尤其是此类函数中的每个递归调用）实现的函数的调用lazy-seq（尤其是此类函数中的每个递归调用）会（立即）返回一个LazySeq序列，该序列的计算被延迟，直到它被迭代。

为了说明和限定@amalloy 的评论recur和懒惰是相互排斥的，这里有一个filter使用这两种技术的实现：

(defn filter [pred coll]
  (letfn [(step [pred coll]
            (when-let [[x & more] (seq coll)]
              (if (pred x)
                (cons x (lazy-seq (step pred more))) ;; lazy recursive call
                (recur pred more))))]                ;; tail call
    (lazy-seq (step pred coll))))

(filter even? (range 10))
;; => (0 2 4 6 8)

两种技术都可以用在同一个函数中，但不能用于同一个递归调用；step如果使用了惰性递归调用，则该函数将无法编译，recur因为在这种情况下recur不会处于尾调用位置（尾调用的结果不会直接返回，而是会传递给lazy-seq）。

于 2014-01-15T10:27:02.763 回答
2

所有惰性函数都是这样编写的。的这种实现将在没有调用足够大的序列partition的情况下破坏堆栈。lazy-seq

如果您对工作原理更感兴趣，请阅读有关 TCO（尾调用优化）的信息recur。当您使用尾递归时，这意味着您可以跳出当前的函数调用而不会丢失任何内容。在这种实现的情况下，您将无法做到这一点，因为您cons在下p一次调用partition. 处于尾部位置意味着你是最后一个被叫到的东西。在执行cons中处于尾部位置。recur仅适用于尾部位置以保证 TCO。

于 2014-01-15T09:01:03.743 回答