lisp - 函数 (OccurencesOfPrimes < list >) 计算(可能嵌套的)列表中素数的数量

Question

我正在解决问题以获得 occurence Lisp 列表中的 Prime。输入:编写一个函数 ( OccurencesOfPrimes < list > ) 来计算(可能嵌套的)列表中素数的数量。

输出:示例:(OccurencesOfPrimes (((1)(2))(5)(3)((8)3)) returns 4 .

我正在使用下面的代码，但出现如下错误:

(

defun OccurencesOfPrimes (list)
        (loop for i from 2 to 100 
            do ( setq isPrime t)
            (loop for j from 2 to i
                never (zerop (mod i j))
                    (setq isPrime f)
                    (break)
            )
        )
        (if (setq isPrime t)
            (append list i)
        )
        )
    )

LOOP: illegal syntax near (SETQ ISPRIME F) in
(LOOP FOR J FROM 2 TO I NEVER (ZEROP (MOD I J)) (SETQ ISPRIME F) (BREAK)

)

任何帮助。

Answer 1

保持格式与预期的语言约定一致很重要。它有助于阅读代码(尤其是与其他程序员一起)，并且可以帮助您发现错误。

此外，您应该使用至少能跟踪括号的编辑器。在 Emacs 中，当您将光标放在第一个左括号中时，匹配的括号会高亮显示。您会发现您还有一个毫无用处的额外括号。

(

defun OccurencesOfPrimes (list)
        (loop for i from 2 to 100 
            do ( setq isPrime t)
            (loop for j from 2 to i
                never (zerop (mod i j))
                    (setq isPrime f)
                    (break)
            )
        )
        (if (setq isPrime t)
            (append list i)
        )
        ) ;; <- end of defun
    ) ;; <- closes nothing

在 Lisp 中，括号用于计算机，而缩进用于人类。工具可以根据结构(括号)自动缩进代码，您期望的缩进与计算出的缩进之间的任何差异都表明您的代码格式不正确。如果您查看表达式的缩进，就可以了解表单的深度，仅此一项就可以帮助您理解代码。

符号名称是破折号分隔，而不是camlCased。

您的代码，带有备注:

(defun occurences-of-primes (list)
  ;; You argument is likely to be a LIST, given its name and the way
  ;; you call APPEND below. But you never iterate over the list. This
  ;; is suspicious.
  (loop
     for i from 2 to 100 
     do
       (setq is-prime t) ;; setting an undeclared variable
       (loop
          for j from 2 to i
          never (zerop (mod i j))

            ;; the following two forms are not expected here according
            ;; to LOOP's grammar; setting IS-PRIME to F, but F is not
            ;; an existing variable. If you want to set to false, use
            ;; NIL instead.
            (setq is-prime f)

            ;; BREAK enters the debugger, maybe you wanted to use
            ;; LOOP-FINISH instead, but the NEVER clause above should
            ;; already be enough to exit the loop as soon as its
            ;; sub-expression evaluates to NIL.
            (break)))

  ;; The return value of (SETQ X V) is V, so here your test would
  ;; always succeed.
  (if (setq is-prime t)
      ;; Append RETURNS a new list, without modifying its
      ;; arguments. In particular, LIST is not modified. Note that "I"
      ;; is unknown at this point, because the bindings effective
      ;; inside the LOOP are not visible in this scope. Besides, "I"
      ;; is a number, not a list.
      (append list i)))

原始问题

Write one function which counts all the occurrences of a prime number in a (possibly nested) list.

尽管作业题上写着“写一个函数”，但并不是说你应该写一个大函数来一次计算所有的东西。你可以写一个这么大的函数，但是如果你把你的问题分解成子问题，你将以不同的辅助函数结束，它们:

1. 更容易理解(他们只做一件事)
2. 可以重复使用来构建其他功能

子问题例如:如何判断一个数是不是素数？如何遍历树(又名可能的嵌套列表)？如何计算事件？

基本思想是编写一个“is-prime”函数，遍历树并在每个元素上调用“is-prime”；如果该元素是质数且以前从未见过，则将 1 加到函数本地的计数器。

您还可以展平输入树，以获得列表，然后对结果进行排序列表;您遍历列表，同时跟踪最后一个看到的值:如果值与前一个相同，则您已经知道这个数是否是素数；如果之前的数字不同，那么你必须首先测试这个数字是否是素数。

您还可以对事物进行更多抽象，并定义一个高阶树遍历器函数，该函数在树的每个叶子上调用一个函数。并编写另一个“内存”调用的高阶函数:它环绕一个 函数 F 这样，如果您使用与之前相同的参数调用 F， 它返回存储的结果而不是重新计算它。

例子

我将结合上述想法，因为如果您将答案交给老师，您可能必须仔细解释每个部分的作用(如果可以的话，这对您来说很好)；这不一定是“最佳”答案，但它涵盖了很多内容。

(defun tree-walk-leaves (tree function)
  (typecase tree
    (null nil)
    (cons
      (tree-walk-leaves (car tree) function)
      (tree-walk-leaves (cdr tree) function))
    (t (funcall function tree))))

(defun flatten (tree &optional keep-order-p)
  (let ((flat nil))
    (tree-walk-leaves tree (lambda (leaf) (push leaf flat)))
    (if keep-order-p
        (nreverse flat)
        flat)))

(defun prime-p (n)
  (or (= n 2)
      (and (> n 2)
           (oddp n)
           (loop
              for d from 3 upto (isqrt n) by 2
              never (zerop (mod n d))))))

(defun count-occurences-of-prime (tree)
  (count-if #'prime-p (remove-duplicates (flatten tree))))

(count-occurences-of-prime '(((1)(2))(5)(3)((8)3)))
=> 4

相反，如果您不想删除重复项，而是想计算质数出现的次数，您可以这样做:

(count-if (memoize #'prime-p) (flatten tree))

... memoize 是:

(defun memoize (function &key (test #'equalp) (key #'identity))
  (let ((hash (make-hash-table :test test)))
    (lambda (&rest args)
      (let ((args (funcall key args)))
        (multiple-value-bind (result exists-p) (gethash args hash)
          (values-list
           (if exists-p
               result
               (setf (gethash args hash)
                     (multiple-value-list (apply function args))))))))))

(如果没有重复，memoize 就没用了)