Scheme 中的 Eratosthenes 筛法在其过滤过程中使用局部状态突变
Sieve of Eratosthenes in Scheme using mutation of local state in its filtering procedure
虽然 a recent 我想出了以下代码，实现了 Eratosthenes 筛法的变体，反复剔除初始 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)))
运行 (sieve 50) 在 Racket 中的结果是 '(2 3 3 5 5 7 7 11 11 13 17 19 23 29 31 37 41 43 47)。
它有一些错误，在结果中很明显，我没有立即看到它在哪里。这可能是我犯了一些愚蠢的错误，也可能是使用中的算法部分出现了一些根本性的偏差，我不能说哪个是哪个。
请问这是什么错误，如何解决？
明确地说，我不是要求对代码进行算法改进，我想要 其中表达的计算结构 保留 .此外，我在链接问题中看到的挑战是设计缺失的函数——并改变 sieve 本身——同时保持 sievehelper 函数 给定 ，直到这个问题的代码中明显的一些小改动。这也是我想在这个问题中提出的要求。
我对 sieve2 中对 sievehelper2 的 两次 调用也不满意。也许以某种方式修复代码结构也会使错误消失？
问题在这里：
(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)
去掉 sieve2 中的外部 let 并只调用一次 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 有一个 result 变量，此后已更改为 filtered。 result 描述性不够，无法提供帮助，我认为更改是一种改进；毕竟，filtered 确实包含过滤 candidates 列表的结果。虽然，filtered 的初始值在这个意义上没有意义，因为 candidates 尚未被过滤。
更让我困扰的是结构：
(cons (car candidates)
(loop (cdr candidates) (sievehelper2 candidates n)))
不是很清楚 (car candidates) 是正在收集的素数， (cdr candidates) 是部分过滤的候选列表，或者目标是对已找到的素数进行 cons进入完全过滤的候选人名单。
这是 sieve 的改进版本，它使用显式累加器 primes 来保存遇到的素数。当 sievehelper2 returns 一个空列表时，我们知道 filtered 列表已经完全过滤掉了非素数。最后，可以将找到的素数和完全过滤的候选列表附加在一起并返回（但不是在反转找到的素数列表之前，因为最近找到的素数被放在 primes 的前面）。此 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)
更新： 仔细考虑后，我开始不喜欢新结构并重新欣赏我最初提出的结构。
它来自处理对的角度——当前序列及其下一次迭代（修复了错误，感谢 by ad absurdum）：
(define (sieve2_fixed n)
(let ((start (makelist n)))
(let loop ((this start )
(next (sievehelper2 start n)))
(if (null? next)
this
(cons (car this)
(loop next
(sievehelper2 next n)))))))
原始（已弃用）答案如下，仅供记录。
感谢 from ad-absurdum，错误现已修复。
关于代码错误的问题，我真正应该做的是首先为变量使用专有名称，如下所示：
(define (sieve2a n)
(let ((start (makelist n)))
(let loop ((this start)
(next (sievehelper2 start n)))
(if (null? next)
this
(cons (car this)
(loop next ;____ error: `this`: WRONG
(sievehelper2 this n)))))))
与问题中的 sieve2 相比，这里唯一改变的是名称（和一个换行符）。现在错误很明显了，这些名字很可能让我自己更容易注意到它。
至于代码结构和清晰度问题，我不太喜欢 build-in-reverse 范式用于 sieve 重写那个答案。是的，它是函数式编程的主要内容，但实际上，它不必再这样了——如果我们 运行 我们在 Racket 中的代码，堆用于堆栈，堆栈溢出就不可能发生总内存耗尽，直接 tail-recursive-modulo-cons 代码可能有更好的性能，避免了多余的 reverse.
现在查看固定版本，将 this 和 next 放在一起，因为循环变量被误导了，这样做是为了避免另一个内部 let原因。但是用表示的计算更清楚，如
(define (sieve2b n)
(let loop ((this (makelist n)))
(let ((next (sievehelper2 this n)))
(if (null? next)
this
(cons (car this)
(loop next))))))
;; Start with the range of numbers. On each iteration,
;; try running the helper to get the next version of the list.
;; If the attempt produces '(), stop and use what we've got
;; as the remaining prime numbers, which they all are.
;; Otherwise, keep the first number as the next prime, and go on
;; using that "next" version in the next iteration of the loop.
现在只有一次 helper 调用，代码清晰，原来的错误变得不可能像我希望/怀疑的那样。
简单直接胜过不必要的过度复杂化。哦。
虽然
(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)))
运行 (sieve 50) 在 Racket 中的结果是 '(2 3 3 5 5 7 7 11 11 13 17 19 23 29 31 37 41 43 47)。
它有一些错误，在结果中很明显，我没有立即看到它在哪里。这可能是我犯了一些愚蠢的错误，也可能是使用中的算法部分出现了一些根本性的偏差，我不能说哪个是哪个。
请问这是什么错误，如何解决？
明确地说，我不是要求对代码进行算法改进，我想要 其中表达的计算结构 保留 .此外，我在链接问题中看到的挑战是设计缺失的函数——并改变 sieve 本身——同时保持 sievehelper 函数 给定 ，直到这个问题的代码中明显的一些小改动。这也是我想在这个问题中提出的要求。
我对 sieve2 中对 sievehelper2 的 两次 调用也不满意。也许以某种方式修复代码结构也会使错误消失？
问题在这里：
(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)
去掉 sieve2 中的外部 let 并只调用一次 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 有一个 result 变量，此后已更改为 filtered。 result 描述性不够，无法提供帮助，我认为更改是一种改进；毕竟，filtered 确实包含过滤 candidates 列表的结果。虽然，filtered 的初始值在这个意义上没有意义，因为 candidates 尚未被过滤。
更让我困扰的是结构：
(cons (car candidates)
(loop (cdr candidates) (sievehelper2 candidates n)))
不是很清楚 (car candidates) 是正在收集的素数， (cdr candidates) 是部分过滤的候选列表，或者目标是对已找到的素数进行 cons进入完全过滤的候选人名单。
这是 sieve 的改进版本，它使用显式累加器 primes 来保存遇到的素数。当 sievehelper2 returns 一个空列表时，我们知道 filtered 列表已经完全过滤掉了非素数。最后，可以将找到的素数和完全过滤的候选列表附加在一起并返回（但不是在反转找到的素数列表之前，因为最近找到的素数被放在 primes 的前面）。此 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)
更新： 仔细考虑后，我开始不喜欢新结构并重新欣赏我最初提出的结构。
它来自处理对的角度——当前序列及其下一次迭代（修复了错误，感谢
(define (sieve2_fixed n)
(let ((start (makelist n)))
(let loop ((this start )
(next (sievehelper2 start n)))
(if (null? next)
this
(cons (car this)
(loop next
(sievehelper2 next n)))))))
原始（已弃用）答案如下，仅供记录。
感谢
关于代码错误的问题，我真正应该做的是首先为变量使用专有名称，如下所示：
(define (sieve2a n)
(let ((start (makelist n)))
(let loop ((this start)
(next (sievehelper2 start n)))
(if (null? next)
this
(cons (car this)
(loop next ;____ error: `this`: WRONG
(sievehelper2 this n)))))))
与问题中的 sieve2 相比，这里唯一改变的是名称（和一个换行符）。现在错误很明显了，这些名字很可能让我自己更容易注意到它。
至于代码结构和清晰度问题，我不太喜欢 build-in-reverse 范式用于 sieve 重写那个答案。是的，它是函数式编程的主要内容，但实际上，它不必再这样了——如果我们 运行 我们在 Racket 中的代码，堆用于堆栈，堆栈溢出就不可能发生总内存耗尽，直接 tail-recursive-modulo-cons 代码可能有更好的性能，避免了多余的 reverse.
现在查看固定版本，将 this 和 next 放在一起，因为循环变量被误导了，这样做是为了避免另一个内部 let原因。但是用表示的计算更清楚，如
(define (sieve2b n)
(let loop ((this (makelist n)))
(let ((next (sievehelper2 this n)))
(if (null? next)
this
(cons (car this)
(loop next))))))
;; Start with the range of numbers. On each iteration,
;; try running the helper to get the next version of the list.
;; If the attempt produces '(), stop and use what we've got
;; as the remaining prime numbers, which they all are.
;; Otherwise, keep the first number as the next prime, and go on
;; using that "next" version in the next iteration of the loop.
现在只有一次 helper 调用，代码清晰，原来的错误变得不可能像我希望/怀疑的那样。
简单直接胜过不必要的过度复杂化。哦。