Proper use of tail recursion while forming a list

Question

As a project to better develop my understanding of functional programming, I am writing a prime number generator in Scheme. I am using a simple brute-force algorithm to detect whether a number is prime and I know there are better algorithms. What I'm interested is whether my attempt at the brute-force algorithm can be better written and whether I am using tail recursion appropriately and forming the list efficiently. The goal is to have a list of numbers at the end I can use for some task or print out. Maybe even write it as a generator where I can continually ask it for the next prime. Here is my current code:

(define is_prime1
 (lambda(num div)
  (if (= num div)
   #t
   (if (= (remainder num div) 0)
    #f
    (is_prime1 num (+ div 1))
   )
  )
 )
)

(define is_prime
 (lambda(num)
  (if (< num 2) #f (is_prime1 num 2))
 )
)

(define list_primes1
 (lambda(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
 (lambda(num)
  (list_primes1 0 num)
 )
)

(define print_primes
 (lambda(primes)
  (if (null? primes)
   '()
   (list
    (display (car primes))
    (newline)
    (print_primes (cdr primes))
   )
  )
 )
)

(print_primes (list_primes 4095))

Answer 1

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:

1. 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.

2. 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.

3. 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.

4. 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 ifs, 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))

Answer 2

First, a few useful notation conventions:

1. In Lisp languages - is commonly used instead of _ to form composite nouns (so is-prime instead of is_prime, etc.).
2. Closed parentheses are not written on a separate line, but at the end of the line they close.
3. Standard indentation is two characters, and the arguments of a function on different lines are aligned at the same distance of the first argument.

Tail recursion

While is-prime1 is tail-recursive, list-primes1 and print-primes are not tail recursive. The reason is that in both cases the recursive call is not the last one: in list-primes1 the result of the recursive call is passed to cons, while in print-primes it is passed to list.

To define list-primes1 as tail recursive, you should use the technique of passing a new parameter to the function, the “accumulator”, which collects the elements while they are found. For instance:

(define list-primes1
  (lambda (idx num acc)
    (if (<= idx num)
        (if (not (is-prime idx))
            (list-primes1 (+ idx 1) num acc)
            (list-primes1 (+ idx 1) num (cons idx acc)))
        (reverse acc))))

(define list-primes
  (lambda (num)
    (list-primes1 0 num '())))

Note that the new parameter is initialized with an empty list inside list-primes, and it is reversed at the end of the recursion in order to produce the resulting list in increasing order.

Here is a possible tail-recursive definition of print-primes:

(define print-primes
  (lambda (primes)
    (if (null? primes)
        '()
        (begin
          (display (car primes))
          (newline)
          (print-primes (cdr primes))))))

Note that the begin is needed since you want to perform side-effects (print values), and since it a special operator for sequencing, the recursive call can be compiled as tail recursion. Note also that, in this way, the ugly list of void values is not printed at the end of of the call of the function, only the primes are printed.

Use of and and or instead of if

When a conditional expression returns a boolean value, in Lisp languages is more idiomatic to use the special operators and and or, since they evaluate their arguments only when needed. For instance:

(define is-prime1
  (lambda (num div)
    (or (= num div)
        (and (not (= (remainder num div) 0))
             (is-prime1 num (+ div 1))))))

(define is-prime
  (lambda (num)
    (and (>= num 2) (is-prime1 num 2))))

and stops the evaluation of its arguments as soon as one of them is #f, returning #f, otherwise returns the value of the last argument; or stops the evaluation of its arguments as soon as one of the is not #f, returning its value, otherwise it returns #f.