結城浩のSICP日記 RSSフィード

2006-05-12

パスカルの三角形 パスカルの三角形 - 結城浩のSICP日記 を含むブックマーク

Rubyで書いたパスカルの三角形を読んでいて、何となくパスカルの三角形を描きたくなったので。

(define (combination n k)
  (cond ((= k 0) 1)
        ((= k n) 1)
        (else (+
          (combination (- n 1) k)
          (combination (- n 1) (- k 1))))))

(define (line n)
  (let loop ((k 0) (result '()))
    (cond ((> k n) (reverse result))
          (else
            (loop (+ k 1)
              (cons (combination n k) result))))))

(let main ((n 0))
  (cond ((< n 10)
          (print (line n))
          (main (+ n 1)))))

実行結果です。

(1)
(1 1)
(1 2 1)
(1 3 3 1)
(1 4 6 4 1)
(1 5 10 10 5 1)
(1 6 15 20 15 6 1)
(1 7 21 35 35 21 7 1)
(1 8 28 56 70 56 28 8 1)
(1 9 36 84 126 126 84 36 9 1)

delayとforce delayとforce - 結城浩のSICP日記 を含むブックマーク

Gaucheマニュアルの「6.15.5 Delayed evaluation」を読んでいます。

まだよく理解していませんが、delayとforceだけではなく、lazyというのもあるようです。

delayはaからaのプロミスを作り、lazyはaのプロミスからaのプロミスを作るようです。

とりあえず、lazyは置いておいて、マニュアルにあるフィボナッチ数列の例を半・写経します。

(define (lazy-car x)
  (car (force x)))

(define (lazy-cdr x)
  (cdr (force x)))

(define (lazy-take x k)
  (cond ((<= k 0) '())
        (else
          (cons (lazy-car x)
                (lazy-take (lazy-cdr x) (- k 1))))))

(define (lazy-map proc x y)
  (cond ((null? x) '())
        (else
          (cons (proc (lazy-car x) (lazy-car y))
                (delay    ; ここに要るのか!
                  (lazy-map proc (lazy-cdr x) (lazy-cdr y)))))))

(define (fib)
  (cons 0
    (cons 1
      (delay    ; ここにも!
        (lazy-map + (fib) (cdr (fib))))))) ; ここはcdrでよいんだね。

(lazy-take (fib) 10)
;=> (0 1 1 2 3 5 8 13 21 34)

関数名をlazy-...だけれど、気持ちはforce-...なのではないだろうか。仕切り直し。

引数のpはpromiseのつもり。夢の約束をforceで無理矢理現実化する。でも、無限に長くなるcdrのところはforceするのをdelayする。

こうすると、※のところがdelayになるの、納得する。

(define (force-car px)
  (car (force px)))

(define (force-cdr px)
  (cdr (force px)))

(define (force-take px k)
  (cond ((<= k 0) '())
        (else
          (cons (force-car px)
                (force-take (force-cdr px) (- k 1))))))

(define (force-map proc px py)
  (cond ((null? px) '())
        (else
          (cons (proc (force-car px) (force-car py))
                (delay ;※
                  (force-map proc (force-cdr px) (force-cdr py)))))))

(define (fib)
  (cons 0
    (cons 1
      (delay    ;※
        (force-map + (fib) (cdr (fib))))))) ; ここがcdrでよいのは納得している

(force-take (fib) 10)
;=> (0 1 1 2 3 5 8 13 21 34)

あいあい2006/05/30 19:04ちょっと教えてもらいたんですが、
パスカルの三角形で、
-------------------------------
m 0 1 2 3 4 ・・・
n
0 1
1 1 1
2 1 2
3 1 3 3 1
4 1 4 6 4 1



-------------------------------
P(n,m)を求める関数を作るとき
schemeでどう書いたらいいですか?
例えば
(P 4 2)
=6
みたいになるプログラムを作りたいんです。

hyukihyuki2006/05/30 19:23ええと…。
(define P combination)
ではいかがでしょうか(^_^;;
# つまり、http://sicp.g.hatena.ne.jp/hyuki/20060512/pascal で定義してあるcombinationがそのままPだと思います。