While answering a recent question I came up with the following code, implementing a variant of the sieve of Eratosthenes, repeatedly culling the initial 2...n sequence, stopping as early as possible:
(define (sieve2 n)
(let ((ls (makelist n)))
(let loop ((ls ls)
(next (sievehelper2 ls n)))
(if (null? next)
ls
(cons (car ls)
(loop next (sievehelper2 ls n)))))))
(define (sievehelper2 list n)
(if (> (* (car list) (car list)) n)
'()
(filterfunc (not-divisible-by (car list))
list)))
(define filterfunc filter)
(define (not-divisible-by n)
(let ((m n)) ; the current multiple of n
(lambda (x)
(let ((ret (not (= x m))))
(if (>= x m) (set! m (+ m n)) #f)
ret))))
(define (makelist n)
(range 2 (+ 1 n)))
Running (sieve 50) in Racket results in '(2 3 3 5 5 7 7 11 11 13 17 19 23 29 31 37 41 43 47) though.
It has some error in it, as is obvious in the results, and I don't immediately see where it is. It can either be some stupid mistake that I made or an expression of some fundamental misalignment of the algorithmic pieces in use, and I can't say which is which.
What is that error and how can it be fixed, please?
To be clear, I'm not asking for algorithmic improvements to the code, I want the computational structure expressed in it preserved. Moreover, the challenge that I saw in the linked question was to devise the missing functions -- and alter the sieve itself -- while keeping the sievehelper function as given, up to some minor alterations as evident in this question's code. This is also a requirement I'd like to make in this question.
I'm also not happy with the two calls to sievehelper2 in sieve2. Perhaps fixing the code structure somehow will also make the error go away?
The problem is here:
(loop next (sievehelper2 ls n))
The list ls is passed for a second time to sievehelper2 in this call; but sievehelper2 needs to process next:
(define (sieve2 n)
(let ((ls (makelist n)))
(let loop ((ls ls)
(next (sievehelper2 ls n)))
(if (null? next)
ls
(cons (car ls)
(loop next (sievehelper2 next n)))))))
With this change, the sieve seems to work as expected:
sieve2.rkt> (sieve2 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)
It may help code clarity to get rid of the outer let in sieve2, and make only one call to sievehelper2:
(define (sieve3 n)
(let loop ((filtered '())
(candidates (makelist n)))
(if (null? candidates)
filtered
(cons (car candidates)
(loop (cdr candidates) (sievehelper2 candidates n))))))
This also works as expected:
sieve2.rkt> (sieve3 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)
I am not happy with sieve3 above. While I think that showing only one call to sievehelper2 aids clarity, the code could still be made more clear.
Initially sieve3 had a result variable which has since been changed to filtered. result was not descriptive enough to be helpful, and I think that the change is an improvement; after all, filtered does contain the results of filtering the candidates list. Although, the initial value of filtered is meaningless in that sense because candidates has not yet been filtered.
What bothers me more is the construction:
(cons (car candidates)
(loop (cdr candidates) (sievehelper2 candidates n)))
It is not very clear that (car candidates) is a prime that is being collected and that (cdr candidates) is the partially filtered list of candidates, or that the goal is to cons primes which have been found onto a fully filtered list of candidates.
Here is an improved version of sieve that uses an explicit accumulator primes to save prime numbers as they are encountered. When sievehelper2 returns an empty list, we know that the filtered list has been fully filtered of non-prime numbers. Finally, the found primes and the fully filtered list of candidates can be appended together and returned (but not before reversing the list of found primes, since the most recently found primes are consed onto the front of primes). This sieve procedure also has the virtue of being tail-recursive:
(define (sieve n)
(let loop ((primes '())
(filtered (makelist n)))
(let ((next (sievehelper2 filtered n)))
(if (null? next)
(append (reverse primes) filtered)
(loop (cons (car filtered) primes)
next)))))
sieve2.rkt> (sieve 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)