Your algorithm is okay, but the real issue with this code is that your code style is atrocious, bordering on unreadable. Your style exhibits four main problems:
Scheme is not C, and parentheses are not curly braces. Do not put close parens on separate lines. Scheme code is intended to be read primarily by observing indentation, which brings me to the next point.
Your indentation is wrong. Again, Scheme is not C, and expressions should be indented to align subexpressions, not with a consistent 1-, 2- or 4-space indent. For an explanation of why this is so important, see this Stack Overflow answer.
This is a less significant point, but your explicit use of lambda
here is unnecessary. There is a shorthand form with define
that is equivalent to define
paired with lambda
, and it’s more idiomatic and easier to visually parse.
Identifiers in Scheme should be hyphenated (lisp-case
), not separated by underscores (snake_case
).
Just following the above formatting changes, your code becomes much more readable to a Schemer:
(define (is-prime1 num div)
(if (= num div)
#t
(if (= (remainder num div) 0)
#f
(is-prime1 num (+ div 1)))))
(define (is-prime num)
(if (< num 2) #f (is-prime1 num 2)))
(define (list-primes1 idx num)
(if (<= idx num)
(if (not (is-prime idx))
(list-primes1 (+ idx 1) num)
(cons idx
(list-primes1 (+ idx 1) num)))
'()))
(define (list-primes num)
(list-primes1 0 num))
(define (print-primes primes)
(if (null? primes)
'()
(list (display (car primes))
(newline)
(print-primes (cdr primes)))))
(print-primes (list-primes 4095))
Now we can focus on some more substantive code improvements. First of all, print-primes
is an easy candidate for elimination. Not only does it needlessly produce a list, it can be trivially implemented using the for-each
higher-order function. The name is also silly, since it does not print primes, it prints each element of a list. There is no reason to include the word “primes” in the name.
Instead, just replace the whole function with a simple use of for-each
:
(define (displayln x) (display x) (newline))
(for-each displayln (list-primes 4095))
Next, let’s look at the bulk of the code. You have defined list-primes
in terms of a helper functions, list-primes1
. Since all your list-primes
function is doing is calling list-primes1
with some arguments set, you can replace the helper function with a use of “named let
”:
(define (list-primes num)
(let loop ((idx 0)
(num num))
(if (<= idx num)
(if (not (is-prime idx))
(loop (+ idx 1) num)
(cons idx
(loop (+ idx 1) num)))
'())))
You also have a pair of nested if
s, which might be more readably represented with a cond
:
(define (list-primes num)
(let loop ((idx 0)
(num num))
(cond
((> idx num)
'())
((is-prime idx)
(cons idx (loop (+ idx 1) num)))
(else
(loop (+ idx 1) num)))))
Taking a look at is-prime
and is-prime1
, we can once again replace is-prime1
with a use of named let
:
(define (is-prime num)
(if (< num 2)
#f
(let loop ((num num)
(div 2))
(if (= num div)
#t
(if (= (remainder num div) 0)
#f
(loop num (+ div 1)))))))
However, this is still much more complicated than it needs to be. Due to how Scheme’s and
and or
are both short-circuiting and implement “truthiness”, where all non-#f
values are truthy, we can replace most of the uses of if
with and
or or
:
(define (is-prime num)
(and (>= num 2)
(let loop ((num num)
(div 2))
(or (= num div)
(and (not (= (remainder num div) 0))
(loop num (+ div 1)))))))
Also, we can replace (= x 0)
with the zero?
predicate to improve readability:
(define (is-prime num)
(and (>= num 2)
(let loop ((num num)
(div 2))
(or (= num div)
(and (not (zero? (remainder num div)))
(loop num (+ div 1)))))))
Now, it’s worth noting that list-primes
is not tail recursive, since in the second cond
case, a call to cons
is in tail position, not loop
. A way to make this function tail recursive is to build up a list iteratively, then reverse
it at the end:
(define (list-primes num)
(reverse
(let loop ((idx 0)
(num num)
(acc '()))
(cond
((> idx num)
acc)
((is-prime idx)
(loop (+ idx 1) num (cons idx acc)))
(else
(loop (+ idx 1) num acc))))))
This leaves us with the final, completely tail-recursive program:
(define (is-prime num)
(and (>= num 2)
(let loop ((num num)
(div 2))
(or (= num div)
(and (not (zero? (remainder num div)))
(loop num (+ div 1)))))))
(define (list-primes num)
(reverse
(let loop ((idx 0)
(num num)
(acc '()))
(cond
((> idx num)
acc)
((is-prime idx)
(loop (+ idx 1) num (cons idx acc)))
(else
(loop (+ idx 1) num acc))))))
(define (displayln x) (display x) (newline))
(for-each displayln (list-primes 4095))