球拍中的引用变量

Question

我正在尝试编写一个简单的程序来查找 n:th 素数，但我不认为我理解如何在 racket 中正确引用变量。

我想要的是内部过程 sieve-iter 将素数添加到列表 primlst 中，该列表位于 sieve 但我得到了一个无限循环。我的猜测是 sieve-iter 中的 primlst 导致了问题。

(define (sieve n) ;; returns the n:th prime (n>0) 
  (let [(primlst '(2))
        (cand 3)]
    (define (sieve-iter i lst)
      (cond ((null? lst) (and (cons i primlst) (sieve-iter (+ i 2) primlst))) ;;prime
            ((= (length primlst) n) (car primlst)) ;;end
            ((= (modulo i (car lst)) 0) (sieve-iter (+ i 2) primlst)) ;;non-prime
            (#t (sieve-iter n (cdr lst))))) ;;unclear if prime
  (sieve-iter cand primlst)))

感谢任何帮助！

Answer 1

首先，您根本不应该在 sieve-iter 函数中引用 primlist。相反，您应该参考 lst。

其次，您似乎误解了这个表达式的效果：

(and (cons i primlst) (sieve-iter (+ i 2) primlst))

您似乎将其解释为 "Add i to the primlist and then start the next iteration."

(cons i primlist) 没有任何改变。相反，它会创建一个由 primlist 和前面的 i 组成的新列表，然后计算该值。原始 primlist（无论如何应该是 lst）保持不变。

此外，and 用于布尔逻辑，而不是用于将命令串在一起。它分别计算它的每个子表达式，直到找到一个计算结果为 #f 的子表达式，然后它停止。

你应该用这个替换整个表达式：

(sieve-iter (+ i 2) (cons i lst))

...将 cons 创建的新列表传递给 sieve-iter 的下一个运行。

Answer 2

你试图在一个函数中做太多事情，让 prime-iter 只需担心构建素数列表的迭代。制作另一个内部函数来递归现有素数以测试新候选者。

(define (sieve n) ;; returns the n:th prime (n>0) 
  (define (sieve-iter i lst remaining)
    (cond ;((null? lst) (and (cons i primlst) (sieve-iter (+ i 2) primlst))) ;;should never be null, we are building the list up
            ((<= remaining 0) (car lst)) ;;checking length every time gets expensive added a variable to the function
            ((sieve-prime? i lst) ;;if prime add to lst and recurse on next i
             (sieve-iter (+ i 2) (cons i lst) (- remaining 1)))
            (else 
             (sieve-iter (+ i 2) lst remaining)))) ; else try next
  (define (sieve-prime? i lst)
    (cond ((null? lst) #t)
          ((= 0 (modulo i (car lst))) #f)
          (else (sieve-prime? i (cdr lst))))) 

    (let ((primlst '(2)) ;;you generally don't modify these, 
          (cand 3)) ;mostly they just bind values to name for convenience or keep from having to re-calculate the same thing more than once      
     (sieve-iter cand primlst (- n 1))))

你本可以用set！在原来的地方修改 primlist，但程序显然不再是纯函数。

调用 sieve-prime 时，这里还有另一个可能的低手优化？过滤第一个参数以删除大于 i 的平方根的值。

球拍中的引用变量

Referencing variables in racket

lisp

scheme

functional-programming

racket