ex 2.33, 2.34, 2.35, 2.36, 2.37, 2.38, 2.39, 2.40, 2.41

;; sicp ex 2.33
(define (my-accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (my-accumulate op initial (cdr sequence)))))

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

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

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

;; sicp ex 2.34
(define (horner-eval x coefficient-sequence)
  (my-accumulate (lambda (this-coeff higher-terms)
                   (+ this-coeff (* higher-terms x)))
                 0
                 coefficient-sequence))

;; sicp ex 2.35
;; 2.2.2 count-leaves
(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

;; 参考に
(define (enumerate-tree tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))

(define (count-leaves-accum-sub t)
  (cond ((null? t) 0)
        ((not (pair? t)) 1)
        (else (count-leaves-accum t))))

(define (count-leaves-accum t)
  (my-accumulate +
                 0
                 (map count-leaves-accum-sub t)))

;; sicp ex 2.36
(define (my-accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (my-accumulate op init (map car seqs))
            (my-accumulate-n op init (map cdr seqs)))))
;; '((1 2 3) (4 5 6) (7 8 9))みたいなリストのとき
;; (map car seqs) で先頭の要素を集めたリストが得られるのか。覚えておこう。

;; sicp ex 2.38
(define (my-fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

(define (my-fold-right op initial sequence)
  (my-accumulate op initial sequence))

;; (my-fold-right / 1 '(1 2 3)) -> 3/2
;; (my-fold-left / 1 '(1 2 3)) -> 1/6
;; (my-fold-right list '() '(1 2 3)) -> (1 (2 (3 ())))
;; (my-fold-left list '() '(1 2 3)) -> (((() 1) 2) 3)
;; fold-left, fold-rightどちらをつかっても結果が変わらないためには、
;; opが交換則を満たしている必要がある。

;; sicp ex 2.39
(define (my-reverse-r sequence)
  (my-fold-right (lambda (x y) (append y (cons x '()))) '() sequence))

(define (my-reverse-l sequence)
  (my-fold-left (lambda (x y) (cons y x)) '() sequence))

;; sicp ex 2.40
;; prime?
;; ex 1.21のを再利用
(define (square x)
  (* x x))
(define (smallest-divisor n)
  (find-divisor n 2))
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
  (= (remainder b a) 0))
(define (prime? n)
  (= n (smallest-divisor n)))

;; filter 本文から
(define (filter pred seq)
  (cond ((null? seq) '())
        ((pred (car seq))
         (cons (car seq)
               (filter pred (cdr seq))))
        (else (filter pred (cdr seq)))))

;; 以下問題
;; 実装のために必要な関数。
(define (enumerate-interval low high)
  (if (> low high)
      '()
      (cons low (enumerate-interval (+ low 1) high))))

;; flatmap 本文から
(define (flatmap proc seq)
  (my-accumulate append '() (map proc seq)))

(define (unique-pairs n)
  (flatmap (lambda (x)
                    (map (lambda (y) (list x y))
                         (enumerate-interval 1 (- x 1))))
           (enumerate-interval 1 n)))

(define (make-sum-pairs pair)
  (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))

;; 実装
(define (prime-sum-pairs n)
  (map make-sum-pairs
       (filter prime-sum?
               (unique-pairs n))))

;; sicp ex 2.41
;; i,j,kの組のリストを作る
(define (unique-tris n)
  (flatmap (lambda (x)
             (flatmap (lambda (y)
                        (map (lambda (z) (list x y z))
                             (enumerate-interval 1 (- y 1))))
                      (enumerate-interval 1 (- x 1))))
           (enumerate-interval 1 n)))

(define (search-sum-eq x n)
  (define (search-sum-eq-sub y items)
    (if (null? items)
        '()
        (if (= y (+ (caar items) (cadar items) (caddar items)))
            (cons (car items) (search-sum-eq-sub y (cdr items)))
            (search-sum-eq-sub y (cdr items)))))
  (search-sum-eq-sub x (unique-tris n)))

うむむ。徐々に歯ごたえが出てきました。

こうすればいいと、アイデアは思いつくものの、
それをうまく表現できなかったり、
表現してみたら、結果が全然別のものができていたり。

もっと、分割戦略を意識した方がいいのかな。
小さい問題の組み合わせで解いていく、ということを。

これは、公認インターフェイスにも通ずるし。

と書いていたら、ex 2.41はfilter使えばいいことに気づいた。

;; 書いた後に気づいた。
;; filter使えばいいじゃん！！
(define (search-sum-eq2 x n)
  (filter (lambda (y) (= x (+ (car y) (cadr y) (caddr y))))
          (unique-tris n)))

...。
分割戦略だね！公認インターフェイスだね！