Racket, SICP stream learning

5338 ワード

Windowsに最新のRacket 5.2.1を再インストールしました.
まるで発見して、Common-Lispのインストールは本当に穴のお父さんを比較して、Racketはlispの比較的に理想的な選択を研究して学ぶかもしれません!
WindowsでもUbuntuでも、Lispを学んで以来、Common Lispの様々な実装+開発環境がインストールされていることが多く、どれも配置が面倒で、そういう問題もあります.それに比べて、Racketをインストールするのは超バカです.
紆余曲折の末、SICP 220ページから始まるstreamのいくつかのサンプルコードがやっとオンになった.ここで注意しなければならないのは、
本で述べたcons-streamはspecial formですが、最初は簡単なfunctionを書きました.
; this won't work as a simple function
(define (cons-stream a b)
    (cons a (delay b)))

しかし、これは実際にはworkではありません.ストリームが大きい場合や無限ストリームの場合、無限再帰、メモリオーバーフローの原因になります.解決策はstack overflowの前の答えを参照し,Racketのdefine-syntax構文を用いてマクロを定義した.実はCommon Lispのマクロと少し似ていますが、定義時に使う文法に違いがあります.角カッコを使います.詳しくはコードを参照してください.
Common Lispのリストのsubseq関数と似ていて、ストリームのある区間のサブシーケンスを切り取るためのstream-subseq関数を簡単に実現しました.display-stream関数の印刷に合わせて、ストリームの中間の任意のセグメントの情報を簡単に理解することができます.後のテスト出力世代コードは基本的にこのように書きました.
無限流シフト後の加算,乗算,さらには他の演算と組み合わせて任意に組み合わせることで,流が最も使い心地のよいところである.コードにはSICP原書に付随するふるい法求素数シーケンスの実装が含まれている.
いくつかの例の簡単な実験を通じて、確かにstreamの効果は強いことが分かった.本質的に各ステップの計算は不活性評価であるため、シーケンスの後続の数値を推定しても、リストのように多くの割り当て空間のオーバーヘッドをもたらすことはありません.フィボナッチ数列は簡単に後ろに計算できます.次は、デバッグに合格したテストコードです.
#lang racket

;(define (delay exp)
;  (lambda () exp))
;  ;(memo-proc (lambda ()
;  ; exp)))
;
;(define (force delayed-object)
;  (delayed-object))
;
;(define (memo-proc proc)
;  (let ((already-run? false) (result false))
;    (lambda ()
;      (if (not already-run?)
;          (begin (set! result (proc))
;                 (set! already-run? true)
;                 result)
;          result))))

(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))

; this won't work as a simple function
;(define (cons-stream a b)
;  (cons a (delay b)))

; This is scheme syntax for macro
; http://stackoverflow.com/questions/5610480/scheme-sicp-r5rs-why-is-delay-not-a-special-form
(define-syntax cons-stream
  (syntax-rules ()
    [(cons-stream x y) (cons x (delay y))]))

(define the-empty-stream '())

(define (stream-null? stream)
  (null? stream))

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

(define (stream-ref s n)
  (if (stream-null? s) the-empty-stream
      (if (= n 0)
          (stream-car s)
          (stream-ref (stream-cdr s) (- n 1)))))

(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
      the-empty-stream
      (cons-stream (apply proc (map stream-car argstreams))
                   (apply stream-map 
                          (cons proc (map stream-cdr argstreams))))))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

; Neil, 2012-05-10
(define (stream-subseq stream a b)
  (cond ((stream-null? stream) the-empty-stream)
        ((= a b) the-empty-stream)
        ((> a b) the-empty-stream)
        (else (cons-stream (stream-ref stream a)
              (stream-subseq stream (+ a 1) b)))))

(define (display-line x)
  (newline)
  (display x))

(define (display-stream s)
  (stream-for-each display-line s))

; examples
;(let ((x (delay (+ 1 2))))
;  (for ([i (in-range 1 10)])
;            (display (force x))))
;
(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

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

;(display-line (stream-ref integers 0))
(let ((x (stream-subseq integers 10000 10010)))
  (display-stream x))

(define odd-numbers 
  (stream-filter odd? integers))

(display-stream (stream-subseq odd-numbers 50 60))
  
;(let ((x (cons-stream 1 (cons-stream 2 '(3)))))
;  (display-stream x))

(define (stream-add s n)
  (stream-map (lambda (x)
                (+ x n)) s))

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

(define fib
  (cons-stream 1
               (cons-stream 1
                            (add-streams fib
                                        (stream-cdr fib)))))

(display-stream (stream-subseq fib 150 160))


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

(divisible? 10 2)

(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 (integers-starting-from 2)))

(display-stream (stream-subseq primes 1000 1010))

次に本で述べたオラが発明したシーケンス加速器のアルゴリズムを真剣に体得するつもりだ.本当にすごいidea