データ構造について

絶賛書き途中

Emacs Lispでは基本的にリストで全てのデータを扱います。リストはconsにより作成し、carやcdrといった関数で参照していきます。

あまり、Cで言う構造体のようにデータを扱いたい場合、連想配列を使うと分かりやすいかもしれません。ここでは2分木を表す連想配列を例に説明します。

2分木なのであるノードは子ノードleftとright、あと各ノードが値を持てるようにvalueを持ちます。Cであれば次のような構造体tokenを使うかもしれません。

struct {
   struct token left;
   struct token right;
   int value;
} token;

Emacs Lispの連想配列を使って同じようなデータ構造を作るとすると次のようになります。

(list
   (cons 'value v)
   (cons 'left nil)
   (cons 'right nil))

使うときはこのようなリストを作成する関数を用意しておくと使いやすいと思います。

(defun binary-tree (l r v)
  (list
   (cons 'left l)
   (cons 'right r)))

こうしておくことで例えば

(binary-tree (binary-tree nil nil "a") nil "b")

このように使うと次のようなリストが得られます

((left . ((left . nil) 
          (right . nil) 
          (value . "a"))) 
 (right . nil) 
 (value . "b"))

この連想配列から値を取り出すときはassoc関数とcdr関数を使います。

(setq bt  (binary-tree (binary-tree nil nil "a") nil "b"))
(cdr (assoc 'value bt))
=> "b"
(cdr (assoc 'left bt))
=> ((left . nil)(right.nil)(value . "a"))
(cdr (assoc 'value (cdr (assoc 'left bt))))
=>"a"

連想配列中の値を書き換えるにはsetcdr関数を使います。少しわかりづらいかもしれません。

 (setq bt  (binary-tree (binary-tree nil nil "a") nil "b"))
 (setcdr (assoc 'value bt) "c")
 (cdr (assoc 'value bt))
 => "c"

次のようなリストがあったとして、

(car . cdr)

このcdrの部分を書き換えるための関数がsetcdrです。全てのリストは上記のような形をしており、例えば次の二つは等価です。

(list a b c d)
'(a . (b . (c . (d . nil))))