構造を持ったデータとは, 要素となるデータを集めてできているデータのこと
である. KL1 で扱える構造を持つデータの代表的なものには, 以下のものが
ある.
('') 最初のもの以外の要素をカンマで区切って並べたもの, そし
て閉括弧 (``)'') という順に記述する. たとえば `` a(b,c)''
は, 名前が a, 引数が b と c というファンクタ構造を表す. 要素はどんな
型でも良く, 入れ子構造をしていても良い. たとえば ``
f(g(a,b),h(c))'' は名前が f, ふたつの引数がまたファンクタ構造であるよ
うなファンクタ構造である.
|'') で区切って書き並べる. たとえば
``[a|b]'' は car がアトム a, cdr がアトム b であるようなコンス
を意味する.
コンスそれ自体はふたつの要素だけを持つ構造データだが, これを組み合わせ
てさまざまなデータ構造を作れる. その代表がリスト構造である. コンスの
car がひとつの要素, cdr がリストの残り, 要素がひとつもないリストはアト
ム ``[]'' 表すものと取り決めれば, ふたつの要素 a, b を持つリス
トは `` [a| [b| []]]'' と, ネストしたふたつのコンス
を用いて表すことができる (図 1.2). このままではリストが長くな
ると多数の括弧が必要になるので, これを `` [a,b]'' のように書き表
す.
