list 処理と再帰呼び出しのパターン

listは、再帰的に定義されたデータである( listの定義を思い出そう.. )したがって、一般にlistを処理する関数は、自然に再帰呼び出しを行う関数になる。

list処理の基本は、次のような事実による。

1. listは、NILでない限り、car部とcdr部の二つに分けられる
2. cdr部は再びlistになる(ので、再帰呼び出しが使える)
3. car部の処理をどうするかで、結果が異なる。

再帰呼び出しのパターンは、それこそ、様々な形式が考えられるが、ここでは基本となるパターンをいくつか紹介する。

走査型

listの中に特定の要素があるかどうかを調べるような関数は、全て、この走査型に含まれる。

この走査型の関数の構造は次のようになっている。

1. もし、引数がNILなら、走査は失敗したのでNILを返す
2. そうでなければ、car部を調べる
   1. car部が求めるものなら、走査終了、結果を返す。
   2. そうでなければ、cdr部を探す(再帰呼び出し)

[演習2.3.1]

次の入力を行い、どのような結果が表示されるかを確認しなさい。inatomは、listの要素にatomがあるかどうかを調べ、atomがあれば、そのatomを、そうでなければ、NILを返す関数である。

1. (defun inatom (L) (if (NULL L) NIL (if (atom (car L)) (car L) (inatom (cdr L)))))
2. (inatom '( (a b) c (d e) ) )
3. (inatom '( (a b) x (d e) y ) )
4. (inatom '( (a b) (d c f) (d e) ) )

[演習2.3.2]

次の入力を行い、どのような結果が表示されるかを確認しなさい。関数memberpは、二つの引数もち、一つ目の引数が、二つ目の引数であるlistに、要素として含まれているかどうかを判定し、含まれていればTそうでなければNILを返す関数である。

1. (defun memberp (X L) (if (NULL L) NIL (if (equal X (car L)) T (memberp X (cdr L)))))
2. (memberp 'c '( (a b) c (d e) ) )
3. (memberp 'c '( (a b) x (d e) ) )
4. (memberp 'c '( (a b) (c) (d e) ) )

[演習2.3.3]

次のような走査型関数を定義しなさい。

1. inlist :一つのlistを引数とし、そのlistの要素にlistが含まれていれば、TそうでなければNILを返す関数
2. inplus :一つのlistを引数とし、そのlistの要素に正の数が含まれていれば、TそうでなければNILを返す関数

3. ingt :二つの引数を持ち、一つ目は、数、二つ目は、数のlistとする。

   この関数は、二つ目の引数のlistの中に、一つ目の引数より大きな数があれば、その値を返す。そうでなければ。一つ目の数を返す。

4. memberpp :二つの引数を持ち、二つ目はlistのlistとする。memberppは、二つ目のlistの要素(これは、listである)の内一つ目の要素を含むlistがあれば、それを返す。そうでなければNILを返す。

   [ヒント:memberpを利用してよい]

累積型

走査型では、途中で求めるものが見つかれば、その後を処理しない。累積型では、原則として、listの要素を全て処理する。

そして、その処理した結果を、まとめたものを結果とする。この走査型の関数の構造は次のようになっている。

1. もし、引数がNILなら、定値を返す
2. そうでなければ、
   1. car部を処理する
   2. cdr部を処理する(再帰呼び出し)
   3. car部の処理結果とcdr部の処理結果を合わせた処理をし、全体の結果とする

[演習2.3.4]

次の入力を行い、どのような結果が表示されるかを確認しなさい。関数alladdは、数のlistを引数とし、その数の値を全て加えた結果を返す。

1. (defun alladd (L) (if (NULL L) 0 (+ (car L) (alladd (cdr L)))))
2. (alladd NIL )
3. (alladd '(1 2 9 10) )
4. (alladd '(9) )

[演習2.3.5(mapcar型)]

次の入力を行い、どのような結果が表示されるかを確認しなさい。関数mapsquareは、数のlistを引数とし、要素をすべて二乗した結果のlist返す。

1. (defun mapsquare (L) (if (NULL L) NIL (cons (* (car L) (car L)) (mapsquare (cdr L)))))
2. (mapsquare '(2 3 5 9) )
3. (mapsquare NIL )

[演習2.3.6]

次のような累積型関数を定義しなさい

1. listlen :一つのlistを引数とし、その要素数を数える
2. maxpnum :正の数からなlistを与え、その中で最大の要素を返す
3. allmul :数のlistを与え、その要素を全て掛けた結果を返す関数

4. allcar : listのlistを与え、その各要素の一つ目要素からなるlistを返す。

   (allcar '( (a b c) (e f g) (x y z))) = (a e x)

5. mulv :二つの引数を持ち、一つ目は、数、二つ目は数のlistとする結果は、二つ目引数の各の要素に、一つ目数をそれぞれ掛けた結果のlistとする。

   (mulv 3 '( 1 2 3 4 ) ) = (3 6 9 12)

   これは、listをベクトルとしてみたときの定数倍に相当する。

6. addv :二つの引数を持ち、ともに同じ数の要素を持つ数listとする。結果は、二つの引数のそれぞれn番目同士の要素の和を結果とするlistになる。

   (addv '(3 4 5) '(10 20 30) ) = (13 24 35)

   これは、listをベクトルとしてみたときのベクトルの和に相当する。

7. prodv : addvと同様で、ベクトルの内積を計算する。

順累積型

順累積型は、累積型の一種である。但し、通常の累積型(逆累積型と..)の場合、listの要素を後ろの方「cdr部」から処理し、その後「car部」を処理するといった形が多い。これは、後から、「car部とcdr部の結果をまとめる」操作が、対称な処理であれば、問題ない(加算とか.. )。しかし、そうでない場合(例えば減算.. )は、「car部を先に処理するする必要がある」場合もある。

特にconsは、引数に対称性がない、典型的な操作なので、このような順累積型が必要になることがある。

この順累積型の関数の構造は次のようになっている。

1. 順累積型は、main関数とsub関数の二つからなる。

2. main関数は、sub関数に、引数がNILのときの値とその他の引数全てをsub関数に与える。

   このmainが渡す値を累積値と呼ぶ

3. sub関数は次のような再帰で定義する
   1. もし、引数がNILなら、累積値を返す
   2. そうでなければ、
      1. car部を処理する
      2. car部の処理結果と累積値の処理結果を求め、新しい累積値とする。
      3. 新しい累積値を利用してcdr部を処理する(再帰呼び出し)

[演習2.3.7]

次の入力を行い、どのような結果が表示されるかを確認しなさい。関数revlistは、listの要素をの順を逆順にした結果を返す。

1. (defun revlist (L) (revlistsub NIL L)
2. (defun revlistsub (V L) (if (NULL L) V (revlistsub (cons (car L) V) (cdr L))))
3. (revlist NIL )
4. (revlist '(a b c))
5. (revlist '((a b)(c d)(e f)))

[演習2.3.8]

maxnum :少なくても一つの要素を含む数のlistを与え、その中で最大の要素を返す関数を定義しなさい。

[演習2.3.9]

行列の計算をする関数群を考え、定義しなさい。