common-lisp - 从循环列表中删除自引用

Question

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

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

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

Answer 1

最简单的方法是了解使用哈希表遇到的所有缺点。即使在 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)