Hatena::Groupsicp

SICP読書メモ

 | 

2009-03-29

4.2.3 遅延リストとしてのストリーム 01:22

遅延評価が組み込まれた処理系で、以前実装したストリームを再度試してみる。

以前はかなり回りくどい工夫をしたけど、今回は cons / car / cdr を合成手続きで定義して

遅延評価させるだけで良い。

   (define (cons a b)
     (lambda (x) (x a b)))

   (define (car pair)
     (pair (lambda (a b) a)))

   (define (cdr pair)
     (pair (lambda (a b) b)))

SICPの最初の頃出てきた、手続きで表現した対(とリスト)で実装。以前実験したストリーム演算、一通り試したら一応ちゃんと動いていた。

但し今回はリスト=ストリームなので、より自然に表現できる。

   ;;リストのn番目を表示(動作確認用)
   (define (list-ref items n)
     (print (car items))
     (if (< n 1)
         (car items)
         (list-ref (cdr items) (- n 1))))

   ;;リストをフィルタする
   (define (list-filter p items)
     (if (p (car items))
         (cons (car items)
               (list-filter p (cdr items)))
         (list-filter p (cdr items))))

   ;;map
   (define (list-map proc items)
     (cons (proc (car items))
           (list-map proc (cdr items))))

   ;;複数のリストを引数に取り、それを引数の手続きで一つにするmap
   (define (lists-map proc list1 list2)
     (cons (proc (car list1) (car list2))
           (lists-map proc (cdr list1) (cdr list2))))

   ;;list-mapを利用して、リストの乗算
   (define (scale-lists items factor)
     (list-map (lambda (x) (* x factor)) items))

   ;;lists-mapを利用して、リストの加算
   (define (add-lists list1 list2)
     (lists-map + list1 list2))

   ;;無限に1が続くリスト
   (define ones
     (cons 1 ones))

   ;;整数 numbers は ones と numbers を加算したリスト
   ;; 1
   ;; 1 + (1)
   ;; 1 + (1 + 1)
   ;; 1 + (1 + 1 ....)
   (define numbers
     (cons 1 (add-lists ones numbers)))

   ;;偶数 even-numbers は2で割りきれる整数
   (define even-numbers
     (list-filter
       (lambda (x) (< (- x (* (/ x 2) 2)) 1))
       numbers))

   (list-ref even-numbers 10)

   ;;フィボナッチ数列は、フィボナッチ数列と(cdr フィボナッチ数列)の加算リスト
   ;;
   (define fib-numbers
     (cons 1
           (cons 1
                 (add-lists (cdr fib-numbers)
                            fib-numbers))))

   (list-ref fib-numbers 10)

   ;;素数primesは、素数を判定するprime?手続きでフィルタした整数
   (define primes
     (list-filter prime?
                  (list-filter (lambda (n)(> n 1)) numbers)))

   ;;素数を判定するprime?は、素数列primesで割り切れない整数の場合trueを返す
   (define (prime? n)
     (define (iter ps)
       (if (> (square (car ps)) n)
           #t
           (if (divisible? n (car ps))
               #f
               (iter (cdr ps)))))
     (iter primes))

   (list-ref primes 10)

sobdtmarvdsobdtmarvd2013/12/17 16:47ccgkctjdq, <a href="http://www.qbmpdylnok.com/">liqdnfobbj</a> , [url=http://www.nfgrvpybhu.com/]flnnrlozne[/url], http://www.qebafatuhp.com/ liqdnfobbj

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20090329
 |