ленивая последовательность в зависимости от предыдущих элементов

Question

Изучая clojure, пытаясь создать ленивую бесконечную последовательность всех простых чисел. Я знаю, что есть более эффективные алгоритмы; Я делаю следующее больше как POC / урок, чем как идеальное решение.

У меня есть функция, которая, учитывая последовательность простых чисел, сообщает мне, каково следующее простое число:

(next-prime [2 3 5]) ; result: 7

Поэтому моя ленивая последовательность должна передать себя этой функции, затем взять результат и добавить его к себе.

Моя первая попытка:

(def lazy-primes
  (lazy-cat [2 3 5] (find-next-prime lazy-primes)))

.. что приводит к исключению IllegalArgumentException: не знаю, как создать ISeq из: java.lang.Integer

Моя вторая попытка:

(def lazy-primes
  (lazy-cat [2 3 5] [(find-next-prime lazy-primes)]))

.., который дает мне [2 3 5 7], когда меня просят 10 элементов.

Попытка 3:

(def lazy-primes
  (lazy-cat [2 3 5]
    (conj lazy-primes (find-next-prime lazy-primes))))

(take 10 lazy-primes) ; result: (2 3 5 7 2 3 5 7 2 3)

Все они, похоже, должны работать (или, по крайней мере, должны работать, учитывая, что предыдущее не сработало). Почему я получаю фиктивный вывод для каждого случая?

Answer 1

С помощью функции next-prime вы можете создать ленивую последовательность всех простых чисел с помощью следующего фрагмента кода:

(def primes (map peek (iterate #(conj % (next-prime %)) [2])))

Answer 2

Причины, по которым ваши первоначальные попытки не работают:

1. (find-next-prime lazy-primes) возвращает целое число, но ленивому коту нужна последовательность
2. [(find-next-prime lazy-primes)] создает вектор (и, следовательно, является секвенируемым), но он оценивается только один раз при первом обращении
3. con добавляет новые простые числа в начало последовательности (поскольку lazy-cat и, следовательно, lazy-primes возвращает последовательность) ... что, вероятно, не то, что вы хотите! Это также, возможно, сбивает с толку find-next-prime в зависимости от того, как это реализовано, и может быть несколько тонких проблем, связанных с секвенированными последовательностями .....

Вместо этого вы можете использовать что-то вроде:

(defn seq-fn [builder-fn num ss] 
  (cons 
    (builder-fn (take num ss)) 
    (lazy-seq (seq-fn builder-fn (inc num) ss))))

(def lazy-primes 
  (lazy-cat [2 3 5] (seq-fn next-prime 3 lazy-primes)))

Немного сложно, но в основном я использую вспомогательную функцию более высокого порядка, чтобы обеспечить замыкание по набору параметров, который включает число созданных к настоящему времени простых чисел, так что он может генерировать следующее простое число постепенно на каждом шагу.

p.s. как я уверен, вы знаете, что существуют более быстрые алгоритмы для генерации простых чисел! Я предполагаю, что это предназначено прежде всего как упражнение в Clojure и использование ленивых последовательностей, и в этом случае все хорошо! Но если вы действительно хотите создать много простых чисел, я бы рекомендовал взглянуть на Сито Аткина

Answer 3

В качестве альтернативы вы можете использовать итерацию: встроенная функция, которая лениво принимает выходные данные функции и снова применяет ее к функции

clojure.core/iterate                                                                                                                                                         
([f x])                                                                                                                                                                
Returns a lazy sequence of x, (f x), (f (f x)) etc.
f must be free of side-effects

для того, чтобы заставить его работать, функция next-prime должна объединить свой результат со своими входными данными и вернуть конкатенацию.

Тогда вы можете просто позвонить (взять 100 (повторять список простых чисел [1])), чтобы получить список первых 100 простые числа.

Answer 4

Комбинация, которую вы ищете: concat + lazy-seq + местный фн.

Взгляните на реализацию сита Erathostenes в библиотеках Clojure Contrib: https://github.com/richhickey/clojure-contrib/blob/78ee9b3e64c5ac6082fb223fc79292175e8e4f0c/src/main/clojure/clojure/contrib/lazy_seqs.clj#L66

Еще одно слово: эта реализация использует более сложный алгоритм для Sieve на функциональном языке .

Другая реализация для Clojure может быть найдена в Rosetta code . Однако он мне не нравится, поскольку он использует атомы, которые вам не нужны для решения этого алгоритма в Clojure.