方案中的埃拉托色尼筛选在其过滤过程中使用局部状态的突变

While 回答最近question我想出了以下代码，实现了埃拉托斯特尼筛的变体，反复剔除初始的2...n顺序，尽早停止：

(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)在 球拍 结果'(2 3 3 5 5 7 7 11 11 13 17 19 23 29 31 37 41 43 47) though.

它有一些错误，正如结果中显而易见的那样，我没有立即看出它在哪里。这可能是我犯的一些愚蠢的错误，也可能是所使用的算法部分存在一些根本性错位的表现，我不能说哪个是哪个。

请问这个错误是什么？如何修复？

需要明确的是，我并不是要求对代码进行算法改进，我想要计算结构表达在其中保留。此外，我在相关问题中看到的挑战是设计缺失的功能 - 并改变sieve本身——同时保持sievehelper功能as given，最多进行一些细微的更改，如该问题的代码所示。这也是我想提出的要求this问题。

我也不满意two打电话给sievehelper2 in sieve2。也许以某种方式修复代码结构也会使错误消失？

问题就在这里：

(loop next (sievehelper2 ls n))

列表ls第二次通过sievehelper2在这次通话中；但sievehelper2需要处理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)))))))

通过此更改，筛子似乎按预期工作：

sieve2.rkt> (sieve2 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

摆脱外部可能有助于代码清晰let in sieve2，并且只拨打一次sievehelper2:

(define (sieve3 n)
  (let loop ((filtered '())
             (candidates (makelist n)))
    (if (null? candidates)
        filtered
        (cons (car candidates) 
              (loop (cdr candidates) (sievehelper2 candidates n))))))

这也按预期工作：

sieve2.rkt> (sieve3 50)
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47)

一些改进

我不满意sieve3多于。虽然我认为只显示一个电话sievehelper2有助于清晰，代码仍然可以变得更清晰。

最初sieve3 had a result变量已更改为filtered. result描述性不够，没有帮助，我认为这种改变是一种进步；毕竟，filtered确实包含过滤的结果candidates列表。虽然，初始值filtered从这个意义上来说是没有意义的，因为candidates尚未被过滤。

更让我困扰的是构造：

(cons (car candidates) 
      (loop (cdr candidates) (sievehelper2 candidates n)))

目前还不是很清楚(car candidates)是一个正在被收集的素数，并且(cdr candidates)是部分过滤的候选列表，或者目标是在完全过滤的候选列表上找到素数。

这是一个改进版本sieve使用显式累加器primes保存遇到的素数。什么时候sievehelper2返回一个空列表，我们知道filtered列表已完全过滤掉非素数。最后，找到的素数和完全过滤的候选列表可以附加在一起并返回（但不是在反转找到的素数列表之前，因为最近找到的素数被放在前面）primes). This sieve过程还具有尾递归的优点：

(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)