Бесконечно рекурсивная ленивая последовательность отображается в Clojure как пустая последовательность - PullRequest
Новая
       2

Бесконечно рекурсивная ленивая последовательность отображается в Clojure как пустая последовательность

3 голосов
/ 25 мая 2020

Предположим, я написал: 

(def stuff
  (lazy-seq stuff))

Когда я запрашиваю значение stuff в REPL, я ожидаю, что оно застрянет в бесконечном l oop, поскольку я определяю stuff сам по себе (что практически ничего не говорит об этой последовательности).

Однако вместо этого я получил пустую последовательность. 

> stuff
()

Почему?

Edit: Под «рекурсивным» я имел в виду рекурсивные данные, а не рекурсивные функции.

Я все еще не понимаю, почему последовательность завершилась. Для сравнения, следующий код - это застрял в бесконечном l oop (и взрывает стек). 

(def stuff
  (lazy-seq (cons (first stuff) [])))

Некоторая предыстория: этот вопрос возникает из-за того, что я пытаюсь реализовать генератор простых чисел, используя решето Эратосфена. Моя первая попытка была: 

(def primes
  (lazy-seq (cons 2
                  (remove (fn [x]
                            (let [ps (take-while #(< % x) primes)]
                              (some #(zero? (mod x %)) ps)))
                          (range 3 inf))))) ;; My customized range function that returns an infinite sequence

Я полагал, что это никогда не сработает, поскольку take-while будет продолжать запрашивать больше простых чисел, даже если их еще нельзя было вычислить. Поэтому меня удивило, когда он сработал довольно хорошо. 

> (take 20 primes)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)

1 Ответ

6 голосов
/ 25 мая 2020

Во-первых, каждую отложенную последовательность можно реализовать только один раз. Во-вторых, ваше определение stuff не использует рекурсию - stuff не является функцией. Если вы посмотрите на определение из lazy-seq, вы увидите, что ваше определение stuff расширяется до 

(def stuff (new clojure.lang.LazySeq (fn* [] stuff)))

Когда fn arg в конструктор clojure.lang.LazySeq вызывается, он возвращает тот же ленивый seq, который уже был реализован. Итак, когда вы пытаетесь напечатать ленивую последовательность в REPL, итерация немедленно завершается и возвращает nil.

Вы можете проверить, что тип stuff равен clojure.lang.LazySeq

user=> (type stuff)
clojure.lang.LazySeq

и что после печати stuff в REPL было реализовано stuff 

user=> (realized? stuff)
false
user=> stuff
()
user=> (realized? stuff)
true

Вы можете использовать рекурсию, чтобы получить ожидаемый эффект 

user=> (defn stuff
         []
         (lazy-seq (stuff)))
#'user/stuff
user=> (stuff) ;; Hangs forever.
...