SICP独習会 並びの演算(問題2.33〜)

SICP

問題2.33

この問題を解くには、定義する手続きを、accumulate(積み上げる)という単語を使って説明できなければ解くことができないと思う。


で、mapは最初このように定義した。

現在の要素と、次の要素を、与えられた手続きを作用させる。作用させた要素をaccumulateとしてlist形式で返す。次の要素がナルの場合、「cons x '()」でlistを閉じる。

この定義にしたがって、最初に書いたコードがこれ。

(define (my-map p sequence)
  (accumulater (lambda (x y)
                 (if (null? y)
                   (cons (p x)'())
                   (cons (p x) (p y))))
               '()
               sequence))

実行をトレース。



gosh> (my-map (lambda (x) (* x x)) (list 1 2 3 4))

CALL my-map #[proc] (1 2 3 4)

 CALL accumulater #[proc] () (1 2 3 4)

  CALL accumulater #[proc] () (2 3 4)

   CALL accumulater #[proc] () (3 4)

    CALL accumulater #[proc] () (4)

     CALL accumulater #[proc] () ()

     RETN accumulater ()

    RETN accumulater (16)




    
ERROR: operation * is not defined between (16) and (16)

ぉぉう。これは初めてのエラーだ。原因を探ってみたが、いまいちわからなかった。「にゅお~！！」と悔やしく叫びながら、解答を参考させてもらうことに。

(define (my-map p sequence)
  (accumulater (lambda (x y)
                (cons (p x) y))
               '()
               sequence))
関数型言語の勉強にSICPを読もう - (13) 2章 - データによる抽象の構築(65-69ページ) - higepon blog


トレースした結果。



gosh> (my-map (lambda (x) (* x x)) (list 1 2 3 4))

CALL my-map #[proc] (1 2 3 4)

 CALL accumulater #[proc] () (1 2 3 4)

  CALL accumulater #[proc] () (2 3 4)

   CALL accumulater #[proc] () (3 4)

    CALL accumulater #[proc] () (4)

     CALL accumulater #[proc] () ()

     RETN accumulater ()

    RETN accumulater (16)

   RETN accumulater (9 16)

  RETN accumulater (4 9 16)

 RETN accumulater (1 4 9 16)

RETN my-map (1 4 9 16)

(1 4 9 16)


あ〜そうか。yはまた再帰的に呼び出されているから、そのままconsしてしまえばよいのか。深く考えすぎたか。

accumulateを使ってのappend手続き

言葉による定義。

第一引数の並びを初期値としての第二引数をconsでaccumulateして返す。

(define (my-append seq1 seq2)
  (accumulater cons
               seq2
               seq1))




CALL my-append (1 2 3) (4 5 6)

 CALL accumulater #[proc] (4 5 6) (1 2 3)

  CALL accumulater #[proc] (4 5 6) (2 3)

   CALL accumulater #[proc] (4 5 6) (3)

    CALL accumulater #[proc] (4 5 6) ()

    RETN accumulater (4 5 6)

   RETN accumulater (3 4 5 6)

  RETN accumulater (2 3 4 5 6)

 RETN accumulater (1 2 3 4 5 6)

RETN my-append (1 2 3 4 5 6)

(1 2 3 4 5 6)

accumulateを使ってのlength手続き

言葉による定義。

与えられた要素の個数分だけ1をaccumulateする。

(define (my-length sequence)
  (accumulater (lambda (x y) (+ 1 y))
               0
               sequence))




CALL accumulater #[proc] 0 (1 2 3 4)

 CALL accumulater #[proc] 0 (2 3 4)

  CALL accumulater #[proc] 0 (3 4)

   CALL accumulater #[proc] 0 (4)

    CALL accumulater #[proc] 0 ()

    RETN accumulater 0

   RETN accumulater 1

  RETN accumulater 2

 RETN accumulater 3

RETN accumulater 4

4

うまく動いてはいるが、使わない引数を取るのはうまく抽象化できていないと思う。と、思ったので解答集を見てみると、私の解答を同じだった。う〜む。

問題2.34

多項式を計算するhornerの方法というのがでてきた。これは多項式を計算するアルゴリズムとして最適な方法らしい。

このhornerの方法は後ろの方(指数部の大きい方)から計算していくから・・・

(define (horner-eval x coefficient-sequence)
  (accumulater (lambda (this-coeff higher-terms)
                 (+ this-coeff (* x higher-terms)))
               0
               coefficient-sequence))




CALL accumulater #[proc] 0 (1 3 0 5 0 1)

 CALL accumulater #[proc] 0 (3 0 5 0 1)

  CALL accumulater #[proc] 0 (0 5 0 1)

   CALL accumulater #[proc] 0 (5 0 1)

    CALL accumulater #[proc] 0 (0 1)

    RETN accumulater 2

   RETN accumulater 9

  RETN accumulater 18

 RETN accumulater 39

RETN accumulater 79

79
ここまでaccumulateを利用して手続きを定義してきたけど、accumulateは反復プロセスとなんだか似ているなあと感じて来た。

問題2.35

またもや、accumulateを使っての問題。

最初に書いたコード。

(define (count-leaves t)
  (accumulate +
              0
              (map
                (lambda (x)
                  (cond ((null? x) 0)
                        ((not (pair? x)) (/ x x))))
                t)))

信号処理的に考えてみたところ

  • mapを使って要素の数を全て1に替る。
  • accumulateする

という構想のもと書いてみたが、あえなくエラーが返って終了。解答集を見ることに。

(define (count-leaves t)
  (accumulater +
               0
               (map
                 (lambda (x)
                   (if (pair? x)
                     (count-leaves x)
                     1))
                 t)))

なんだろう・・・考えかたとしてはなんとなくあってる気がするが、mapの結果をlistで返すことを意識するべきだったのな。どうやったらこのようなコードを思い付けるのだろうか。以下がトレースした結果。

  

CALL count-leaves (1 (2 (3 4) 5))

 CALL map #[proc] (1 (2 (3 4) 5))

  CALL count-leaves (2 (3 4) 5)

   CALL map #[proc] (2 (3 4) 5)

    CALL count-leaves (3 4)

     CALL map #[proc] (3 4)

     RETN map (1 1)

     CALL accumulater #[proc] 0 (1 1)

      CALL accumulater #[proc] 0 (1)

       CALL accumulater #[proc] 0 ()

       RETN accumulater 0  

      RETN accumulater 1   

     RETN accumulater 2

    RETN count-leaves 2

   RETN map (1 2 1)

   CALL accumulater #[proc] 0 (1 2 1)

    CALL accumulater #[proc] 0 (2 1)

     CALL accumulater #[proc] 0 (1)

      CALL accumulater #[proc] 0 ()

      RETN accumulater 0   

     RETN accumulater 1

    RETN accumulater 3

   RETN accumulater 4

  RETN count-leaves 4

 RETN map (1 4)

 CALL accumulater #[proc] 0 (1 4)

  CALL accumulater #[proc] 0 (4)

   CALL accumulater #[proc] 0 ()

   RETN accumulater 0

  RETN accumulater 4

 RETN accumulater 5

RETN count-leaves 5

5