プログラミング言語論・第 2 回レポート

問題

  1. （問 5.1.10） プリント p.31の deleteの定義では、 (delete 4 '(1 4 4 7))は (1 4 7)になってしまう。 (delete 4 '(1 4 4 7))が (1 7)になるように、 deleteを定義しなおせ。 4がいくつあろうが、対応できるようにすること。

  2. （問 6.1.2） 任意の述語とリストを受取り、リストの中で述語を満たす最初の要素を返す関数 findを定義せよ。例えば、 (find odd? '(2 4 5 3 0))は 5、 (find even? '(2 4 5 3 0))は 2となる。 （述語を満たす要素が見つからない場合は考慮しなくて良い。）

  3. （問 6.3.1）関数iterateを改造して、第3引数として、 終了条件の述語を与える代わりに、生成されるリストの長さを与える関数 iterate2を定義せよ。例えば (iterate2 0 (lambda (x) (+ x 1)) 6) は (0 1 2 3 4 5)に、(iterate2 1 (lambda (x) (* 2 x)) 5)は、 (1 2 4 8 16)になる。

  4. 例題 5.1.8（p.31）の insertと同等の関数を p.12で定義した構造体および関数を用いて、C言語で定義せよ。（非破壊的バージョン）

    また、新しい要素（insertの第1引数）をcar成分に持つ ひとつのconsセル以外は新しいconsセルを作らず、 既存の consセルを破壊的に書き換えるバージョンも定義せよ。

    破壊的バージョンと非破壊的バージョンの説明
    insert(5, cons(1, cons(4, cons(7, NULL))))という呼出しの場合

    青色部分が入力のリスト、赤色部分が出力のリスト（つまり赤い箱が新しいconsセル）、 黒色は両者に共通の部分。

    プログラム全体はおそらくこんな感じ 

    #include <stdio.h>
#include <stdlib.h>

/* p.12の_list, list, cons, car, cdrの定義をここに挿入 */

/* insertの定義（問の答）をここに挿入 */

int main(int argc, char** argv) {
/* テスト用ルーチン */
  list xs = cons(1, cons(4, cons(7, cons(10, NULL))));
  xs = insert(atoi(argv[1]), xs);

  printf("result: ")
  for(; xs; xs=cdr(xs)) {
   printf("%d ", car(xs));
  }
  putchar('\n');
}

    注:破壊的バージョンの場合、リストの最初に挿入する時（例えばinsert(0, cons(1, cons(4, NULL)))の場合）だけ特別扱いする必要がある。 これが面倒な場合は、リストの先頭のconsセルは常にダミーで、 （あるいは、入っている要素が常にマイナス無限大で、） 先頭の手前に新しい要素を挿入する場合はないと仮定して、 プログラムを作成しても良い。

以上の問題をすべて解いてください。

提出要領

Koji Kagawa (kagawa@eng.?????)