Hatena::Groupcsnagoya-sicp

クラなんとかの日記 このページをアンテナに追加 RSSフィード

 | 

2009-06-11準備会

2.38

| 2.38 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.38 - クラなんとかの日記 2.38 - クラなんとかの日記 のブックマークコメント

accumulate は,先頭の要素に右側の要素を組み合わせるので,fold-right と呼ばれている.

fold-left のことを考えてみようという問題.

fold-right と fold-left の結果が等しくなるのは,op の結果が引数の順序で不変である場合.(+ や * など)

#!/usr/bin/env gosh
;; -*- coding: utf-8; -*-
; 

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

(define fold-right accumulate)

; 問題文より
(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 x (list 1 2 3))

(display x) (newline) ; (1 2 3)
(display (fold-right / 1 x)) (newline) ; 3/2 {= 1 / (2 / (3 / 1))}
(display (fold-left / 1 x)) (newline) ; 1/6 {= (1 / 2) / 3}
(display (fold-right list (list) x)) (newline) ; (1 (2 (3 ())))
(display (fold-left list (list) x)) (newline) ; (((() 1) 2) 3)

2.37

| 2.37 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.37 - クラなんとかの日記 2.37 - クラなんとかの日記 のブックマークコメント

matrix-*-vector, transpose, matrix-*-matrix を定義せよ.

matrix の定義がわかればわかる問題.2.36 も参照のこと.

#!/usr/bin/env gosh
;; -*- coding: utf-8; -*-
; 

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

; 2.36 より
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      (list)
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

; 問題文より
(define (dot-product v w)
  (accumulate + 0 (map * v w)))

;; 答え
(define (matrix-*-vector m v)
  (map (lambda (w)
;         (dot-product w v))
         (list (dot-product w v))) ; 6/18 訂正 list が抜けていた
       m))

(define (transpose mat)
  (accumulate-n cons (list) mat))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (v)
           (matrix-*-vector cols v))
         m)))

;; 確認
(define m (list (list 1 2 3 4) (list 4 5 6 6) (list 6 7 8 9)))
(define n (list (list 2 4) (list 6 8) (list 9 7) (list 1 3)))
(define v (list 1 2 3 4))

(display m) (newline) ; ((1 2 3 4) (4 5 6 6) (6 7 8 9))
(display n) (newline) ; ((2 4) (6 8) (9 7) (1 3))
(display v) (newline) ; (1 2 3 4)
(display (matrix-*-vector m v)) (newline) ; (30 56 80)
(display (transpose m)) (newline) ; ((1 4 6) (2 5 7) (3 6 8) (4 6 9))
(display (matrix-*-matrix m n)) (newline) ; ((45 53) (98 116) (135 163))

2.36

| 2.36 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.36 - クラなんとかの日記 2.36 - クラなんとかの日記 のブックマークコメント

accumulate-n を実装する.

seqs の car を accumulate していき,cdr を accumulate-n すればよい.

#!/usr/bin/env gosh
;; -*- coding: utf-8; -*-
; 

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

;; 答え
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      (list)
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

;; 確認
(define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))

(display s) (newline) ; ((1 2 3) (4 5 6) (7 8 9) (10 11 12))
(display (accumulate-n + 0 s)) (newline) ; (22 26 30)

2.35

| 2.35 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.35 - クラなんとかの日記 2.35 - クラなんとかの日記 のブックマークコメント

count-leaves をaccumulate を使って実装する.

再帰がどこにかかるかわかれば簡単.

list の要素がlist である場合に再帰すればよい.

#!/usr/bin/env gosh
;; -*- coding: utf-8; -*-
; 

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

;; 答え
(define (count-leaves tree)
  (accumulate + 0 (map (lambda (x)
                         (if (pair? x)
                             (count-leaves x)
                             1))
                       tree)))
              

;; 確認
(define x (cons (list 1 2) (list 3 4)))
(define y (list x x))

(display x) (newline) ; ((1 2) 3 4)
(display y) (newline) ; (((1 2) 3 4) ((1 2) 3 4))
(display (length x)) (newline) ; 3
(display (length y)) (newline) ; 2
(display (count-leaves x)) (newline) ; 4
(display (count-leaves y)) (newline) ; 8

2.34

| 2.34 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.34 - クラなんとかの日記 2.34 - クラなんとかの日記 のブックマークコメント

(k_n k_{n-1} ... k_1 k_0) のように項のリストが与えられたとして.

  • T_0 = k_0
  • T_n = k_n + T_{n-1} * x

こんな感じで,前の項をx 倍して,項を足す漸化式を考えればよい.

例えば,(1 3 0 5 0 1) を項のリストとして与えられた場合,以下のように式が変形する.

(ここで,リストとは逆順に項が与えられていくことに注意)

  1. 1
  2. 0 + (1) * x = x
  3. 5 + (x) * x = 5 + x^2
  4. 0 + (5 + x^2) * x = 5x + x^3
  5. 3 + (5x + x^3) * x = 3 + 5x^2 + x^4
  6. 1 + (3 + 5x^2 + x^4) * x = 1 + 3x + 5x^3 + x^5
#!/usr/bin/env gosh
;; -*- coding: utf-8; -*-
; 

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

;; 答え
(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coefficient higher-term)
                (+ (* higher-term x)
                   this-coefficient))
              0
              coefficient-sequence))

;; 確認
(define x 2)
(define cs (list 1 3 0 5 0 1))

(display x) (newline) ; 2
(display cs) (newline) ; (1 3 0 5 0 1)
(display (horner-eval x cs)) (newline) ; 79 (= 1 + 3x + 5x^3 + x^5 = 1 + 6 + 40 + 32)
 |