惰性求值与无穷流

目录

如何在计算机中表示一个无穷序列?比如所有自然数,所有偶数,所有质数等。难道我们需要一个无穷的内存来实现吗,很显然不能这样,使用惰性求值就可以很好的解决这个问题

无穷流程序

; 使用宏实现惰性求值实在太漂亮了
(define-syntax mydelay
  (syntax-rules ()
    ((_ exp) (lambda () exp))))

(define (myforce exp)
  (exp)
  )


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

; 实现惰性的 cdr
(define (stream-cdr stream) (myforce (cdr stream)))

; 实现惰性的 cons
(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
     (cons a (mydelay b))))
  )

(define (stream-take stream n)
  (if (= n 1)
      (stream-car stream)
      (cons (stream-car stream) (stream-take (stream-cdr stream) (- n 1)))
      )
  )

(define the-empty-stream '())
(define (stream-null? stream)
  (null? stream))

(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-add s1 s2)
  (stream-map + s1 s2)
  )

; 定义从 n 开始数列
(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1)))
  )

; 定义 integers 为 1 到无穷大的序列
(define integers (integers-starting-from 1))

; 定义全是 1 的无穷序列
(define ones (cons-stream 1 ones))

; 定义所有自然数加 1 的无穷序列
(define add-ones (stream-add ones integers))

; 取序列的前 100 个
(stream-take integers 100)
(stream-take ones 100)
(stream-take add-ones 100)

目录