Создать lazy seq с рекурсией в Clojure?

Question

Я новичок в clojure и в настоящее время борется с loop/recur. Вопрос в основном заключается в том, почему мой «пользовательский» range func. не возвращает ленивую последовательность. Что-то не так с моей реализацией, или вы не должны использовать рекурсию в этом случае?

(defn my-range 
    [nr] 
    (loop [l nr acc '()] 
    (if (< l 1) 
     acc 
     (recur (dec l) (conj acc l))))) 

Когда я запускаю его:

> (time (take 10 (my-range 100000))) ;; "Elapsed time: 85.443 msecs" 
> (time (take 10 (range 100000))) ;; "Elapsed time: 0.095 msecs" 

Разница очень большое время заставляет меня верить в список сначала построили, а затем 10 приняты.

Answer 1

Вы не используете ленивые конструкции в my-range. Поскольку вы собираете список, начиная с конца и работая по пути к началу, единственный способ доступа к первым десяти элементам - сначала реализовать все остальные элементы.

Ленивые последовательности начинаются с самого начала и работать к концу, как это:

(defn my-range 
    ([end] 
    (my-range 1 end)) 
    ([start end] 
    (when (<= start end) 
    (lazy-seq (cons start (my-range (inc' start) end)))))) 

Хитрость здесь в том, что вы не вернете реализованную последовательность. Скорее всего, вы возвращаете объект, который хранит эту функцию:

#(cons start (my-range (inc' start) end)) 

Когда кто-то звонит seq на этом объекте, он будет вызывать функции выше, кэшировать свой результат, и возвращает этот результат. Будущие звонки в seq просто вернут результат кэширования. Обратите внимание, однако, что второй параметр, который вы переходите на cons, равно также ленивая последовательность (потому что звонок my-range возвращает lazy-seq), поэтому он, в свою очередь, будет реализован только при необходимости.

Просто для полноты картины, другой способ, чтобы написать эту функцию следующим образом:

(defn my-range 
    [end] 
    (take end (iterate inc' 1))) 

Это работает, потому что iterate и take возвращают ленивые последовательности.