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

问题描述

作为某些欧拉苦恼的一部分，我正在尝试编写

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允许实现限制可以传递给函数的参数的最大数量.此限制由通话参数限制可以小至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屋！