4

作为一些Eulerian travails的一部分，我正在尝试使用分解轮编写Eratosthenes 筛。到目前为止，我的代码是：

(defun ring (&rest content)
"Returns a circular list containing the elements in content.
 The returned list starts with the first element of content."
   (setf (cdr (last content)) content))

(defun factorization-wheel (lst)
"Returns a circular list containing a factorization 
 wheel using the list of prime numbers in lst"
   (let ((circumference (apply #'* lst)))
     (loop for i from 1 to circumference
           unless (some #'(lambda (x) (zerop (mod i x))) lst)
             collect i into wheel
           finally (return (apply #'ring 
                             (maplist 
                                 #'(lambda (x) ; Takes exception to long lists (?!)
                                     (if (cdr x)
                                         (- (cadr x) (car x))
                                         (- circumference (car x) -1)))
                                 wheel))))))

(defun eratosthenes (n &optional (wheel (ring 4 2)))
"Returns primes up to n calculated using
 a Sieve of Eratosthenes and a factorization wheel"
   (let* ((candidates (loop with s = 1
                            for i in wheel
                            collect (setf s (+ i s))
                            until (> s n))))
       (maplist #'(lambda (x) 
                    (if (> (expt (car x) 2) n)     
                        (return-from eratosthenes candidates))
                    (delete-if 
                        #'(lambda (y) (zerop (mod y (car x)))) 
                        (cdr x))) 
                candidates)))

对于超过 6 个元素的车轮，我得到了以下结果。我真的不明白为什么：

21 > (factorization-wheel '(2 3 5 7 11 13))
(16 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 ...)
21 > (factorization-wheel '(2 3 5 7 11 13 17))
> Error: Too many arguments.
> While executing: FACTORIZATION-WHEEL, in process listener(1).

否则，该算法似乎工作正常，并使用具有 6 个或更少元素的轮子生成素数。

显然apply，ring当长长的名单传给他们时，他们会嗤之以鼻。

但是列表不应该算作一个参数吗？我承认我完全糊涂了。任何输入表示赞赏。

4

1 回答 1

8

ANSI Common Lisp 允许实现限制可以传递给函数的参数的最大数量。此限制由call-arguments-limit给出，可以小至 50。

对于行为类似于代数群运算符的函数，遵循关联属性（+、和其他），我们可以通过使用抽取输入列表同时将函数视为二进制来list绕过限制。reduce

例如添加大量数字：(reduce #'+ list)而不是(apply #'+ list).

注意事项reduce

在 Common Lisp 中，reduce即使列表为空，它也似乎可以工作。很少有其他语言可以为您提供此功能，而且它实际上并非来自reduce：它不适用于所有功能。但是+我们可以写(reduce #'+ nil)，它计算为零，就像(apply #'+ nil).

这是为什么？因为该+函数可以用零参数调用，并且当用零参数调用时，它会产生加法组的单位元素：0。这与功能相吻合reduce。

在其他一些语言中，foldorreduce函数必须被赋予一个初始种子值（如0），或者一个非空列表。如果两者都没有给出，则为错误。

Common Lisp reduce，如果给定一个空列表和 no :initial-value，将调用不带参数的内核函数，并使用返回值作为初始值。由于该值是唯一的值（列表为空），因此返回该值。

注意对最左边的参数有特殊规则的函数。例如：

(apply #'- '(1)) -> -1  ;; same as (- 1), unary minus semantics.

(reduce #'- '(1)) -> 1  ;; what?

发生的事情是，当reduce给定一个单元素列表时，它只返回元素而不调用函数。

基本上它是建立在上面提到的数学假设之上的，如果没有:initial-value提供，那么f预计支持(f) -> i，其中i是一些与 相关的恒等元素f，所以(f i x) -> x。这在减少单例列表时用作初始值(reduce #'f (list x)) -> (f (f) x) -> (f i x) -> x。

该-函数不遵守这些规则。(- a 0)表示“从”中减去零a，因此产生a，而(- a)是 的加法倒数a，可能出于纯粹实用的符号原因（即，不让 Lisp 程序员编写(- 0 a)只是为了翻转一个符号，只是为了在and-下表现得更一致） . 该函数也不能用零参数调用。reduceapply-

如果我们想获取一个数字列表并从某个 value 中减去它们x，那么模式是：

(reduce #'- list-of-numbers :initial-value x)
于 2015-12-10T06:06:56.617 回答