functional-programming - 不使用中间列表过滤范围

Question

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

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

到目前为止，还不错。现在我想生成 min 和 max 之间的质数列表，所以我想想出一个函数，将这两个值作为参数并返回一个所有质数的列表:

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

现在这是我目前卡住的地方。当然，我可以做的是创建一个包含所有数字范围从min 到max 的列表，然后运行remove- if-not 就可以了。

无论如何，这意味着我首先必须创建一个潜在的巨大列表，其中包含我无论如何都会丢弃的大量数字。所以我想反过来做，建立一个列表，只包含 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，堆栈有限，各种资源有限(允许的参数数量等)。 ), 突变 是可能的。对于任何 Haskell 爱好者来说，这听起来都不是很有动力。但是 Common Lisp 是为了编写 Lisp 应用程序而开发的，而不是为了推进 FP 研发。 Common Lisp 中的求值(和 Lisp 中一样)是严格而不是惰性。默认数据结构也不是惰性。虽然有惰性 库。 Common Lisp 也不提供标准功能，例如continuations 或coroutines - 这在这种情况下可能很有用。

默认的 Common Lisp 方法是非功能性的，并使用某种迭代 结构: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 中发布:Series .新书Common Lisp Recipes Edi Weitz(汉堡的数学教授)有一个用于计算素数的系列示例。请参阅第 7.15 章。您可以下载本书的源代码并在那里找到示例。
• Series 是更简单的变体，例如 pipes