Lisp函数计数列表中重复出现的a

Question

我正在尝试编写一个函数，它只接受一个列表作为参数并计算符号 a 的次数出现在列表中，不计算列表中子列表中的任何 a。

我对 Lisp 很陌生，所以请尽可能使用基本代码，这样我就可以理解它在做什么，即使它效率低下。

(defun times (l)
    (setf x 'a)
    (cond
        ((null l) nil)
        ((equal x (car l)) (+ 1 (times x (cdr L))))
        (t (times x(cdr l)))))

所以 (times '(a b (a) c))应该返回 1。但是我得到的错误是，当它应该得到一个时，这个行时间得到了两个参数。

Answer 1

在 Common Lisp 中有多种实现方式。该示例应该足够小以供您遵循(测试它们)。

递归实现

你的方法很好，除了你有小错误(除了评论中报告的其他错误):

不要使用 SETF 对于未声明的变量。

不返回 NIL在基本情况下:您的函数应该返回一个数字。

此外，您的代码可以更好地格式化，并且您应该使用更长的名称(小写 l 尤其难以阅读)

这是修改后的版本:

(defun times (list element)
  (cond
    ((null list) 0)
    ((equal (car list) element) (1+ (times (cdr list) element)))
    (t (times (cdr list) element))))

例子

让我们 TRACE 功能:

CL-USER> (trace times)

这是执行跟踪:

CL-USER> (times '(a b c d a f a) 'a)
0: (TIMES (A B C D A F A) A)
  1: (TIMES (B C D A F A) A)
    2: (TIMES (C D A F A) A)
      3: (TIMES (D A F A) A)
        4: (TIMES (A F A) A)
          5: (TIMES (F A) A)
            6: (TIMES (A) A)
              7: (TIMES NIL A)
              7: TIMES returned 0
            6: TIMES returned 1
          5: TIMES returned 1
        4: TIMES returned 2
      3: TIMES returned 2
    2: TIMES returned 2
  1: TIMES returned 2
0: TIMES returned 3
3

您可以看到列表中访问的每个元素的调用堆栈都在增长。这通常是一种不好的做法，尤其是当递归函数基本上是在实现一个循环时。

循环

使用简单的 LOOP :

(defun times (list element)
  (loop for value in list count (equal value element)))

或者，使用 DOLIST :

(defun times (list element)
  (let ((counter 0))
    (dolist (value list counter)
      (when (equal element value)
        (incf counter)))))

在上面， counter是 LET 引入的局部变量.它以 INCF 递增在循环内，只有 WHEN 比较成立。最后， counter从 dolist 返回(第三个参数指示要评估的表单具有结果值)。 dolist的返回值也是 let 的返回值和整个功能。

这也可以用 DO 重写。 :

(defun times (list element)
  (do ((counter 0)) ((null list) counter)
    (when (equal element (pop list)) 
      (incf counter))))

do 中的第一个列表引入绑定(bind)，第二个列表是一个终止测试(这里我们在列表为空时停止)，然后是一个结果表单(这里是计数器)。在循环体内，我们 POP 输入列表中的元素并像以前一样进行比较。

尾递归实现

如果要保留递归实现，请在进入递归评估之前添加一个累加器并计算所有中间结果。如果所有结果都作为函数参数传递，则无需在递归的每一步跟踪中间结果，这甚至消除了分配堆栈帧的需要。语言规范没有明确要求执行尾调用消除的能力，但它通常在大多数实现中都可用。

(defun times (list element)
  (labels ((recurse (list counter)
             (cond
               ((null list) counter)
               ((equal (first list) element)
                (recurse (rest list) (1+ counter)))
               (t (recurse (rest list) counter)))))
    (recurse list 0)))

在上面， recurse是 LABELS 引入的局部递归函数，它接受 counter范围。与原来的递归函数不同的是，当列表为空时，返回 counter的当前值而不是零。这里， recurse 的结果总是与递归调用返回的值相同:编译器只需重新​​绑定(bind)输入并执行跳转，而不是分配中间帧。

高阶函数

这里还有另外两种基于高阶函数的方法。

首先，使用累加器定义函数的常用方法是使用 REDUCE (在其他语言中称为折叠)。没有明确的突变:

(defun times (list element)
  (reduce (lambda (counter value)
            (if (equal value element)
              (1+ counter)
              counter))
           list
           :initial-value 0))

匿名函数接受累加器的当前状态，列表中访问的当前值，并计算累加器的下一个状态(计数器)。

或者，调用 MAP 与 nil第一个参数，因此迭代只针对效果进行。 LAMBDA 建立的匿名函数表格关闭本地 counter变量，并且可以在比较成立时增加它。类似于前面的 dolist例如 w.r.t.通过副作用增加计数器，但迭代是使用 map 隐式完成的。

(defun times (list element)
  (let ((counter 0))
    (map () 
         (lambda (value)
           (when (equal value element)
             (incf counter)))
         list)
    counter))

内置

供您引用，有一个内置的 COUNT 功能:

(defun times (list element)
  (count element list :test #'equal))