(sicp15)2章から復習。

一度やったことがあると、すぐに解けるみたい。
1日で今までやっていたところまでいけた。（めんどくさそうな問題は除いて）

• same-parityの解き方は大部変わった。

;;久しぶりなので、もう一度2章の始めの方からやってみる。
;;m2.4
(define (_cons x y)
  (lambda (m) (m x y)))
(define (_car z)
  (z (lambda (p q) p)))
(define (_cdr z)
  (z (lambda (p q) q)))
;	gosh> (define x (_cons 1 2))
;	x
;	gosh> (_car x)
;	1
;	gosh> (_cdr x)
;	2

;;m2.5
;省略

;;m2.6
(define zero (lambda (f) (lambda (x) x)))
(define one (lambda (f) (lambda (x)(f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
(define (add f1 f2)
  (lambda (g) (lambda (x) ((f2 g)((f1 g)x)))))
;	gosh> (((add one two)inc)3)
;	6

;;Alyssaの部分は飛ばす

;;m2.17
(define (last-pair lst)
  (if (null? (cddr lst))
      (cdr lst)
      (last-pair (cdr lst))))
;無駄がある気がするけど、
;	gosh> (last-pair '(1 2 3))
;	(3)

;;m2.18
;再帰と反復両方で
;再帰版
(define (recursive-reverse lst)
  (if (null? (cdr lst))
      (list (car lst))
      (append (recursive-reverse (cdr lst)) (list (car lst)))))
;	gosh> (recursive-reverse '(1 2 3))
;	(3 2 1)

;反復版
(define (iterative-reverse lst)
  (define (iter result lst)
    (if (null? lst)
        result
        (iter (cons (car lst) result) (cdr lst))))
  (iter '() lst))
;	gosh> (iterative-reverse '(1 2 3))
;	(3 2 1)

;;m2.19
;省略

;;m2.20
(define (filter ok? lst)
  (if (null? lst)
      '()
      (if (ok? (car lst))
          (cons (car lst) (filter ok? (cdr lst)))
          (filter ok? (cdr lst)))))
(define (same-parity x . y)
  (append (list x) (filter (if (odd? x) odd? even?) y)))
;	gosh> (same-parity 1 2 3 4 5)
;	(1 3 5)
;	gosh> (same-parity 2 3 4 5 7 9 10)
;	(2 4 10)

;;m2.21
(define (square-list items)
  (if (null? items)
      '()
      (cons ((lambda (x) (* x x)) (car items))
            (square-list (cdr items)))))
;	gosh> (square-list '( 1 2 3))
;	(1 4 9)

(define (square-list-bymap items)
  (map (lambda (x) (* x x)) items))
;	gosh> (square-list-bymap '(1 10 100))
;	(1 100 10000)

;;m2.22
;理由を書くのめんどうなので省略

;;m2.23
(define (for-each func items)
  (cond ((not (null? items))
         (func (car items))
         (for-each func (cdr items)))
        (else
         (newline))))

;;m2.25
(define ax '(1 3 (5 7)))
;	gosh> (cadr (caddr ax))
;      7
(define bx '((7)))
;	gosh> (caar bx)
;	7
(define cx '(1 (2 (3 (4 (5 (6 7)))))))
;	gosh> (cadadr (cadadr (cadadr cx)))
;	7

;;m2.27
(define (deep-reverse tree)
  (if (not (pair? tree))
      tree
      (if (pair? (cdr tree))
          (append (deep-reverse (cdr tree))
                (cons (deep-reverse (car tree)) '()))
          (append (cdr tree) (cons (deep-reverse (car tree)) '())))))
;	gosh> (deep-reverse dx)
;	((4 3) (2 1))

;;m2.28
(define (fringe tree)
  (if (null? tree)
      '()
      (if (pair? tree)
          (append (fringe (car tree)) (fringe (cdr tree)))
          (list tree))))
;	gosh> (fringe dx)
;	(1 2 3 4)

;;m2.30
(define ex '(1(2(3 4) 5)(6 7)))
(define (square-tree tree)
  (if (null? tree)
      '()
      (if (pair? tree)
          (cons (square-tree (car tree)) (square-tree (cdr tree)))
          ((lambda (x) (* x x)) tree))))
;	gosh> (square-tree ex)
;	(1 (4 (9 16) 25) (36 49))

(define (square-tree-bymap tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (square-tree-bymap sub-tree)
             ((lambda (x) (* x x)) sub-tree)))
       tree))
;	gosh> (square-tree-bymap ex)
;	(1 (4 (9 16) 25) (36 49))

;;m2.31
(define (tree-map func tree)
  (map
   (lambda (sub-tree)
     (if (pair? sub-tree)
         (tree-map func sub-tree)
         (func sub-tree)))
   tree))
;	gosh> (tree-map (lambda (x) (* x x)) ex)
;	(1 (4 (9 16) 25) (36 49))

;;m2.32
(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (x) (cons (car s) x)) rest)))))
(define (enumrate-1ton n)
  (if (= n 1)
      (list 1)
      (append (enumrate-1ton (- n 1)) (list n))))
;	gosh> (display (subsets (enumrate-1ton 3)))
;	(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))#<undef>

;;m2.33
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

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

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

(define (ac-length sequence)
  (accumulate (lambda (x y) (+ 1 y)) 0 sequence))
;	gosh> (ac-map (lambda (x) (* x x x)) (enumrate-1ton 4))
;	(1 8 27 64)
;	gosh> (ac-append '(1 2) '(3 4))
;	(1 2 3 4)
;	gosh> (ac-length (enumrate-1ton 10))
;	10

;;m2.34
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coef high-terms) (+ this-coef (* x high-terms)))
              0
              coefficient-sequence))
;	gosh> (horner-eval 2 '( 1 3 0 5 0 1))
;	79

;;m2.35
(define (count-leaves t)
  (accumulate
   +
   0
   (map (lambda (sub-t)
          (if (pair? sub-t)
              (count-leaves sub-t)
              1))
        t)))
;	gosh> ex
;	(1 (2 (3 4) 5) (6 7))
;	gosh> (count-leaves ex)
;	7

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

;((1 2 3) (4 5 6) (7 8 9) (10 11 12))
;これをつくろうとしたら、本体よりも大きくなってしまった。
(define (fx seq)
  (define (use-f-ntimes f n)
    (define (compound f g)
      (lambda (x) (f (g x))))
    (if (= n 1)
        f
        (compound f (use-f-ntimes f (- n 1)))))
  (define u use-f-ntimes)
  (if (null? seq)
      '()
      (cons (list (car seq)
                  (car ((u cdr 1) seq))
                  (car ((u cdr 2) seq)))
            (fx ((u cdr 3) seq)))))
;	gosh> (accumulate-n + 0 (fx (enumrate-1ton 12)))
;	(22 26 30)

;;m2.37
(define (dot-product v w)
  (accumulate + 0 (map * v w)))
(define (matrix-*-vector m v)
  (map (lambda (xs) (dot-product xs v)) m))
(define (transpose mat)
  (accumulate-n (lambda (x y) (cons x y)) '() mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (v) (matrix-*-vector cols v)) m)))

;;m2.38
(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest ))))
  (iter initial sequence))

(define (fold-right op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence) (fold-right op initial (cdr sequence)))))
  
(define (lreverse seq)
  (fold-left (lambda (x y) (cons y x)) '() seq))
(define (rreverse seq)
  (fold-right (lambda (x y) (append y (list x))) '() seq))
;	gosh> (lreverse (enumrate-1ton 4))
;	(4 3 2 1)
;	gosh> (rreverse (enumrate-1ton 5))
;	(5 4 3 2 1)


;;m2.40
(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))
(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))
(define (make-pair-sum pair)
  (list (car pair) (cdr pair) (+ (car pair) (cadr pair))))
(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum?
               (flatmap
                (lambda (i)
                  (map (lambda (j) (list i j))
                       (enumrate-1ton (- i 1))))
                (enumrate-1ton n)))))

(define (permutations s)
  (if (null? s)
      (list '())
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove x s)))))))
(define (remove item sequence)
  (filter (lambda (x) (not (= x items)))
                  sequence))

;;m2.40
;;大変そうなので、ちょっと休憩