関数型言語の勉強にSICPを読もう - (49) 3章 - 標準部品化力、オブジェクトおよび状態 (193-195ページ)

問題3.52の続き

昨日悩んでいた点は、結局 force をメモするかどうかで結果が違うことを考慮してなかったのが問題でした。
ヒントを下さった g:sicp:id:hyukiさんありがとうございました。

Gaucheのforceはメモするので、メモしたくない場合は

 (define-macro (delay x)
               `(lambda ()
                  ,x))
 (define (force x)
        (apply x '()))

のようにしておきます。

streamへの高階関数をたくさん適用すると頭がまわらなくなるので後で復習しよう。

無限ストリーム

問題があったわけではないのだけど、無限ストリームを体験したかったので紹介されているコードを実行してみた。

(define (integer-starting-from n)
  (cons-stream n (integer-starting-from (+ n 1))))

(define integers (integer-starting-from 1))

(define (divisible? x y) (= (remainder x y) 0))

(define no-sevens
  (stream-filter (lambda (x) (not (divisible? x 7)))
                 integers))

;; 7で割り切れない1,000番目の整数
(stream-ref no-sevens 1000)
;; 1167

;; Eratosthenesの篩（ふるい）
(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (integer-starting-from 2)))

(stream-ref primes 1000)
;; 7297

面白い。

問題3.53

紙にも書かず頭だけで考えた。1 2 4 8 16 32 のように 2^nのストリームになるはず。
→ 正解

問題3.54

3.53の問題から類推した。

(define (integer-starting-from n)
  (cons-stream n (integer-starting-from (+ n 1))))

(define integers (integer-starting-from 1))

(define (mul-stream s1 s2)
  (stream-map * s1 s2))

(define factorilals (cons-stream 1 (mul-stream factorilals integers)))

(stream-ref factorilals 1)
(stream-ref factorilals 2)
(stream-ref factorilals 3)
(stream-ref factorilals 4)
(stream-ref factorilals 5)

問題3.55

だいぶ分かってきた。

(define (integer-starting-from n)
  (cons-stream n (integer-starting-from (+ n 1))))

(define integers (integer-starting-from 1))

(define (add-stream s1 s2)
  (stream-map + s1 s2))

(define (partial-sums s)
  (cons-stream
   (stream-car s)
   (add-stream (stream-cdr s) (partial-sums s))))

(define s (partial-sums integers))

(stream-ref s 1)
(stream-ref s 2)
(stream-ref s 3)
(stream-ref s 4)
(stream-ref s 5)
(stream-ref s 6)

g:sicp:id:hyuki:20060520:harmonic2という答えも。

※「SICPを読もう」の目次はこちら