Filter a range without using an intermediate list

Question

I have written a function is-prime that verifies whether a given number is a prime number or not, and returns t or nil accordingly.

(is-prime 2) ; => T
(is-prime 3) ; => T
(is-prime 4) ; => NIL

So far, so good. Now I would like to generate a list of prime numbers between min and max, so I would like to come up with a function that takes those two values as parameters and returns a list of all prime numbers:

(defun get-primes (min max)
  ...)

Now this is where I am currently stuck. What I could do, of course, is create a list with the range of all numbers from min to max and run remove-if-not on it.

Anyway, this means, that I first have to create a potentially huge list with lots of numbers that I throw away anyway. So I would like to do it the other way round, build up a list that contains only the numbers between min and max that actually are prime according to the is-prime predicate.

How can I do this in a functional way, i.e. without using loop? My current approach (with loop) looks like this:

(defun get-primes (min max)
  (loop
    for guess from min to max
    when (is-prime guess)
    collect guess))

Maybe this is a totally dumb question, but I guess I don't see the forest for the trees.

Any hints?

Answer 1

Common Lisp does not favor pure Functional Programming approaches. The language is based on a more pragmatic view of an underlying machine: no TCO, stacks are limited, various resources are limited (the number of arguments which are allowed, etc.), mutation is possible. That does not sound very motivating for any Haskell enthusiast. But Common Lisp was developed to write Lisp applications, not for advancing FP research and development. Evaluation in Common Lisp (as usual in Lisp) is strict and not lazy. The default data structures are also not lazy. Though there are lazy libraries. Common Lisp also does not provide in the standard features like continuations or coroutines - which might be useful in this case.

The default Common Lisp approach is non-functional and uses some kind of iteration construct: DO, LOOP or the ITERATE library. Like in your example. Common Lisp users find it perfectly fine. Some, like me, think that Iterate is the best looping construct ever invented. ;-) The advantage is that it is relatively easy to create efficient code, even though the macros have a large implementation.

There are various ways to do it differently:

• lazy streams. reading SICP helps, see the part on streams. Can be easily done in Common Lisp, too. Note that Common Lisp uses the word stream for I/O streams - which is something different.
• use a generator function next-prime. Generate this function from the initial range and call it until you got all primes you are interested in.

Here is a simple example of a generator function, generating even numbers from some start value:

(defun make-next-even-fn (start)
  (let ((current (- start
                    (if (evenp start) 2 1))))
    (lambda ()
      (incf current 2))))


CL-USER 14 > (let ((next-even-fn (make-next-even-fn 13))) 
               (flet ((get-next-even ()
                        (funcall next-even-fn)))
                 (print (get-next-even))
                 (print (get-next-even))
                 (print (get-next-even))
                 (print (get-next-even))
                 (list (get-next-even)
                       (get-next-even)
                       (get-next-even))))

14 
16 
18 
20 
(22 24 26)

Defining the next-prime generator is left as an exercise. ;-)

• use some kind of more sophisticated lazy data structure. For Common Lisp there is Series, which was an early iteration proposal - also published in CLtL2: Series. The new book Common Lisp Recipes by Edi Weitz (math prof in Hamburg) has a Series example for computing primes. See chapter 7.15. You can download the source code for the book and find the example there.
• the are simpler variants of Series, for example pipes