Scheme事始め１：リストがすべて - ryamadaのコンピュータ・数学メモ

集合からn-タプル、ペアノの自然数
- 集合を要素数の括弧の入れ子とする。その入れ子的構造がn-タプル
- $s^+ :=\{s\} \cup s$ で $s=\phi$ とすると、 $\{\phi\}$ も $s$ の構成要素となってくる。ここで $\phi$ は『空集合』、 $\{\phi\}$ は『空集合を要素とする集合』。この２つは違うもの。違うというのはどれくらい違うかというと、 $\phi$ を0に対応付け、 $\{\phi\}$ を1に対応付けるのが有用なほど違う。ここで $\{k\} = k+1$ という対応を入れると、 $\phi = 0$ を出発点とした無限の自然数が出来上がる
まだなんとなくしっくりこないところがある。リストの要素は２つとして考えてあとは順番に右に向かって剥いていく、というのがLISPの原則のようだが、"( )"を使った表現では第１要素とその他の要素があって、その他の要素は複数だったりするので…。このあたりは、LISP表記の読み取り方、という側面と、構文解析、という側面との見方・解釈の仕方の違い、であって、どちらも正しい、ということのように、少なくとも今は見える
List
- LISPはListですべてを取り扱う
- Listは要素を２個持つことを原則とする。ときに０個の要素、１個の要素のこともある
- Listの要素はListかAtomかのどちらかである
Listの要素の取扱い
- Listは原則２個の要素を持つが、左側を優先して取り扱う(左側をCar(『かー』Contents of the Address part of the Register)、右のその他をCdr(『くだー』Contents of the Decrement part of the Register)と呼ぶ
LISPでのListの取扱い
- "( )"で囲ったものがList、囲まれたものが要素で、要素の区切りは空白文字