不使用中间列表过滤范围

Question

我写了一个函数 is-prime 来验证给定的数字是否是质数，并相应地 returns t 或 nil。

(is-prime 2) ; => T
(is-prime 3) ; => T
(is-prime 4) ; => NIL

到目前为止，还不错。现在我想生成一个介于 min 和 max 之间的素数列表，所以我想想出一个将这两个值作为参数和 returns 列表的函数所有素数：

(defun get-primes (min max)
  ...)

现在这是我目前卡住的地方。当然，我可以做的是创建一个列表，其中包含从 min 到 max 和运行 [=20= 的所有数字范围] 就可以了。

无论如何，这意味着我首先必须创建一个可能 巨大的 列表，其中包含我无论如何都会丢弃的大量数字。所以我想反过来做，建立一个列表，只包含 min 和 max 之间的数字，根据 is-prime 谓词，这些数字实际上是质数。

如何以 功能性 方式执行此操作，即不使用 loop？我当前的方法（使用 loop）如下所示：

(defun get-primes (min max)
  (loop
    for guess from min to max
    when (is-prime guess)
    collect guess))

也许这是一个完全愚蠢的问题，但我想我只见树木不见森林。

有什么提示吗？

Answer 1

Common Lisp 不支持纯 函数式编程 方法。该语言基于对底层机器更务实的看法：没有TCO，stacks是有限的，各种资源是有限的（参数个数这是允许的，等等），突变是可能的。对于任何 Haskell 爱好者来说，这听起来都不是很有动力。但是 Common Lisp 是为了编写 Lisp 应用程序而开发的，而不是为了推进 FP 研发。 Common Lisp 中的求值（和 Lisp 中一样）是 strict 而不是 lazy。默认数据结构也不是 lazy。尽管有 lazy 个库。 Common Lisp 也没有提供标准功能，例如 continuations 或 coroutines - 这在这种情况下可能很有用。

默认的 Common Lisp 方法是 non-functional 并使用某种迭代构造：DO、LOOP 或 ITERATE 图书馆。就像你的例子一样。 Common Lisp 用户发现它非常好。有些人，比如我，认为 Iterate 是有史以来最好的循环结构。 ;-) 优点是创建高效代码相对容易，即使宏的实现量很大。

有多种不同的方法：

惰性流。阅读 SICP 有帮助，请参阅 streams 上的部分。也可以在 Common Lisp 中轻松完成。请注意，Common Lisp 使用单词 stream 表示 I/O 流 - 这是不同的东西。
使用 生成器函数 next-prime。从初始范围生成这个函数并调用它，直到你得到所有你感兴趣的素数。

这里是生成器函数的一个简单示例，从某个起始值生成偶数：

(defun make-next-even-fn (start)
  (let ((current (- start
                    (if (evenp start) 2 1))))
    (lambda ()
      (incf current 2))))


CL-USER 14 > (let ((next-even-fn (make-next-even-fn 13))) 
               (flet ((get-next-even ()
                        (funcall next-even-fn)))
                 (print (get-next-even))
                 (print (get-next-even))
                 (print (get-next-even))
                 (print (get-next-even))
                 (list (get-next-even)
                       (get-next-even)
                       (get-next-even))))

14 
16 
18 
20 
(22 24 26)

定义 next-prime 生成器留作练习。 ;-)

使用某种更复杂的惰性数据结构。对于 Common Lisp，有 Series，这是一个早期的迭代建议 - 也在 CLtL2 中发布：Edi Weitz（汉堡的数学教授）的 Series. The new book Common Lisp Recipes 有一个用于计算素数的系列示例.请参阅第 7.15 章。您可以下载本书的源代码并在那里找到示例。
Series 的更简单变体，例如 pipes

不使用中间列表过滤范围

Filter a range without using an intermediate list

lisp

primes

functional-programming

common-lisp