リスト

非真正リストを真正リストに変換する

最後の cdr が '() でないリストを普通の（真正）リスト(proper_list)と区別して非真正リスト(improper_list)と呼びます。 循環リスト、点対リストは、非真正リストです。

このコード例だと、(foo . #0=(bar baz . #0#)) のように途中で循環しているリストを与えたら無限ループに入りますので「うさぎと亀」アルゴリズムなどを使った方が良いでしょう。

;; 非真正リストを真正リストに変換
(defun improper-list->proper-list (list)
  (check-type list list)
  (do ((again? nil)
       (x list (cdr x))
       (ans () (cons (car x) ans)))
      (nil)
    (typecase x
      (null (return (nreverse ans)))
      (atom (return (nreconc ans (list x))))
      (T (when (and (eq x list)
                    (prog1 again? (setq again? T)))
           (return (nreverse ans)))))))

;; 試してみる

;; 真正リスト
(improper-list->proper-list '(foo bar baz))
;=> (FOO BAR BAZ)

;; 点対リスト
(improper-list->proper-list '(foo bar . baz))
;=> (FOO BAR BAZ)

;; 循環リスト
(let ((circl (list 'foo 'bar 'baz)))
  (setf (cdr (last circl)) circl)
  (improper-list->proper-list circl))
;=> (FOO BAR BAZ)

議論

• このコードだと、(foo #0=(bar baz . #0#)) のように途中で循環しているリストを与えたら無限ループに入っちゃいます。「うさぎと亀」アルゴリズムなどを使った方が良いでしょう。(直したらこのコメントは消しちゃって構いません)
• (foo #0=(bar baz . #0#)) だと proper list なので (foo . #0=(bar baz . #0#)) ですよね。お手軽にチェックするならlist-lengthを使ってこういうのとかでしょうか。

(defun check-list (list)
  (handler-case 
      (typecase (list-length list)
        (null 'circular-list)
        (number 'proper-list))
    (type-error (c) 'dotted-list)))