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

2006-05-19

勉強方針 勉強方針 - 結城浩のSICP日記 を含むブックマーク

現在の勉強方針を書いておきます。

  • Schemeをやる
    • SICPをやる、からちょっと修正(^_^)
  • 毎日なんでもよいからSchemeのコードを書いて動かす
    • 動くコードを書くのがポイント
  • 題材選びは「何でもよいから好きなもの」
    • SICPリングの他の人のページをちらちら見て、刺激をもらう
    • もっとよいコードが書けないか考える(書けたら自慢する)
    • その際に必ずマニュアルを調べて情報を増やす
  • コメントなどで教えてもらったことも自分で試してみる
  • 「後で読む」メソッドは使うのやめた。性に合わない
  • ときどきはSICPも開く(^_^;

ストリームの練習、もっと ストリームの練習、もっと - 結城浩のSICP日記 を含むブックマーク

記憶をたどってストリームの練習をします。

まずは無限整数列を定義します。

(use util.stream)

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

次に、1から始める自然数列。

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

(stream-car naturals)
;=> 1

(stream-ref naturals 10)
;=> 11

で、昨日作った「割り切れるかどうか」を調べる述語。

(define (divisible? x y) (zero? (remainder x y)))

(divisible? 100 2)
;=> #t

(divisible? 100 3)
;=> #f

これを元に、nの倍数からなる無限列を作ります。

(define (divisible-stream n st)
  (cond ((divisible? (stream-car st) n)
          (stream-cons (stream-car st)
            (divisible-stream n (stream-cdr st))))
        (else
          (divisible-stream n (stream-cdr st)))))

たとえば、偶数列。

(define evens
  (divisible-stream 2 naturals))

(stream-car evens)
;=> 2

(stream-ref evens 10)
;=> 22

14の倍数列は、偶数列に7の倍数列を重ねて作ります。フィルタを重ねるようなものです。

(define divisible-by-14
  (divisible-stream 7 evens))

(stream-car divisible-by-14)
;=> 14

(stream-ref divisible-by-14 10)
;=> 154

stream-takeとstream->listを使うと、リストにしてみることができます。

(stream->list (stream-take naturals 10))
;=> (1 2 3 4 5 6 7 8 9 10)

(stream->list (stream-take evens 10))
;=> (2 4 6 8 10 12 14 16 18 20)

(stream->list (stream-take divisible-by-14 10))
;=> (14 28 42 56 70 84 98 112 126 140)

そのものずばりのstream-filterもあるようですね。

(define even-stream
    (stream-filter (lambda (n) (divisible? n 2)) naturals))

(stream->list (stream-take even-stream 10))
;=> (2 4 6 8 10 12 14 16 18 20)

さて、今後は逆に割り切れないほうの数列を作ります。

(define (sieve n s)
  (cond ((not (divisible? (stream-car s) n))
          (stream-cons (stream-car s)
            (sieve n (stream-cdr s))))
        (else
          (sieve n (stream-cdr s)))))

(stream->list (stream-take (sieve 2 naturals) 10))
;=> (1 3 5 7 9 11 13 15 17 19)

割り切れない数でフィルタするのを重ねていくと…

(define (make-primes n s)
  (let* ((t (sieve n s))
        (m (stream-car t)))
    (stream-cons
      (stream-car t)
      (make-primes m t))))

素数列が作れるかな。

(define primes
  (stream-cons 2
    (make-primes 2 (integers-starting-from 2))))

やってみましょう。

(stream->list (stream-take primes 10))
;=> (2 3 5 7 11 13 17 19 23 29)

(stream-ref primes 0)
;=> 2

(stream-ref primes 1)
;=> 3

(stream-ref primes 100)
;=> 547

(stream-ref primes 1000)
;=> 7927

できたできた♪

もう眠いから答え合わせ(?)は朝にやろうっと。

トラックバック - http://sicp.g.hatena.ne.jp/hyuki/20060519