7章メモ

ドットリスト

終端がnilでないコンスセルの連なり。終端がnilで終わるのがリストなので真のリストではない。

対

対はコンスセルをそのまま使うことで表現できる。

循環リスト

終端がなく循環した(自己参照をもった)リスト。

REPLが正しく循環リストを表示するために、以下のように設定する必要がある。このように設定する事で、表示する時に循環をチェックして無限ループを回避してくれる。

(setf *print-circle* t)

連想リスト

5章メモ参照。遅い(きっとO(n))。

木構造

Lispコードでいい感じに表現できる。

グラフ

グラフをコード(1次元データ)で上手く表現するのは困難。 Graphvizを使って可視化する。

mapc

リストを返さないmapcar、副作用が主作用()の時に使う。

標準出力を横取りする

*standard-output*を一時的に別のストリームで上書きすることで、標準出力に出力する関数の出力を得ることが出来る。本文中では、ファイルへの書き込みストリームで上書きしている。

また、出力という副作用が意味を持つので、dot->png関数はthunkを引数にとって中で呼んでいる。

~~この辺の出力とかを使った書き方気持ち悪すぎ~~

キーワードシンボル

:で始まるシンボルはそれ自身をさす定数となる。

Source

;ノード(場所)
(defparameter *wizard-nodes* `((living-room (you are in the living-room.))
                        (garden (you are in a beautiful garden.))
                        (attic (you are in the attic.))))

;エッジ(移動手段)
(defparameter *wizard-edges* `((living-room (garden west door)
                                     (attic upstairs ladder))
                        (garden (living-room east door))
                        (attic (living-room downstairs ladder))))

;識別子の変換
(defun dot-name (exp)
  (substitute-if #\_ (complement #'alphanumericp) (prin1-to-string exp)))

(defparameter *max-label-length* 30)

(defun dot-label (exp)
  (if exp
      (let ((s (write-to-string exp :pretty nil)))
        (if (> (length s) *max-label-length*)
            (concatenate 'string (subseq s 0 (- *max-label-length* 3)) "...")
            s))
      ""))

;ノードをDOTフォーマットへ変換
(defun nodes->dot (nodes)
  (mapc (lambda (node)
          (fresh-line)
          (princ (dot-name (car node)))
          (princ "[label=\"")
          (princ (dot-label node))
          (princ "\"];"))
        nodes))

;エッジをDOTフォーマットへ変換
(defun edges->dot (edges)
  (mapc (lambda (node)
          (mapc (lambda (edge)
                  (fresh-line)
                  (princ (dot-name (car node)))
                  (princ "->")
                  (princ (dot-name (car edge)))
                  (princ "[label=\"")
                  (princ (dot-label (cdr edge)))
                  (princ "\"];"))
                (cdr node)))
        edges))

;グラフをDOTフォーマットへ変換
(defun graph->dot (nodes edges)
  (princ "digraph{")
  (nodes->dot nodes)
  (edges->dot edges)
  (princ "}"))

;標準出力に出力される内容をDOTファイルとして書き込みグラフ画像を生成する
(defun dot->png (fname thunk)
  (with-open-file (*standard-output*
                    fname
                    :direction :output
                    :if-exists :supersede)
    (funcall thunk))
  (ext:shell (concatenate 'string "dot -Tpng -O "fname)))

;グラフを画像にする
(defun graph->png (fname nodes edges)
  (dot->png fname
            (lambda ()
              (graph->dot nodes edges))))

;無向グラフを追加
(defun uedges->dot (edges)
  (maplist (lambda (lst)
             (mapc (lambda (edge)
                     (unless (assoc (car edge) (cdr lst)) ;残りのリストに行き先ノードが無いとき
                       (fresh-line)
                       (princ (dot-name (caar lst)))
                       (princ "--")
                       (princ (dot-name (car edge)))
                       (princ "[label=\"")
                       (princ (dot-label (cdr edge)))
                       (princ "\"];")))
                   (cdar lst)))
           edges))

(defun ugraph->dot (nodes edges)
  (princ "graph{")
  (nodes->dot nodes)
  (uedges->dot edges)
  (princ "}"))

(defun ugraph->png (fname nodes edges)
  (dot->png fname
            (lambda ()
              (ugraph->dot nodes edges))))

koropicot's blog

Land of Lisp 7章メモ