07/01/06 08:10:01
リスト関数をもう少し単純に定義してみます。
m重リストを表す括弧には_mをつけて表記する。（ただし_1は省略）
また、あるリストの唯一の要素となっている多重リストの括弧は省略する。
（例えば、((a,b))は(a,b)_2、((a),(b))は((a),(b))_2、(((n)))は(n)_3のように表記）
f(a)_m=a
f(a,b)_m=a^b
多重リストの要素に自然数の1または1のみを要素とする多重リストがあるとき、そこから右側の要素をすべて取り去る。
リストの右側のカンマから順番に見ていき、以下の表記に当てはまる最初のカンマに対し変換を適用する。
f(…y,z…)_m=f(… f(…y-1,z…)_m ,z-1…)_m
f(…(y),(z)…)_m=f(…(y,…,y),(z-1)…)_m ただしyはy個
f(…(y)_n,(z)_n…)_m=f(…((y)_(n-1),…,(y)_(n-1))_n,(z-1)_n…)_m ただし(y)_(n-1)はy個
f_n(a)_m=f_(n-1)((a)_(a-1),…,(a)_(a-1))_a ただし(a)_(a-1)はa個
定義は以上です。以前のリスト関数と定義が一部変わっているので
二重リスト以上に対しては異なる値となりますが、
f(a,b,…,y,z)=a→b→…→y→zなことには変わりはありません。
これだと、>>100で述べた（多重リスト）重リストにも拡張しやすいと思います。