SICP lec6a : 流 I part3 (lazy seq 解释)

此篇为 SICP教程 6a 的笔记

找出 1,000 ~ 1,000,000 中的第二个质数

若是 流 的方式来处理，流程如下：

map 所有 1,000 ~ 1,000,000 的数字filter 其中的质数

这显然是非常非常佔记忆体的事情，若是更大的範围呢，况且只是要找第二个数，用这个例子来比较传统 时序 概念与流概念谁比较适合的话，答案反而是前者。

现在反而矛盾了，之前把 流 吹捧得这么厉害，能把逻辑複杂的规则呈现的简单又清楚，但实务上却是佔记忆体且无法处理大型数据，怎么会这样？

其实接下来才是真正厉害的地方。

流 之所以会输 传统时序 的地方，就是需要 先产生所有计算要用到的数据 才进行处理，那能不能让数据在 需要计算 的时候再进行计算呢？

如果用图形来表示(影片当中用道具)：
失败的流：

想像中成功的流：

当result要求一个数据，就从 流 的尾部(tail)向最后一个process拉取一个数据，最后一个process再向前一个process拉取，以此类推。只有在末端要求一定量数据时，源头才产生定量的数据。

但有什么 data structure 可以这样搞？ 有的! 而且是最基本的种类，就是 "function as data" 来达成这个梦幻的 流。

首先认识几个基本元素 con-stream, head, tail

(defn con-stream [x y]    (cons x (delay y)))(defn head [s] (car s))(defn tail [s] (force (cdr s)))

delay 所做的有两件事 1. 产生function的表达式 2.一个执行许可，当接收到执行许可时再去执行。force 就是 delay 的执行许可

回到最一开始的问题，来检视一下 梦幻流 的执行过程

(head (tail (filter prime? (map 每一个数 1000 1000000)))))

(map 每一个数 1000 1000000) -> (cons 1000 (delay (map 每一个数 1001 1000000)))

map第一个数 1000 出来计算其他的先不计算

(filter prime? (map 每一个数 1000 1000000))-> (filter prime? 1000)-> (filter prime?(tail (cons 1000 (delay (map 每一个数 1001 1000000)))))

filter prime? 计算第一个数 1000执行tail，force (map 每一个数 1001 1000000)递迴的对 tail 做 filter prime?产生第一个质数后停止，但要求是第二个因此继续启动

上述可见，filter出来的数据，不会比map的还要多，因为filter去要求(force delay)的时候，数据才会产生。

真正神奇的地方 delay 与 force ，实作上也非常的简单

(defn delay [exp] (fn [] (exp)))(defn force [fn] (fn))

delay 神奇的地方在于将 "预期事件的执行顺序" 与 "实际电脑的执行顺序" 解耦开来，以至于可以用 "综观全局不考虑每个时间状态" 的表示方式，做出 "最有效率，不佔无效空间" 的执行。

还有一个问题，当执行递迴的tail时会出现 (tail (tail (tail...)))，每一次计算新的数据，就要把以前的tail都计算一次，相当没有效率，因此若能将之前计算过的tail都记录下来就能避免，因此将delay改成为

(defn delay [exp] (memo-proc (fn [] (exp))))

memo-proc是一个function，记录前面所有产生过的数据，让每一次force tail时只做一次的计算。