recursion - 分区 seq - Clojure 中的递归(或一般的 Lisp)

Question

在我从事的一个项目中，我遇到了一个有趣的问题，我很好奇它的其他解决方案。我正在阅读“The Little Schemer”，所以我正在尝试一些递归技术。我想知道是否有另一种方法可以通过递归来做到这一点，如果有一种不使用递归的方法，我也很感兴趣。

问题是获取一个序列并通过获取每个第 n 个元素将其划分为一个序列的序列。例如这个向量:

[ :a :b :c :d :e :f :g :h :i ]

当用 n=3 分区时会产生 seq

((:a :d :g) (:b :e :h) (:c :f :i))

n=4:

((:a :e :i) (:b :f) (:c :g) (:d :h))

等等。我用两个函数解决了这个问题。第一个创建内部序列，另一个将它们拉到一起。这是我的功能:

(defn subseq-by-nth
  "Creates a subsequence of coll formed by starting with the kth element and selecting every nth element."
  [coll k n]
  (cond (empty? coll) nil
        (< (count coll) n) (seq (list (first coll)))
        :else (cons (nth coll k) (subseq-by-nth (drop (+ n k) coll) 0 n))))

(defn partition-by-nth
  ""
  ([coll n]
     (partition-by-nth coll n n))
  ([coll n i]
      (cond (empty? coll) nil
        (= 0 i) nil
        :else (cons (subseq-by-nth coll 0 n) (partition-by-nth (rest coll) n (dec i))))))

我对仅仅为了递归而具有多个元数的第 n 个分区函数并不完全满意，但看不到其他方式。

这似乎适用于所有测试用例。这是一个体面的方法吗？是不是太复杂了？有没有一种方法可以不用递归或者在单个递归函数中做到这一点？

感谢您的建议。我是 Clojure 和 Lisp 的新手，所以我在学习不同的技术。

Answer 1

我希望有一个更简单的递归定义，它更符合 The Little Schemer 的精神，但以下使用 take-nth 的函数要紧凑得多，因为您说过您对替代方法感兴趣:

(defn chop [coll n]
  (for [i (range n)]
    (take-nth n (drop i coll))))

满足你的例子:

(chop [:a :b :c :d :e :f :g :h :i ] 3)
;= ((:a :d :g) (:b :e :h) (:c :f :i))

(chop [:a :b :c :d :e :f :g :h :i ] 4)
;= ((:a :e :i) (:b :f) (:c :g) (:d :h))

在 Clojure 中，内置的库会让你走得更远；当失败时，使用显式递归解决方案。这个版本也很懒；您可能希望在任何“普通”(显式递归)版本中使用 lazy-seq 或 loop...recur 来处理大型数据集而不会破坏堆栈。