再帰プログラミング(その2)

情報科学概論IIA

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/Joka2a-1998/1998-06-09
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/coins/
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html

■先週の課題への応答

先週の課題(教科書62ページ〜67ページの「6.7演習問題」)のチェック・ ポイント

◆一般的な話

授業時間中に、教官、TA、隣の人などを使って、疑問点を解決するように。

単に結果だけでなく、日本語で説明をいれるように。

Lisp のプログラムを書く時に、tab を使うと自動的にきれいな字下げ(段付 け)をしてくれます。

◆手続き定義の形式

次の形式は、同じです。
(define f (lambda (x) ....))
(define (f x) ....)

◆手続き呼び出しの形式

Lisp の次の書き方に慣れてください。
(f .... )
けっこう、次のように書いて、エラーになっている人がいます。
f( .... )
あと、括弧の一番左側は、手続きの名前だということに注意してください。
(lambda (x) 
...
(x .... )
)
こう書くと、x という変数の値を関数だと思って実行するという意味になりま す。

lambda の本体は、括弧で括る必要はありません。たとえば、次の例は、引数 を1つ取るのですが、どんな引数が与えられても 1 を返す手続きです。

(lambda (x) 1)
これを、次のようにかいてはいけません。
(lambda (x) (1))

◆copynは、数の線形再帰

copyn は、2引数ですが、再帰で回るのは、数の方です。 コピーされるリスト方は、単に引き渡せばいいです。

線形再帰なので、! (56ページ)と同じパタンで作れます。これは、線形再帰な ので、末尾再帰にもできます。(末尾再帰にしようと思ってもできないものも あります。) (do .... ) でループで書いてもかまいません。

◆palindrome?

revserse を使うと、簡単です。x と x の revserse が等しい時に、回文と判 断します。

「等しい」かどうかの判定には、equal? が便利です。 再帰で1つひとつ eq? で調べる方法もあります。 ただし、= では、記号は比較できません。= は、数専用です。

#t や #f を返すには、 #t, '#t, #f, '#f, と書きます。

((lambda () '#t))  

◆letrecのはずしかた

letrec で書くと、グローバルな手続きを define しなくてもいいという利点 があります。同じことが、define の中で define してもできます。
  (define (reverse x)
    (define (rev x acc)
      (if (null? x) acc
          (rev (cdr x) (cons (car x) acc))))
    (rev x '()))

◆atomcount

非線形(樹状)再帰です。木構造にそって再帰します。 基本的には、car部とcdr部のatomcountを足せばできます。 ただし、引数がアトムや()になってしまっている時に car, cdr を取ってはいけません。

次のような述語で、場合わけをします。 (全部使う必要はありません。2つ使えば普通は足ります。)

(null? x)
(pair? x)
(atom? x)

◆depth

考え方としては、car の depth に 1 足したものとcdr の depth のうち、大 きいものを取ったものです。car だけ1を足すというのが、ポイント。つまり、 普通の2進の木構造だと、car も cdr も両方足すのが筋です。しかし、Lisp でよく使うリスト構造だと、cdr の部分は深さにいれずに数えるということを よくやります。(他にもいろいろな考え方があります。これが唯一の考え方で はありません)

あとは、ひたすら場合わけと再帰です。

◆flat

基本的には、car を flat したものと、cdr を flat したものをappend すれ ばできます。ただし、最後にアトムになった段階で困ります。アトムは、 append できないので、append に合うようにリストにしてしまうのが簡単です。 あるいは、アトムの時には、別の

■今日の課題

教科書62ページ〜52ページの「6.7演習問題」のうち、1. 〜 5. と、自分 のレポート課題になっているものをやりなさい。 時間内にできたものについて、プログラムと実行結果を次のような電子メール で送りなさい。
To: yas
Subject: [joka2a] enshuu-6.7

余裕がある人は、「6.7演習問題」や、84ページの 演習問題8.3に進みなさい。


Last updated: 1998/06/09 13:35:49
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>