получение переполнения стека в функции Clojure.

Question

Почему я получаю переполнение стека в следующей функции Clojure:

(defn length
  [xs]
  (if ,(not= xs nil)
    (println (+ 1 (length (rest xs))))
    (println 0)))

Answer 1

Я думаю, что идиоматический способ сделать это - позвонить seq на вашу коллекцию. seq для коллекции возвращает nil, если коллекция пуста.

(defn length [xs]
  (if (seq xs)
      (inc (length (rest xs)))
      0))

Это не хвостовая рекурсия (вы не используете recur и не можете здесь), поэтому это все равно будет переполнять стек в очень больших коллекциях.

user> (println (length (range 1000000)))
;; stack overflow

Одна хвостовая рекурсивная версия будет

(defn length [xs]
  (loop [xs xs
         acc 0]
    (if (seq xs)
        (recur (rest xs) (inc acc))
        acc)))

user> (println (length (range 1000000)))
1000000

Это не переполнит стек даже для огромных коллекций, но все еще медленно. Многие коллекции Clojure реализуют интерфейс Counted, а встроенная функция count возвращает длину этих коллекций в постоянном времени.

Answer 2

После переключения на все lazy seqs rest никогда не вернет nil, только пустой список - попробуйте это:

(defn length 
   [xs]
   (if (not (empty? xs))
      (println (+ 1 (length (rest xs))))
      (println 0)))

ИЛИ это

(defn length
   [xs]
   (if ,(not= xs nil)
      (println (+ 1 (length (next xs))))
      (println 0)))