流的实现，操作与部分应用

#lang sicp


#|
流的实现,在后面发现这样定义是不行的，会导致无限递归，内存溢出。可能是因为racket对表达式应用序求值的问题
参考https://www.cnblogs.com/RChen/archive/2012/05/11/2495281.html的方法，重新定义了流的实现
(define (cons-stream a b)
  (cons a (delay b)))
|#
(define-syntax cons-stream;;好像是一种宏定义,不过确实可行，似乎和后文讲的惰性求值有关
  (syntax-rules ()
    [(cons-stream x y) (cons x (delay y))]))
 
(define (stream-car stream)
  (car stream))

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

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


#|本来以为延时求值的实现需要自己写，思路就是用delay用过程把表达式包装起来，force再执行过程。
但是Racket本身已经提供.而且自己写的会爆内存。原因依然可能是表达式求值的问题。所以用Racket自带的函数就行
(define (delay exp)
(lambda () exp))
(define (force delayed-object)
(delayed-object))
|#
;;一个优化，如果一个过程已经被求过值，保存起来，下次求值直接返回结果。这里提供但不调用
(define (memo-proc proc)
  (let ((already-run? false) (res false))
    (lambda ()
      (if (not already-run?)
               (begin (set! res (proc))
                      (set! already-run? true)
                      res)
               res))))
(define (delay-better exp)
  (memo-proc (lambda () exp)))


(define  (stream-ref s n);;提取器，取出流中的第n个元素
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))


(define (stream-map proc s);;映射器，对流中的每个元素执行指定过程,返回一个新流
  (if (stream-null? s)
      '()
      (cons-stream (proc (stream-car s))
                   (stream-map proc (stream-cdr s)))))

(define (stream-for-each proc s);;与映射器相同，求值但不返回
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))

;;考察一个流
(define (display-stream s)
  (stream-for-each display-line s))
(define (display-line x)
  (newline)
  (display x))

;;流过滤器
(define (stream-filter pred stream)
  (cond ((stream-null? stream) '())
        ((pred (stream-car stream))
         (cons-stream  (stream-car stream)
                       (stream-filter pred
                                      (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

#|
一的无穷流
(define ones (cons-stream 1 ones))
;;两个流求和，没有实现多参数map
(define (add-streams s1 s2)
  (stream-map + s1 s2))
;;定义整数流
(define integers (cons-stream (add-streams ones integers)))
;;不使用上面几个定义。
|#

;；生成数列
(define (integers-from n)
  (cons-stream n (integers-from (+ n 1))))
;;自然数列
(define integers
  (integers-from 1))



;;素数筛
#|
工作原理：一个素数的无穷流从2开始。从把其余整数中的2的倍数过滤掉，得到一个从三开始的流。3就是下一个素数，再从流的
后面部分过滤掉所有三的倍数，留下一个从5开始的流。循环往复这个操作。
可描述如下：对流S做筛选，就是形成一个流，第一个元素是s的第一个元素，得到随后的元素的方式是把S的其余部分中过滤掉
所有第一个元素的倍数，再对得到的结果进行筛选。
可以注意到，流是无穷的，素数筛也是无穷的，筛中还包含着筛。
|#

(define (divisible? x y)
  (= (remainder x y) 0))
       
(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

;;test
(define primes
  (sieve (integers-from 2)))
 (stream-ref primes 50)

;;定义一个斐波那契数列
(define (streams-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 (add-streams s1 s2)
  (streams-map + s1 s2))
(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

#|
欧拉加速器，把一个流转化为新流，这个流（数列）收敛速度更快
|#
(define (square x)
  (* x x))
(define (fast-transformer s)
  (let (( s0 (stream-ref s 0))
        (s1 (stream-ref s 1))
        (s2 (stream-ref s 2)))
    (cons-stream (- s2 (/ (square (- s2 s1))
                          (+ s0 (* -2 s1) s2)))
                 (fast-transformer (stream-cdr s)))))

;;可以构造一个流，流的每个元素都是一个流，称为表列
(define (make-tableau transform s)
  (cons-stream s
               (make-tableau transform
                             (transform s))))