pair とリスト構造 (2/5)

pair とリストの関係

実は、リストというのは空リスト () でおわる一連鎖の pair のことです。


> empty          ; DrScheme では、変数 empty の値が空リストに設定されている
()
> (cons 1 (cons 2 (cons 3 empty)))
(1 2 3)

pair を二つの正方形で表すと (1 2 3) は下のような図に対応します。

このため、リストに対してその car をとることで先頭要素が、 cdr をとることで残りのリストが得られた訳です。

> (car (list 1 2 3))
1
> (cdr (list 1 2 3))
(2 3)

リストの要素としてリストが入っている場合は、下のようになります。

> (define x (list (list 1 2) (list 'a 'b) (list 3 'c)))
> x
((1 2) (a b) (3 c))
> (car x)
(1 2)
> (cdr x)
((a b) (3 c))

同様に図で表すと、下の様になります。実は、 (car x), (cdr x) が x と一つのデータ構造を共有していることに注意して下さい。

99.10.6/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp