副作用を持つプログラムと高階関数

情報科学概論IIA

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

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

■先週の課題への応答

先週の課題(教科書84ページ〜86ページの「8.3演習問題」、教科書89ペー ジ〜91ページの「9.3演習問題」)のチェック・ポイント

◆一般的な話

先々週の話、 先週の話も参考に

◆破壊的代入

破壊的代入を使うものでは、cons を使ってはいけません。(ただし、insert では、新しい要素を接続するために、1つだけは使ってよい。)

直接 cons を使わなくても、次のような関数は内部で cons を呼び出しているので、同じように使ってはいけません。

◆再帰

先週も説明したように、 普通は、末尾再帰で書けないものを、無理矢理、末尾再帰で書こうとしてプロ グラムを複雑にしている例がかなりありました。 教科書の練習問題の多くは、線形再帰だが、末尾再帰にならないものです。末 尾再帰で書けるものは、do でかけます。逆に、do で書きにくいものは、末尾 再帰でも書けません。

再帰する時には、cdr や (- n 1) で、小さくしていくこと。 そうでないと、無限に再帰を続けて終らなくなります。

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

次のようなステップで考えるとわかりやすい。

  1. 最後の cons セル ( cdr部分が '() ) を探す関数を作る。
  2. 1.で見つけたconsセルを set-cdr! で y をつける。
  3. 関数全体のリターン・バリューとして x を返す。 (このためには、 を使うとよい。 define の特殊性として、begin を省略できる場合もある。)

    set-cdr! は、1回だけやれば十分です。 再帰で何度も呼び出さなくてもできるはずです。

    先週の話も参照

    ◆modulo

    割算のあまりを求めるには、modulo という組み込み手続き を利用するといいでしょう。
    > (modulo 10 3)
    1
    > (modulo 12 3)
    0
    > 
    

    ◆filter2のis-baisuu-i

    先週説明したfilter2のis-baisuu-iに は、間違いがありました。
    誤:
      (define (is-baisuu-i x)
        (modulo x i))
    
    正:
      (define (is-baisuu-i x)
        (= (modulo x i) 0))
    
    それから、#t, #f を返す時には、YHM_Computer_Escape(=) <>のように、 もともと #t, #f を返すものなら、その値をそのまま返すようにしてもよい。 わざわざ次のように明示的に書かなくてもよい(書いてもよい)。
    (if (= .... )
        '#t
        '#f
    )
    

    ◆filter/low-set/high-set

    1.〜3. のプログラムは、普通は、map を使わないで、 先週説明したsq-list 先週説明したsq-listのように (末尾再帰ではない)線形再帰で書きます。map は、この プログラムでは、普通は使いません。 map が有効に使えるのは、要素の数が変わらない時です。

    ■今日の課題

    教科書84ページ〜86ページの「8.3演習問題」や、教科書89ページ〜91ペー ジの「9.3演習問題」や、の練習問題のいくつかをやりなさい。 時間内にできたものについて、プログラムと実行結果を次のような電子メール で送りなさい。
    To: yas
    Subject: [joka2a] enshuu-8.3 enshuu-9.3
    


    Last updated: 1998/06/30 11:58:34
    Yasushi Shinjo / <yas@is.tsukuba.ac.jp>