[ML, Scheme] 无穷表, Stream

win_hate

本贴内容来自 《ML 程序设计语言》(Paulson) 的第 5 章：函数和无穷数据。

在惰性求值语言中如 Haskell 中，惰性是内建的，所以能轻易定义无穷数据。而在严格求值的语言中，要实现惰性求值，就要花费额外的工夫。SICP 第三章最后一节 Strem，讨论的就是这个问题。本贴给出几个在 ML 中实现无穷表的例子，可以与 SICP 对照着看一下：它们的手段是类似的。

[ 本帖最后由 win_hate 于 2008-11-7 16:03 编辑 ]

win_hate

在 Scheme 中，惰性求值是通过 delay 来实现的。如果想延迟表达式 E 的求值，可以构造找一个无参函数 (lambda () E)，在需要时，调用这个函数就可以得到 E 的值.

困难在于，如何构造 (lambda () E) 呢？如果把 delay 实现为函数，比如 (delay (E) (lambda () E))，这样是不行的。因为此时 E 是 delay 的参数，按 scheme 的严格求值方式，在构造 (lambda () E) 之前，E 已经被求值了。

绕过这个困难的一个方法为使用特殊形式，即宏。下面是一个“山寨版” 的 delay 和 force，后者取消延迟

1. 
   
2. (define-syntax delay
   
3.   (syntax-rules ()
   
4.     ((_ x) (lambda () x))))
   
5. 
   
6. (define (force x)
   
7.   (x))
   

复制代码

SICP 中还提到了一些优化手段，不过在这里不关心它们。现在我们知道，SICP 中给出的惰性手段就是 delay，它有两个要点：宏和无参函数。

[ 本帖最后由 win_hate 于 2008-11-7 10:37 编辑 ]

win_hate

下面我们来看一个 ML 实现惰性表的例子

1. 
   
2. datatype 'a seq = Nil | Cons of 'a * (unit-> 'a seq);
   

复制代码

• datatype 定义数据类型和相应的建构函数
• unit-> 'a seq 是一个无参函数类型
  

对 Cons (x, y)， 利用 y() 就可以得一个新表。这个新表正好是无穷序列 Cons(x,y) 中 x 之后的部分。

表头插入函数 cons

1. 
   
2. fun cons x xq = Cons (x, fn()=>xq);
   

复制代码

car 和 cdr

1. 
   
2. exception Empty
   
3. fun car (Cons(x, _)) = x
   
4.   | car Nil = raise Empty
   
5. 
   
6. fun cdr (Cons(_, y)) = y()
   
7.   | cdr Nil = raise Empty
   

复制代码

既然定义了表尾 Nil，这套机制应该可以用在有穷表上：

1. 
   
2. - val x = cons 1 (cons 2 (cons 3 Nil));
   
3. > val x = Cons(1, fn) : int seq
   
4. 
   
5. - car x;
   
6. > val it = 1 : int
   
7. 
   
8. - car (cdr x);
   
9. > val it = 2 : int
   
10. 
    
11. - car (cdr (cdr (cdr x)));
    
12. ! Uncaught exception:
    
13. ! Empty
    
14. -
    

复制代码

构造一个无穷表？ 比如 from k，生成序列：k, k+1, k+2, ...

看上去应该是：

1. 
   
2. - fun from k = cons (k, from (k+1))
   

复制代码

但这是不行的，应为 from (k+1) 现在是 cons 的参数。cons 是 ML 中一个自定义函数，它的求值方式是严格的。在 Scheme 中有宏，在 ML 中有 datatype

1. 
   
2. fun from k = Cons (k, fn()=>from (k+1));
   

复制代码

直接用 'a seq 的构造子 Cons 就可以了。

试一下

1. 
   
2. - val N=from 0;
   
3. > val N = Cons(0, fn) : int seq
   
4. 
   
5. - car N;
   
6. > val it = 0 : int
   
7. 
   
8. - car (cdr N);
   
9. > val it = 1 : int
   
10. 
    
11. - car (cdr (cdr N));
    
12. > val it = 2 : int
    

复制代码

再来个 take，

1. 
   
2. fun take xq 0 = []
   
3.   | take Nil _ = raise Subscript
   
4.   | take xq n = (car xq) :: (take (cdr xq) (n-1));
   

复制代码

1. 
   
2. - take N 10;
   
3. > val it = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] : int list
   

复制代码

(先到这里，欢迎拍砖).

[ 本帖最后由 win_hate 于 2008-11-7 11:37 编辑 ]

win_hate

没人拍砖，自己拍一下。

上面构建的流，流首总是被预先求出的，所以这个方案不够懒惰。书本的习题提供了另一个方案

1. 
   
2. datatype 'a seq = Nil | Cons of unit->'a * 'a seq;
   

复制代码

此时流首和后继都是通过一个无参函数返回的。cons, car, cdr 修改如下：

1. 
   
2. fun cons x xq = Cons (fn()=> (x, xq));
   
3. 
   
4. exception Empty
   
5. fun car (Cons(f)) = #1 (f())
   
6.   | car Nil = raise Empty
   
7. 
   
8. fun cdr (Cons(f)) = #2 (f())
   
9.   | cdr Nil = raise Empty
   

复制代码

对一个有穷表试一下:

1. 
   
2. - val x = cons 1 (cons 2 Nil);
   
3. > val x = Cons fn : int seq
   
4. 
   
5. - car x;
   
6. > val it = 1 : int
   
7. 
   
8. - cdr x;   
   
9. > val it = Cons fn : int seq
   
10. 
    
11. - (car o cdr) x;
    
12. > val it = 2 : int
    
13. 
    
14. - (car o cdr o cdr) x;
    
15. ! Uncaught exception:
    
16. ! Empty
    

复制代码

构造一个无穷表生成函数 from，配套一个 take

1. 
   
2. fun from k = Cons (fn()=> (k, from (k+1)));
   
3. 
   
4. fun take xq 0 = []
   
5.   | take Nil n = raise Subscript
   
6.   | take xq n = (car xq)::(take (cdr xq) (n-1));
   

复制代码

效果:

1. 
   
2. - val N=from 0;
   
3. > val N = Cons fn : int seq
   
4. 
   
5. - take N 10;
   
6. > val it = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] : int list
   

复制代码

MMMIX

win_hate  有研究过 PLT DrScheme 中的 lazy scheme 么？

win_hate

原帖由 MMMIX 于 2008-11-9 13:39 发表
win_hate  有研究过 PLT DrScheme 中的 lazy scheme 么？

没有。我有两个猜测

• 从 mzscheme 运行时打印出的信息来看，它在读到 #lang lazy 后加载了一堆库。因此猜测它也就用了类似 SICP 中的 delay 和 force. 而且我记得看到一些数据是 promise.
  
• 但在 mzscheme 中对 cons 求值可以看到它是个 primitive-procedure 而不是宏。因此猜测它本身是 lazy 的，也许读到  #lang lazy 后加载了一个独立的解析器。
  

这两个猜测是矛盾的，不知道哪个对。

MMMIX

我一直挺好奇 PLT Scheme 的 lazy scheme 是怎么实现的。

win_hate

SICP 第四章讨论如何用 Scheme 的内建机制实现一个 Scheme 解释器。其中 4.2 讨论惰性求值，也就是用严格 Scheme 解释器实现一个惰性 Scheme 解释器。

win_hate

书本的习题还提供了一种 “更具惰性” 的实现

1. 
   
2. datatype 'a seqnode = Nil
   
3.                     | Cons of 'a * 'a seq
   
4. 
   
5. and 'a seq = Seq of unit-> 'a seqnode;
   

复制代码

这个实现有两种而不是一种类型：seq 和 seqnode。每次对 seq 求值得到一个 node, 而一个 node 是一个 'a 类型和 seq 的对。

cons

1. 
   
2. fun cons x xq = Seq(fn()=> Cons(x, xq));
   

复制代码

试下先：

1. 
   
2. - cons 1 Nil;
   
3. ! Toplevel input:
   
4. ! cons 1 Nil;
   
5. !        ^^^
   
6. ! Type clash: expression of type
   
7. !   'a seqnode
   
8. ! cannot have type
   
9. !   int seq
   
10. -
    

复制代码

bump! 出错了。

cons 1 Nil 太顺手了，lisp 中是这样，前面两个 ML 也这样。但这里情况不同。

在前面的例子中， Nil 是个 'a seq, 即空表(流)。但在这个例子中 Nil 是个 'a seqnode. cons x xq 调用 Cons (x, xq)，所以 xq 应该是个 'a seq 才对。

自己做一个空表：

1. 
   
2. val END = Seq (fn()=>Nil);
   

复制代码

再来

1. 
   
2. - val x = cons 1 (cons 2 END);
   
3. > val x = Seq fn : int seq
   

复制代码

这次好像对了，但如何把数据提取出来呢？这比前两个例子要稍微罗唆一点：

1. 
   
2. exception Empty
   
3. 
   
4. fun fst (Cons (x, _)) = x
   
5.   | fst Nil = raise Empty;
   
6. 
   
7. fun rst (Cons (_, y)) = y
   
8.   | rst Nil = raise Empty;
   
9. 
   
10. fun car (Seq(f)) = fst (f());
    
11. 
    
12. fun cdr (Seq(f)) = rst (f());
    

复制代码

fst, rst 是处理 'a seqnode 的，而 car, cdr 则是处理 'a seq 的。

效果：

1. 
   
2. - car x;
   
3. > val it = 1 : int
   
4. 
   
5. - (car o cdr) x;
   
6. > val it = 2 : int
   
7. 
   
8. - (car o cdr o cdr) x;
   
9. ! Uncaught exception:
   
10. ! Empty
    
11. -
    

复制代码

form 和 take 和自然数集

1. 
   
2. fun from k = Seq(fn()=> (Cons (k, (from (k+1)))));
   
3. 
   
4. val N = from 0;
   
5. 
   
6. fun take xq 0 = []
   
7.   | take xq n = (car xq)::(take (cdr xq) (n-1))
   
8.     handle Empty => raise Subscript;
   

复制代码

1. 
   
2. - take N 100;
   
3. > val it =
   
4.     [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
   
5.      21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
   
6.      39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56,
   
7.      57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74,
   
8.      75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92,
   
9.      93, 94, 95, 96, 97, 98, 99] : int list
   

复制代码