递归地建立缺点列表

Question

我正在编写一个程序，它使用经典的 cons 对，如 Common Lisp、Scheme 等

(deftype Cons [car cdr]
  clojure.lang.ISeq
    (first [c] (.car c))
    (more [c] (.cdr c))

我通过链接 cons 单元格来创建列表，例如(Cons. a (Cons. b nil)) 表示包含 a 和 b 的列表。我编写了一个将 Clojure 集合转换为缺点列表的函数：

(defn conslist [xs]
  (if (empty? xs)
      nil
      (Cons. (first xs) (conslist (rest xs)))))

这有效，但如果 xs 太大就会溢出。 recur 不起作用，因为递归调用不在尾部位置。将 loop 与累加器一起使用是行不通的，因为 cons 只会把东西放在前面，当每个递归给你 next 项目时，我可以'不要使用 conj.

我能做什么？

编辑：最后，事实证明，如果你让这个工作正常，Clojure 从根本上来说并不是为了支持缺点对而设计的（你不能将尾部设置为非序列）。我最终只是创建了一个自定义数据结构和 car/cdr 函数。

Answer 1

lazy-seq 是你的朋友。它需要一个评估为 ISeq 的主体，但在调用 lazy-seq 的结果之前不会评估主体。

(defn conslist [xs]
  (if (empty? xs)
      nil
      (lazy-seq (Cons. (first xs) (conslist (rest xs))))))

Answer 2

像往常一样，我会建议最简单的 loop/recur:

(defn conslist [xs]
  (loop [xs (reverse xs) res nil]
    (if (empty? xs)
      res
      (recur (rest xs) (Cons. (first xs) res)))))

Recursively building up cons lists