有没有办法在 Common Lisp 中使用迭代并同时避免副作用？

Question

我写了两个版本的 lisp 函数。两者的主要区别在于一个是递归完成的，而另一个是迭代完成的。

这是递归版本（没有副作用！）：

(defun simple-check (counter list)
  "This function takes two arguments: 
  the number 0 and a list of atoms. 
  It returns the number of times the 
  atom 'a' appears in that list."
  (if (null list)
      counter
      (if (equal (car list) 'a)
          (simple-check (+ counter 1) (cdr list))
          (simple-check counter (cdr list)))))

这是迭代版本（有副作用）：

(defun a-check (counter list)
  "This function takes two arguments: 
  the number 0 and a list of atoms. 
  It returns the number of times the 
  atom 'a' appears in that list."
  (dolist (item list)
    (if (equal item 'a)
        (setf counter (+ counter 1))
        (setf counter (+ counter 0))))
  counter)

据我所知，它们都有效。但我真的很想避免迭代版本中的副作用。我想回答两个问题：

是否可以避免副作用并保持迭代？
假设问题 1 的答案是肯定的，最好的方法是什么？

Answer 1

在某些方面，side-effect 和没有 side-effect 之间的区别有点模糊。采取以下loop版本（忽略loop也有更好的方法）：

(loop :for x :in list
      :for counter := (if (eq x 'a) (1+ counter) counter)
      :finally (return counter))

是counter设置每一步，还是反弹？即，是修改了现有变量（如 setf），还是创建了新的变量绑定（如在递归中）？

这个do版本非常像递归版本：

(do ((list args (rest list))
     (counter 0 (+ counter (if (eq (first list) 'a) 1 0))))
    ((endp list) counter))

同上问题

现在是“显而易见的”loop 版本：

(loop :for x :in list
      :count (eq x 'a))

计数器甚至没有显式变量。有 side-effect 吗？

在内部，当然有效果：创建环境，建立绑定，尤其是如果有尾调用优化，即使在递归版本中 destroyed/replaced 每一步。

我认为 副作用 仅影响某些定义范围之外的事物。当然，如果您也可以在内部定义的层面上避免对事物进行显式设置，而是使用一些更具声明性的表达式，那么事情看起来会更优雅。

Answer 2

您还可以与 map、mapcar 和朋友一起迭代。

https://lispcookbook.github.io/cl-cookbook/iteration.html

我还建议查看 remove-if[-not] 和其他 reduce 以及 apply:

(length (remove-if-not (lambda (x) (equal :a x)) '(:a :b :a)))  ;; 2

Answer 3

为了完整性，请注意 Common Lisp 有一个 built-in COUNT:

(count 'a list)

Answer 4

将计数器传递给递归过程是启用尾递归定义的一种方法。这对于迭代定义是不必要的。正如其他人所指出的，有几种语言结构可以优雅地解决上述问题。

我假设您从更一般的意义上对此感兴趣，例如当您找不到直接解决问题的语言功能。通常，可以通过如下所示将突变保密来维护功能接口：

(defun simple-check (list)                                                                    
  "return the number of times the symbol `a` appears in `list`"                                 
  (let ((times 0))                                                                            
    (dolist (elem list times)                                                                 
      (when (equal elem 'a)                                                                   
        (incf times)))))

有没有办法在 Common Lisp 中使用迭代并同时避免副作用？

Is there a way to use iteration in Common Lisp and avoid side-effects at the same time?

common-lisp

ansi-common-lisp