通过递归函数检查lisp中的循环性 - 相同的变量

Question

我正在尝试创建一个函数来测试给定列表是否为循环,重新起始点是列表的开头.

预期成绩:

(setq liste '(a b c))
(rplacd (cddr liste) liste)

(circular liste) => t
(circular '(a b c a b c)) => nil  

因为我只是想测试任何后续项目是否为第一个'eq',我不想构建整个乌龟和野兔算法.

这是我的代码:

(defun circular (liste)
    (let (beginningliste (car liste)))
    (labels ( (circ2 (liste)
      (cond
        ((atom liste) nil)
        ((eq (car liste) beginningliste) t)
        (t (circ2 (cdr liste)))
        ) ) ) ) )

1. 它没有给出预期的结果,但我不明白我的错误在哪里
2. 我不确定我是否正确使用'标签'
3. 有没有办法在不使用'标签'的情况下做到这一点？

---

编辑.我想我已经回答了我的第三个问题,因为我觉得我找到了一个更简单的方法.这会有用吗？

(defun circular (liste)
   (cond
      ((atom liste) nil)
      ((eq (car liste) (cadr liste)) t)
      (t  (circular (rplacd liste  (cddr liste))))
      )
   )

Answer 1

首先,当您改变常量数据时,行为是未定义的:当您引用某些内容(此处为列表)时,Lisp环境有权将其视为常量.另见这个问题,为什么defparameter或者defvar更喜欢setq.所以...

(setq list '(a b c))
(rplacd (cddr list) list)

...会写得更好:

(defparameter *list* (copy-list '(a b c)))
(setf (cdr (last *list*)) *list*)

其次,您的代码格式错误,命名约定不正确(请使用破折号分隔单词); 这里是传统的布局,在emacs的帮助下:

(defun circularp (list)
  (let (first (car list)))
  (labels ((circ2 (list)
             (cond
               ((atom list) nil)
               ((eq (car list) first) t)
               (t (circ2 (cdr list))))))))

使用这种格式,应该明白两件事:

• 在let不包含身体形态:您定义局部变量和不使用它们; 你也可以删除该let行.

• 此外,let缺少一对括号:您所写的内容定义了一个变量名称first,另一个定义了一个名称car,绑定到list.我认为你想要定义first为(car list).

• 您定义本地circ2函数但从不使用它.我希望circularp函数(-p用于"谓词",如numberp,stringp)调用(circ2 (cdr list)).我更喜欢重命名circ2为visit(或recurse),因为它意味着什么.

通过上述更正,即:

(defun circularp (list)
  (let ((first (car list)))
    (labels ((visit (list)
               (cond
                 ((atom list) nil)
                 ((eq (car list) first) t)
                 (t (visit (cdr list))))))
      (visit (cdr list)))))

但是,如果您的列表不是循环但是多次包含相同的元素(例如'(a a b)),您将其报告为循环,因为您检查它所拥有的数据而不是结构.请不要查看CAR此处:

(defun circularp (list)
  (let ((first list))
    (labels ((visit (list)
               (cond
                 ((atom list) nil)
                 ((eq list first) t)
                 (t (visit (cdr list))))))
      (visit (cdr list)))))

此外,内部函数是尾递归,但不能保证Common Lisp实现自动消除尾调用(您应该检查您的实现;大多数可以根据请求执行).这意味着你冒险分配与列表中的元素一样多的调用堆栈帧,这很糟糕.更好地直接使用循环:

(defun circularp (list)
  (loop 
    for cursor on (cdr list)
    while (consp cursor)
    thereis (eq cursor list)))

最后,但并非最不重要:您的方法是一个非常常见的方法,但是当列表不是一个大的圆形细胞链时,它会失败,但只是在某个地方包含一个循环.考虑例如:

CL-USER> *list*
#1=(A B C . #1#)
CL-USER> (push 10 *list*)
(10 . #1=(A B C . #1#))
CL-USER> (push 20 *list*)
(20 10 . #1=(A B C . #1#))

(看到答案,我解释了什么#1=和#1#意思)

前面有数字的列表显示圆形,但你不能只使用第一个cons单元格作为标记,因为你将永远循环在圆形的子列表中.这是Tortoise和Hare算法解决的一种或多种问题(可能还有其他技术,最常见的是将访问过的元素存储在哈希表中).

在你最后一次编辑之后,如果我想以递归的方式检查圆度,我会做什么,没有labels:

(defun circularp (list &optional seen)
  (and (consp list)
       (or (if (member list seen) t nil)
           (circularp (cdr list) (cons list seen)))))

我们跟踪所有访问过的cons细胞seen,这是可选的并初始化为NIL(你可以传递另一个值,但这可以看作是一个特征).

然后,我们说一个列表是循环的,如果它是一个cons单元,它是:(i)已经存在于看到的,或者(ii)使得它的CDR相对于圆形(cons list seen).

这里唯一的附加技巧是确保结果是一个布尔值,而不是返回值member(它是被搜索元素是第一个元素的子列表):如果您的环境*PRINT-CIRCLE*设置为NIL并且列表实际上是循环的,你不希望它尝试打印结果.

而不是(if (member list seen) t nil),你也可以使用:

• (when (member list seen))
• (position list seen)
• 而且当然 (not (not (member list seen)))