関数型言語の勉強にSICPを読もう - (13) 2章 - データによる抽象の構築(65-69ページ)

2.2.3公認インターフェースとしての並び

「accumulate」の意味が分からないので辞書を引いた。

━━ v. 積む, ためる; 積もる, たまる; 【コンピュータ】累算する.

まずはaccumulateの動作を確認しよう。

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

(accumulate + 0 (list 1 2 3 4 5))

今までまじめに本書を読んでいる人ならば、accumulate関数は薄々パターンがあるなと思っていたものを抽出したものだと気づくと思う。

問題2.33

(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) '() sequence))

(define (double x) (* 2 x))

(map double (list 1 2 3 4))

問題では accumulateの第2引数は nil なんだけど '()じゃないと動かないのは僕が悪いのだろうか。

しかし accumulate 最強だなぁ。

(define (append seq1 seq2)
  (accumulate cons seq2 seq1))

(append (list 1 2 3) (list 4 5 6))

lengthの実装に迷う。直感的には

(define (length sequence)
  (accumulate (lambda (x y) 1) 0 sequence))

なんだけど大はずれ。。

これが正解。

(define (length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))

(length (list 1 2 3 4))

問題2.34

Hornerの方法。
数式が出てくると身構えてしまう癖は良くないですね。
素直に解けました。

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

(horner-eval 2 (list 1 3 0 5 0 1))

問題2.35

急に難易度上がってます･･･。
答えを見てしまいました。

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

全ての枝に対して再帰的にcount-leavesした結果のリストの要素を足し合わせるのか。
たしかにこれで実装できることは分かる。
でも今の自分にはこれは解けなかった。悔しい。

問題2.36

(define (accumulate-n op init seq)
  (if (null? (car seq))
      nil
      (cons (accumulate op init (car seq))
            (accumulate-n op init (cdr seq)))))

(define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9)))

(display s)

(accumulate-n + 0 s)

やっぱり自分の解答に自信がないときは間違っている場合が多い。
正解は

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

らしい。

mapの引数に car って何?って一瞬戸惑った。
よく考えたら car も cdr も手続きだ。
リストの取り出しで (map car seqs)とか(map cdr seqs)ってのが新鮮。
よく考えればそうなんだけれども、まだ頭が高階関数やリストの操作に慣れてないと感じる。

※「SICPを読もう」の目次はこちら