Lazy sequence depending on previous elements

Question

Learning clojure, trying to create a lazy infinite sequence of all primes. I know that there are more efficient algorithms; I do the following more as a POC / lesson than as an ideal solution.

I have a function that, given a sequence of primes, tells me the following:

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

Therefore, my lazy sequence should go to this function, then take the result and add it to myself.

My first attempt:

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

.., which leads to an IllegalArgumentException: I don’t know how to create ISeq from: java.lang.Integer

My second attempt:

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

.. which gives me [2 3 5 7] when asked for 10 items.

Attempt 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) 

They all look as if they should work (or at least they should work, given that the previous ones didn't work). Why do I get fictitious output for each case?

Answer 1

Reasons why your initial attempts do not work:

• (find-next-prime lazy-primes) returns an integer, but lazy-cat needs a sequence
• [(find-next-prime lazy-primes)] creates a vector (and therefore seqable), but it is evaluated only once when it is first available
• conj adds new primes to the beginning of the sequence (since lazy cats and therefore lazy numbers return the sequence) ... which is probably not what you want! It also possibly confuses find-next-prime depending on how it is implemented, and there may be some subtle issues around alternating sequences ...

Instead, you can use something like:

 (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))) 

A bit trickier, but mostly I use a higher order helper function to provide closure over a set of parameters that includes the number of primes created so far, so that it can generate the next simple step at every step.

ps since I'm sure you know that there are fast algorithms for generating prime numbers! I suppose this is intended primarily as an exercise in Clojure and using lazy sequences, in which case all is well and good! But if you really care about creating lots of primes, I would recommend taking a look at Sito Atkin

Answer 2

Alternatively, you can use iteration: a built-in function that lazily takes the output of the function and applies it again to the function

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

to make it work, the next-prime function must concatenate its result with its input and return concatenation.

Then you can just call (take 100 (iterate list-primes [1])) to get a list of the first 100 primes.

Answer 3

Using the next-prime function, you can generate a lazy sequence of all primes with the following code snippet:

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

Answer 4

The combination you are looking for is concat + lazy-seq + local fn.

Take a look at the implementation of the Erathostenes sieve in the Clojure Contrib libraries: https://github.com/richhickey/clojure-contrib/blob/78ee9b3e64c5ac6082fb223fc79292175e8e4f0c/src/main/clojure/clojure/sellqlaz

Another word: this implementation uses a more complex algorithm for a sieve in a functional language .

Another implementation for Clojure can be found in the Rosetta code . However, I do not like this, since it uses atoms that you do not need to solve this algorithm in Clojure.