高階関数、map

情報科学概論IIA

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

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

■先週の課題への応答

先週の課題（教科書84ページ～86ページの「８．３演習問題」）のチェック・ポイント

◆一般的な話

define や if では適当に改行してください。横幅80桁で見やすいように。

(define (f x)
  (if ...
      xxx
      ...))

括弧の対応がとれていない状態で途中でリターンを打っても大丈夫です。

先週の話も参考に

◆再帰

再帰のプログラムでは、自分自身を信じること。自分が完成したと思って、 (f (car x)) とか (f (cdr x)) のように呼び出します。

そして、それができたと思って、１ステップ進める手続きをかきます。後は、再帰が止る所の条件を考えます。

線形再帰と末尾再帰に注意。教科書の例題の多くは、線形再帰だが、末尾再帰にならないもの。

末尾再帰ではない線形再帰
(define (f x y)
 .....
  (cons ..... (f (cdr ... ) ... )))

末尾再帰
(define (f x y)
 .....
  (f ..... (cons (cdr ... ) ... )))



末尾再帰ではない線形再帰の例。
教科書56ページのcopy参照。


(define (copy x)
  (if (null? x)
      '()
      (cons (car x) (copy (cdr x)))))





◆let


先週の話を参考。

◆myappend(破壊的代入を使わない)

myappend の考え方ですが、「x の cdr と y を myappend したものに xの 
car を consする」です。x を car, cdr でばらしていくと、そのうちに x が 
null? になる時がきます。その時の対応は、(myappend '() ' (a b c)) の結
果は、何になるべきか、'() と何かを myappend すると、何になるべきかを考
えます。



myappend の中で 標準の append を使ってはいけません。



myappend では、普通は、revserse は使いません。  



myappend は、線形再帰（教科書56ページ）ですが、末尾再帰（教科書57ペー
ジ）には普通は、なりません。



myappend では、結局、後ろの方の y は、あまりいじらなくてもいいわけです。
逆に y をいじって、x をそのままという考え方もできなくはないですが、こ
れはだめです。リストの性質上、car とcdr が対称形でないので。



(myappend '() '(a b c)) が動かない回答がたくさんありました。
(myappend '() なんとか) は、「なんとか」をそのまま返せばいいです。
car, cdr をとる前に、null? のチェック、または pair? のチェックを
するように。



◆myappend!(破壊的代入を使うmyappend)



考え方としては、最後の cdr が '() であるようなconsセルを探して、その 
cdr 部分を set-cdr! で y にします。最後のconsセルを探す手続きを別に書
くと簡単になります。



リターン・バリューは、別途考えます。
下の begin 参照。



set! は、define や let の変数の束縛を変えるものです。myappend! では、
consセルの内容を書き換える必要があるので、set-cdr! を使います。



myappend! では、cons は使わないはずです。revserse も不可。reverse の中
で cons を使っているので。破壊的代入を使うものは、myappend 以外のもの
でも cons を使いません。



◆begin

set!, set-car!, set-cdr! は、値を返しません。値を返すには、begin を使
うといいでしょう。

(begin
  (set-cdr! ....)
  (set-cdr! ....)
  10
)


こうすると、最後の式(この例では10)が値として返ります。begin は、if の 
then, else 部分を書く時につかいます。define や lambda のトップレベルで
は、begin を省略してもいいようです。

(define (f x)
  (if ...
  )
  (set! .... )
  x)


最後に x の値を返す例。



◆set!とset-cdr!の使い分け

set! は、define や let の変数の「束縛」を変えるものです。
cons セルの内容を変える時には、set-cdr! や set-car! を使います。



リスト操作で、破壊的代入を使うものは、set-car!, set-cdr! を使います。



do ループなどで、let の変数の値を変える時には、set! を使います。define 
で定義された変数（特に大域変数）の値を変えるには、set! を使います。



◆insert

(insert n x y) とは、x の cdr の n-1 番目に y を insert した
ものと x の car を cons したもの。n=1 の時には、y と x cons 。

◆insert(破壊的代入)

たぶん、consセルを一つは増やさないと、挿入はできないでしょう。

◆delete

(delete x y) とは、まず y の cdr から x を delete したもの(これをzと置
く)と、y の car (これを y1とおく)を考え、y1 が x と eq? なら、y1 を z 
とcons したもので、eq? でないなら、単に z である。


(define (delete x y)
   ....
   (let ((y1 (car y))
         (z (delete (cdr y))))
      (if ....
          (cons y1 z)
          z
)))

let に行く前に、(car y) に備えて、null? とか pair? で条件を跳ねること。



◆subst

(subst a b x) とは、まず、x の cdr について a を b で substすることを
してそれと x の car をなんとかする。

◆myreverse

教科書５８ページににもあるように、append を使わなくてもでき
ます。この問題では、append を使うようにというヒントが出ていますが、こ
れは次のように考えてなさいという意味です。



(myreverse x) とは、x の cdr 部分を myreverse したものとx の
car 部分を、なんとかしてリストにしたものを append する。



「なんとかしてリストにする」には、list 手続きか cons を使います。



◆random-number



(random-number) という手続きは、引数はありません。実行するたびに、違う
値を返します。下の (counter) では、呼び出すたびに、結果が１つずつ増え
ていきますが、(random-number)では、呼び出すたびにまったくでたらめに見
える数が返されます。



n番目の乱数を作るのは、直前に作った乱数(n-1番目の乱数)に、教科書にある
ような計算をして、作ります。ですから、一つの前の乱数をどこかに覚えてお
く必要があります。記憶場所としては、しばしば大域変数が使われますが、
がんばれば局所変数でも可能です。
しかも、呼ばれるたびにその内容を更新する必要がありま
す。この更新を、set! などを使ってやります。



乱数を生成する時には、教科書の式で pやaは、慎重に選ぶ必要があります。
そうでないと、よい疑似乱数は得られません。よい乱数とは、髭が長く（繰り
返さない部分が大きい）、周期が長い（繰り返したとしても、周期が長い）も
のです。



コンピュータで作る疑似乱数は、かならず繰り返します。



◆counter

先週示したカウンタの例です。乱数を作る時に参考にしてください。

(define n 0)
(define (counter)
  (set! n (+ n 1))
  n)




最後に n と書いてあるので、n の値が返されます。(上の begin の所で説明
したように、define や lambda のトップレベルでは、begin を省略してもよ
い。)



大域変数を使わない、ちょっとおしゃれなカウンタ。

(define counter
  (let ((n 0))
    (lambda ()
      (set! n (+ n 1))
      n)))


■今日の課題


教科書84ページ～86ページの「８．３演習問題」や、教科書89ページ～91ペー
ジの「９．３演習問題」や、の練習問題のいくつかをやりなさい。

時間内にできたものについて、プログラムと実行結果を次のような電子メール
で送りなさい。

To: yas
Subject: [joka2a] enshuu-8.3 enshuu-9.3




◆sq-list(mapの例)

sq-list は、引数として数のリストを取り、結果としてそれぞれの数を２乗し
たリストを返す手続きである。　普通の定義では、次のようになる。


(define (sq-list l)
  (define (square x) (* x x))
  (if (null? l)
      ()
      (cons (square (car l)) (sq-list (cdr l)))))


末尾再帰ではない線形再帰。(sq-list l) とは、まず (sq-list (cdr l)) を
計算して、(car l) の square を cons する。



map を使うと、次のようになる。

(define (sq-list l)
  (define (square x) (* x x))
  (map square l))




square を define するのがめんどうな時には、map の引数に lambda を直接
書く。

(define (sq-list l)
  (map (lambda (x) (* x x)) l))


◆filter2

実は、4. の filter2 があれば、1.～3. は、簡単。

(define (filter i l)
  (define (is-baisuu-i x)
    (= (modulo x i) 0))
  (filter2 is-baisuu-i l))


このような回答は、レポートでのカウントは、１。



注意：２３日に示した時には、間違いがありました。

誤：
  (define (is-baisuu-i x)
    (modulo x i))


正：
  (define (is-baisuu-i x)
    (= (modulo x i) 0))




◆filter

1. の filter のプログラムは、普通は、map を使わないで、上の最初の 
sq-list のように、（末尾再帰ではない）線形再帰で書きます。map が使えな
い理由は、map では、要素の数が変わらないからです。この場合、filter2 が
map に相当します。




Last updated: 1998/06/30 11:19:49
 

 Yasushi Shinjo / <yas@is.tsukuba.ac.jp>