递归地建立缺点列表

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集合转换为cons列表：

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

这是有效的，但如果xs太大，则会溢出。recur不起作用，因为递归调用不在尾部位置。将loop与累加器一起使用是不可行的，因为cons只将内容放在前面，当每次递归都会给您下一个项时，而我不能使用conj。

我能做什么？

编辑：最后，如果你能做到这一点，Clojure从根本上来说并不是为了支持cons对而设计的（你不能将尾部设置为非seq）。我最终只是创建了一个自定义的数据结构和car/cdr函数。

Answer 1

像往常一样，我会提出最简单的循环/递归：

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

Answer 2

lazy-seq是您的朋友。它获取一个计算结果为ISeq的主体，但在调用lazy-seq的结果之前不会对该主体进行计算。

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