免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 3779 | 回复: 2

惰性不足 [复制链接]

论坛徽章:
0
发表于 2009-03-07 15:06 |显示全部楼层
SICP 3.5 讨论了如何构造两个无穷流 S, T 构成的序对流 (S(i), T(j)),其中 i <=j。这个操作记为 (pairs S T)

书本的正文给出了了一个“三部分”的方案,把 (pairs S T) 分成三个部分:

  •   (S(0), T(0))
  •   (S(0), T(1)), (S(0), T(2)), (S(0), T(3)), ......
  •   (pairs (cdr S), (cdr T))


下面的图是直观解释

ch3-Z-G-47.gif

一个可行的生成方式为:把第 2,3 部分两个流用 interleave 混合起来,然后把第一部分,即元素 (S(0), T(0)) 插入流首。对应代码为


  1. (define (pairs s t)
  2.   (cons-stream
  3.    (list (stream-car s) (stream-car t))
  4.    (interleave
  5.     (stream-map (lambda (x) (list (stream-car s) x))
  6.                (stream-cdr t))
  7.     (pairs (stream-cdr s) (stream-cdr t)))))
复制代码


但这种划分方式有点别扭。如果把横线上方的看做一个流,横线下方的看作另一个流,再用 interleave 混合起来,则看上去要简洁得多。书本的习题 3.68 提出了这个“两部分”方案,并给出了代码


  1. (define (pairs s t)
  2.   (interleave
  3.    (stream-map (lambda (x) (list (stream-car s) x))
  4.                t)
  5.    (pairs (stream-cdr s) (stream-cdr t))))
复制代码


可惜这段代码在标准 scheme 里并不能正常工作。因为在表准 scheme 中,函数对参数的求值是严格的。interleave 是函数,它会对第二个参数 pairs 严格求值;而 pairs 调用 interleave;interleave 再对 pairs 求值,....... 如是反复,直到耗尽全部资源。

“两部分” 的方案之所以失败,是因为标准 scheme 惰性不足。可以想象,如果用一个惰性求值的语言来实现 pairs,则 “两部分” 方案的方式也是可行的。我用 lazy-scheme 来测试了上面的代码,得到


  1. > (define p (pairs integers integers))

  2. > (display (take 10 p))
  3. ((1 1) (2 2) (1 2) (3 3) (1 3) (2 3) (1 4) (4 4) (1 5) (2 4))
复制代码


回过头来看一下 “三部分” 的方案,容易看出,pairs 此时调用了 cons-stream,这是一个宏,它对参数的求值是惰性的。

不过仔细想一下,既然我们能构造出惰性的 cons-strem,难道我们就不能让 interlever 对参数的求值也延迟一下吗?这当然是可以的,一方面,我们可以像 cons-stream 那样把 interleave 实现为宏;另一方面,我们也可以主动使用 delay 把参数延迟后再送给 interleave。如果采用后一种办法,则 interleave 要在适当的时候主动 force 被延迟的值。

看看习题 3.68 的代码


  1. (define (pairs s t)
  2.   (interleave
  3.    (stream-map (lambda (x) (list (stream-car s) x))
  4.                t)
  5.    (pairs (stream-cdr s) (stream-cdr t))))
复制代码


关键问题在于 interleave 会对 (pairs ...) 进行求值,如果把它延迟呢?反正 interleave 只需要在第一个参数里提取数据就可以产生输出了。


  1. (define (lazy-pairs s t)
  2.   (lazy-interleave
  3.    (stream-map (lambda (x) (list (stream-car s) x))
  4.                t)
  5.    (delay (lazy-pairs (stream-cdr s) (stream-cdr t)))))
复制代码


如果这样,那么 interleave 的第一个参数是一个流,而第二个参数只是个 promise。 interleave 从第一个参数中提取一个元素,递归调用自身,交换两个参数的位置,当然原来的第一个参数要 cdr 一下。但重点是此时 promise 被放到第一个参数位置上了, 在interleave 试图从中提取数据时会出错,因为它是 promise 而不是流。 容易看出,可以在递归时对 promise 进行 force。于是我们得到修改过的 interleave,称为 lazy-interleave


  1. (define (lazy-interleave s t)
  2.   (cons-stream (car s)
  3.                (lazy-interleave (force t) (cdr s))))
复制代码


测试一下:


  1. > (define p (lazy-pairs integers integers))
  2. > (take p 10)
  3. ((1 1) (2 2) (1 2) (3 3) (1 3) (2 3) (1 4) (4 4) (1 5) (2 4))
复制代码


结果与用 lazy-scheme 计算出的一致。

[ 本帖最后由 win_hate 于 2009-3-7 15:19 编辑 ]

论坛徽章:
0
发表于 2009-03-07 15:07 |显示全部楼层
有两个地方值得指出:


    [1] “两部分” 方案与 "三部分” 方案理论上都能遍历全体序对,或者说:对于任意给定的序对,它一定会出现在流中。但两
    者生成的序对在流中的位置是不同的;
    [2] "三部分" 方案有它自己的作用,见习题 3.69 的讨论。

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2009-03-07 18:45 |显示全部楼层
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP