Рекурсивное построение списков минусов

Question

Я пишу программу, которая использует классические пары минусов а-ля Common Lisp, Scheme и др.

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

Я создаю списки, объединяя в цепочку минусы, например (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 только помещает вещи впереди, когда каждый рекурс дает вам следующий предмет, а я не могу использовать conj,

Что я могу сделать?

Изменить: В конце концов, если вы получите это работает, Clojure принципиально не предназначен для поддержки пар "против" (вы не можете установить хвост на non-seq). В итоге я просто создал собственную структуру данных и функции 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

Как обычно, я бы предложил самый простой цикл /recur:

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