循環リスト
xyzzy lispは広井 誠が詳しいのだけれど、循環リストは少し触れているだけだ。
もっと長い循環リストの作り方や、要素の挿入、削除の方法が書かれていない。
まあ、循環リストは不便なところがあるし、大抵は他の実装方法の方がわかりやすいので、必要ない気がしなくもない。
しかし、場所や長さを気にせずにループを扱いたいときには、お呼びがかかることもある*1。
循環リストの扱い方を説明しているところが見つからないので適当に書いて調べてみた。
まず、長い循環リストの作り方だ。
cdrでconsの最後を取り出して循環リストを作ればいいのだが、cdrはcddddrまでしか用意されていない。
そこで、nthcdrを使おうとしたのだが、これはsetfフォームに展開できないらしい。
少し悩んだが、次のようにすれば上手く行くことが判った。
(setq l '(9 8 7 6 5 4 3 2 1)) >(9 8 7 6 5 4 3 2 1) (setf (cdr (last l)) l) >#1=(9 8 7 6 5 4 3 2 1 . #1#)
最後をlastで取り出し、さらに最後のconsのcdrを取り出せばよい。
この方法だと、一度listを探索してしまうので、空の循環リストを作ってから要素を加えた方がいいかも知れない。
要素を加えるのは、popやappendを使うわけにもいかないので、少し工夫が必要だ。
ポインタに直接触れれば早いのだが、それは出来ない気がするので、こんな感じになる。
(setf (cdr l) (cons 0 (cdr l))) >#1=(0 8 7 6 5 4 3 2 1 9 . #1#) l >#1=(9 0 8 7 6 5 4 3 2 1 . #1#)
要は、リストのcdrはポインタになっているので、そこから切り出して、新しい要素を加えて繋げればよい。
このままだと、1番目を無視してしまって使いづらい。実際に使うときには、面倒でも1番目と2番目の順番を入れ替えた方が良さそうだ。
要素を抜き去る場合も同様で、cdrにcddrを繋げてやればよい。
そんな感じで、マクロを作ってみた。
(defmacro make-circ (register lst) `(setf (cdr (last (setq ,register ,lst))) ,register)) (defmacro circ-push (item place) (let ((sym (gensym))) `(let ((,sym (car ,place))) (setf (cdr ,place) (cons ,sym (cdr ,place))) (setf (car ,place) ,item)))) (defmacro circ-pop (place) (let ((sym1 (gensym)) (sym (gensym))) `(let ((,sym1 (car ,place)) (,sym (cadr ,place))) (setf (cdr ,place) (cddr ,place)) (setf (car ,place) ,sym) ,sym1)))
循環リストを作るのと、pushやpop的に操作するもの。
もうすこしエレガントに書ける気がするが、良く解らないので、一応これで。
最後になるが、循環リストは扱うのに注意が必要だ。last辺りなら循環していることを認識してくれるが、どの関数でも調べているとは限らない。
reverseやappendに循環リストを放り込むと、終端を探してメモリ上に目一杯展開してしまう。C-gも利かない。
