1

我写了两个版本的 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. 是否可以避免副作用并保持迭代？
  2. 假设#1 的答案是肯定的，那么最好的方法是什么？
4

4 回答 4

4

为了完整起见，请注意 Common Lisp 有一个内置的COUNT：

(count 'a list)
于 2019-06-22T18:56:11.427 回答
3

在某些方面，副作用或无副作用之间的区别有点模糊。采取以下loop版本（忽略loop也有更好的方法）：

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

是在每一步counter 设置，还是反弹？即，是否修改了现有变量（如 in 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))

计数器甚至没有显式变量。有副作用吗？

在内部，当然有效果：创建环境，建立绑定，特别是如果有尾调用优化，即使在递归版本中，每一步都被销毁/替换。

我只将影响某些定义范围之外的事物的效果视为副作用。当然，如果您还可以在内部定义的级别上避免对事物进行显式设置，而是使用一些更具声明性的表达方式，事情就会显得更加优雅。

于 2019-06-22T09:48:06.643 回答
3

您还可以使用map,mapcar和朋友进行迭代。

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

我还建议看一下remove-if[-not]and other reduceand apply：

(length (remove-if-not (lambda (x) (equal :a x)) '(:a :b :a)))  ;; 2
于 2019-06-22T18:24:26.347 回答
1

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

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

(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)))))
于 2019-06-25T01:02:37.403 回答