从循环列表中删除自引用

Question

我在 Common Lisp 中有一个复杂的循环数据结构：

(defvar xs '#1=(1 #2=(#1# 2 #3=(#2# 3 #4=(#3# 4 #1#)))))

如何将其转换为非循环列表，以便每次出现的自引用都替换为 nil？所以我有 (1 (nil 2 (nil 3 (nil 4 nil))))?

而不是 (1 (#0 2 (#1 3 (#2 4 #0))))

Answer 1

只需递归迭代列表及其子列表，记住您之前遇到过的：

(defun remove-circles (list)
  (let ((seen (make-hash-table :test 'eq)))
    (labels ((rec (datum)
               (cond ((not (listp datum))
                      datum)
                     ((gethash datum seen)
                      nil)
                     (t
                      (setf (gethash datum seen) t)
                      (mapcar #'rec datum)))))
      (rec list))))

* (defvar xs '#1=(1 #2=(#1# 2 #3=(#2# 3 #4=(#3# 4 #1#)))))
XS
* xs
#1=(1 #2=(#1# 2 #3=(#2# 3 (#3# 4 #1#))))
* (remove-circles xs)
(1 (NIL 2 (NIL 3 (NIL 4 NIL))))

这将创建一个新列表 - 原始结构未被修改。

Answer 2

最简单的方法是使用散列 table 了解您遇到的所有 cons。即使循环发生在 cdr:

中，此版本也能正常工作

(defun remove-ref (list &optional (value nil))
  (let ((h (make-hash-table :test #'eq)))
    (labels ((rraux (list)
               (cond ((gethash list h) value)
                     ((not (consp list)) list)
                     (t (setf (gethash list h) t)
                        (cons (rraux (car list)) 
                              (rraux (cdr list)))))))
      (rraux list))))


(remove-ref '#1=(1 2 #2=(3 4 5 . #1#) 6 7 . #1#) 'test) 
; ==> (1 2 (3 4 5 . test) 6 7 . test)
(remove-ref '#1=(1 2 #2=(3 4 5 . #1#) 6 7 . #1#)) 
; ==> (1 2 (3 4 5) 6 7)

从循环列表中删除自引用

Remove self-references from a circular list

common-lisp

circular-reference

circular-list