不使用中间列表过滤范围

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？我当前的方法(with 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也没有提供诸如continuation或coroutines之类的标准功能- 在这种情况下可能很有用.

默认Common Lisp的做法是不起作用的,并使用某种形式的重复结构:DO,LOOP或ITERATE库.就像你的例子.Common Lisp用户发现它非常好.像我一样,有些人认为迭代是有史以来最好的循环结构.;-)优点是创建高效代码相对容易,即使宏具有大量实现.

有多种方法可以区别对待:

• 懒惰的溪流.阅读SICP有帮助,请参阅关于流的部分.也可以在Common Lisp中轻松完成.请注意,Common Lisp使用streamI/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中.Edi Weitz的新书Common Lisp Recipes(汉堡的数学教授)有一个用于计算素数的系列示例.见第7.15章.您可以下载该书的源代码并在那里找到示例.
• 系列的更简单的变体,例如管道