SICPを読む(55) 問題 2.33 - 2.35 accumulateの問題

accumulateと書くのが面倒なので、互換性のあるsrfi-1のfold-rightを使います。ついでにsrfi-26もお試しで。

問題 2.23

穴埋め問題。

軽い軽い。

(define (map p sequence)
  (fold-right (lambda (a b) (cons (p a) b)) '() sequence))

(map (cut + 10 <>) (iota 10)) ; (10 11 12 13 14 15 16 17 18 19)

(define (append seq1 seq2)
  (fold-right cons seq2 seq1))

(append (list-tabulate 5 values)
        (list-tabulate 5 (cut + 5 <>))) ; (0 1 2 3 4 5 6 7 8 9)

(define (length sequence)
  (fold-right (lambda (a b) (+ 1 b)) 0 sequence)) ; aを捨てる

(length (iota 10)) ; 10

srfi-1のlist-tabulateが便利過ぎる!!

メモ:括弧があるときはcutが使えない

問題 2.34

Hornerの公式の問題。

(define (horner-eval x coefficient-sequence)
  (fold-right (lambda (this-coeff higher-terms)
                (+ (* (if (pair? coefficient-sequence)
                          (horner-eval x (cdr coefficient-sequence))
                          higher-terms)
                      x)
                   this-coeff))
              0
              coefficient-sequence))

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

ちょっと泣きそうだった(笑

問題 2.35

count-leavesをアキュムレーションとして再定義する。

わかりにくかったので2つの関数に分けた。

(define (map-leaves t)
  (map (lambda (l)
         (if (pair? l)
             (count-leaves l)
             1))
       t))

(define (count-leaves t)
  (fold-right + 0 (map-leaves t)))

(count-leaves '(1 (2 3) (4 5 (6 7)))) ; 7

map-leavesで(1 1 1 1)というリストを作って、count-leavesで数え上げる。

作戦を練らずにやると案外ハマる。