为什么函数应用会抱怨长列表? [英] Why does function apply complain about long lists?

问题描述

作为一些欧拉难题的一部分，我正在尝试编写一个Eratosthenes 的筛选 与分解轮.到目前为止，我的代码是:

As part of some Eulerian travails, I'm trying to code a Sieve of Eratosthenes with a factorization wheel. My code so far is:

(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 个元素的轮子，我得到了以下结果.我真的不明白为什么:

I got the following result for wheels longer than 6 elements. I didn't really understand why:

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 个或更少元素的轮子的素数.

The algorithm seems to be working OK otherwise and churns out primes with wheels having 6 or fewer elements.

显然，apply 或 ring 在向他们传递长列表时会嗤之以鼻.

Apparently apply or ring turn up their noses when long lists are passed to them.

但是列表不应该算作单个参数吗?我承认我彻底糊涂了.任何输入表示赞赏.

But shouldn't the list count as a single argument? I admit I'm thoroughly flummoxed. Any input is appreciated.

推荐答案

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

ANSI Common Lisp allows implementations to constrain the maximum number of arguments which can be passed to a function. This limit is given by call-arguments-limit can be as small as 50.

对于行为类似于代数群运算符的函数，关联属性(+、list等)，我们可以通过使用reduce在处理函数的同时抽取输入列表来绕过限制作为二进制.

For functions which behave like algebraic group operators obeying the associative property (+, list, and others), we can get around the limit by using reduce to decimate the input list while treating the function as binary.

例如添加一个大的数字列表:(reduce #'+ list) 而不是 (apply #'+ list).

For instance to add a large list of numbers: (reduce #'+ list) rather than (apply #'+ list).

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

In Common Lisp, reduce will appear to work even if the list is empty. Few other languages give you this, and it doesn't actually come from reduce: it won't work for all functions. But with + we can write (reduce #'+ nil) and it calculates zero, just like (apply #'+ nil).

这是为什么?因为 + 函数可以用零个参数调用，当用零个参数调用时，它会产生附加组的标识元素:0.这与 reduce 函数相吻合.

Why is that? Because the + function can be called with zero arguments, and when called with zero arguments, it yields the identity element for the additive group: 0. This dovetails with the reduce function.

在其他一些语言中，fold 或 reduce 函数必须被赋予一个初始种子值(如 0)，否则是一个非空列表.如果两者都没有给出，则为错误.

In some other languages the fold or reduce function must be given an initial seed value (like 0), or else a nonempty list. If it is given neither, it is an error.

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

The Common Lisp reduce, if it is given an empty list and no :initial-value, will call the kernel function with no arguments, and use the return value as the initial value. Since that value is then the only value (the list is empty), that value is returned.

注意最左边参数有特殊规则的函数.例如:

Watch out for functions with special rules for the leftmost argument. For instance:

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

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

发生的事情是当 reduce 被赋予一个单元素列表时，它只返回元素而不调用函数.

What's going on is that when reduce is given a one-element list, it just returns the element without calling the function.

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

Basically it is founded on the mathematical assumption mentioned above that if no :initial-value is supplied then f is expected to support (f) -> i, where i is some identity element in relation to f, so that (f i x) -> x. This is used as the initial value when reducing the singleton list, (reduce #'f (list x)) -> (f (f) x) -> (f i x) -> x.

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

The - function doesn't obey these rules. (- a 0) means "subtract zero from a" and so yields a, whereas (- a) is the additive inverse of a, probably for purely pragmatic, notational reasons (namely, not making Lisp programmers write (- 0 a) just to flip a sign, just for the sake of having - behave more consistently under reduce and apply). The - function also may not be called with zero arguments.

如果我们想获取一个数字列表，并从某个值 x 中减去它们，则其模式是:

If we want to take a list of numbers and subtract them all from some value x, the pattern for that is:

(reduce #'- list-of-numbers :initial-value x)

这篇关于为什么函数应用会抱怨长列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！