Hatena::Groupsicp

SICP in the blanket

2008-09-26

2章

01:16 | はてなブックマーク - 2章 - SICP in the blanket 2章 - SICP in the blanket のブックマークコメント

accumulate

SICPでは結果を右に溜める fold-right として定義されている。(R6RSの fold-right と同じ)

(define (accumulate f a xs)
  (if (null? xs) a
      (f (car xs)
         (accumulate f a (cdr xs)))))

Gaucheの(SRFI-1 の) fold も結果を右に溜める

gosh> (fold cons '() '(1 2 3 4))
(4 3 2 1)
gosh> (fold-right cons '() '(1 2 3 4))
(1 2 3 4)

enumerate-tree

preorderで辿る。ここでの tree はリストのリスト。

(define (enumerate-tree tree)
  (cond [(null? tree) '()]
        [(not (pair? tree)) (list tree)]
        [else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree)))]))

ex2.35

何をさせたいのか謎。

(define (count-leaves2 t)
  (accumulate (lambda (x a) (+ a (length x)))
              0
              (map enumerate-tree t)))

ex2.36

(define s1 '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))
(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

ex2.37

vector and matrix

(define m1 '((1 2 3 4) (4 5 6 6) (6 7 8 9)))

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

(define (matrix-*-vector m v)
  (map (lambda (w) (dot-product v w))
       m))

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

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

ex2.38

結合律

ex2.39

fold-right の方はいかにも無駄が多い。

(define (reverse1 seq)
  (fold-right (lambda (x y) (append y (list x))) '() seq))

(define (reverse2 seq)
  (fold-left (lambda (x y) (cons y x)) '() seq))

ex2.40

(define (unique-pairs n)
  (flatmap (lambda (i)
             (accumulate (lambda (j a) (cons `(,i ,j) a))
                         '()
                         (iota (- i 1) 1)))
           (iota (- n 1) 2)))

ex2.41

flatmap を素直に使うとかなり読みづらくなる。

内包表記を使うとスッキリ。(SRFI-42)

(use srfi-42)
(define (ex2-41 s)
  (list-ec (: x 1 s)
           (: y 1 x)
           (: z 1 y)
           (if (= s (+ x y z)))
           (list x y z)))

MattinglyMattingly2012/01/09 19:57Good to see real expertise on display. Your cotnrbiution is most welcome.

exjurlpgksoexjurlpgkso2012/01/10 17:23LtAXNu <a href="http://qwymdffdvjgu.com/">qwymdffdvjgu</a>

igtnwvigtnwv2012/01/15 01:29lgrZ4A , [url=http://dgncekoxiect.com/]dgncekoxiect[/url], [link=http://kgqqnwfzdjcy.com/]kgqqnwfzdjcy[/link], http://jtteuxkxmnoa.com/

トラックバック - http://sicp.g.hatena.ne.jp/blanketsky/20080926