lazy sequence depending on previous elements

Question

Learning clojure, trying to create a lazy infinite sequence of all prime numbers. I'm aware that there are more efficient algorithms; I'm doing the following more as a POC/lesson than as the ideal solution.

I have a function that, given a sequence of primes, tells me what the next prime is:

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

My lazy sequence must therefore pass itself to this function, then take the result and add that to itself.

My first attempt:

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

..which results in an IllegalArgumentException: 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 elements.

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)

All of these seem like they should work (or at least, should work given that the preceding didn't work). Why am I getting the bogus output for each case?

Answer 1

Reasons why your initial attempts don't work:

1. (find-next-prime lazy-primes) returns an integer but lazy-cat needs a sequence
2. [(find-next-prime lazy-primes)] creates a vector (and is hence seqable) but it only gets evaluated once when it is first accessed
3. conj is adding new primes to the start of the sequence (since lazy-cat and hence lazy-primes returns a sequence)... which is probably not what you want! It's also possibly confusing find-next-prime depending on how that is implemented, and there might be a few subtle issues around chunked sequences as well.....

You might instead want to 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 complicated, but basically what I'm doing is using the higher-order helper function to provide a closure over a set of parameters that includes the number of primes created so far, so that it can generate the next prime incrementally at each step.

p.s. as I'm sure you are aware there are faster algorithms for generating primes! I'm assuming that this is intended primarily as an exercise in Clojure and the use of lazy sequences, in which case all well and good! But if you really care about generating lots of primes I'd recommend taking a look at the Sieve of Atkin

Answer 2

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

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

in order for you to make it work, the next-prime function should concatenate its result to its input, and return the concatenation.

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

Answer 3

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

(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 Erathostenes' Sieve in the Clojure Contrib libraries: https://github.com/richhickey/clojure-contrib/blob/78ee9b3e64c5ac6082fb223fc79292175e8e4f0c/src/main/clojure/clojure/contrib/lazy_seqs.clj#L66

One more word, though: this implementation uses a more sophisticated algorithm for the Sieve in a functional language.

Another implementation for Clojure can be found in Rosetta code. However, I don't like that one as it uses atoms, which you don't need for the solution of this algo in Clojure.