- PFDS指Purely Functional Data Structure。
- 算是给N年前没能坚持看完Chris Okasaki的论文的自己一个交代。
- 这个是书的PFDS的笔记,不是论文的笔记。
- 会包括书里没有的东西。
Haskell是默认惰性求值的。Standard ML不是,F#不是,Racket也不是:他们是在每一次function application时就对参数求值,得到结果后再作为参数。这个对应的概念不叫勤快求值,叫strict evaluation。
这个:
(some-actions (+ 1 2) (* 3 4))实际上(至少在racket里)会变成:
(some-actions 3 12)然后再来做some-actions。
推迟求值似乎很简单,包一层lambda就好了:
(define (delay x) (λ () x))但是这是不够的:刚刚已经说过了,strict的语言里会先evaluate参数,于是你试图这样:
(delay (+ 3 4))实际上会变成这样:
(delay 7)然后才是:
(λ () 7)那要怎么办呢?我们需要直接将(delay (+ 3 7))变成(λ () (+ 3 7))。对于这种问题,lisp系里有宏:
#| tested under racket 6.11. |# (define-syntax delay (syntax-rules () [(delay x) (λ () x)]))force就没那么多顾虑了:
(define (force x) (x))但是在这个宏里我们没有做memoization,force一次求值就会进行一次。那么要怎么办呢?放进临时变量就好了:
(define-syntax $ (syntax-rules () [($ x) (λ () (let ((evaluated? #f) (evaluated-res (void))) (if evaluated? evaluated-res (begin (set! evaluated? #t) (set! evaluated-res x) evaluated-res))))]))
($ evaluated?)我们似乎会得到#t,因为展开之后是这样的:
(λ () (let ((evaluated? #f) (evaluated-res (void))) (if evaluated? evaluated-res (begin (set! evaluated? #t) (set! evaluated-res evaluated?) evaluated-res))))实际上(至少在racket里)是不会的,它只会返回当前环境里的evaluated?的值,或者在没有绑定值的时候报错。racket应该做了一点用来避免不小心访问到这种binding的工作,具体情况我不懂racket所以不熟。(正色)
那么lazy能用来做什么呢?至少、目前为止我所知道的大致上有两种:
fib = 0 : 1 : zipWith (+) fib (tail fib)这个是fibonacci数列。主要原理是这样:
fib | 0 1 1 2 3 5 8 ... tail fib 0 | 1 1 2 3 5 8 ... result 0 1 | 1 2 3 5 8 13 ...当你需要fib的第3项的时候,zipWith就会把fib和tail fib展开一部分,然后取出(正好是)fib的第1项和第2项,然后加起来,如此类推。那么假如展开到需要用到fib的第3项时(比如说求第5项)要怎么办呢?不怎么办,因为在此之前第3项(一定)已经计算过了,直接用就是了。
(delay (list 1 2 3 4 5))而是:
(delay (cons 1 (delay (cons 2 (delay (cons 3 (delay (cons 4 (delay (cons 5 (delay (list))))))))))))这样才会是“一点一点地”展开:
(force (delay (cons 1 (delay (cons 2 (delay (cons 3 (delay (list))))))))) ;; ==> '(1 . #<promise>)(racket自带的delay的结果是一个叫做promise的东西;是什么现在可以不用管)
(force (delay (list 1 2 3 4 5))) ;; ==> '(1 2 3 4 5)那么,要append两个lazy list的话要怎么办呢?如果不lazy的话,我们可以这么做:
(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y))))假如涉及到lazy,那么就要连这个if也要delay掉,因为可能连append操作本身都不会执行:
(let ((appended-list (append '(1 2 3) '(4 5)))) (displayln "hello world!"))按照lazy的语义,这个'(1 2 3)和'(4 5)永远都不会被append,因为它们append的结果根本就不会被用到。
(define (lazyAppend a b) (delay (let ((forced (force a))) (if (null? forced) (force b) (cons (car forced) (lazyAppend (cdr forced) b))))))具体原因是这样:
(define (lazyTake n s) (delay (if (= n 0) '() (let ((forced (force s))) (if (null? forced) '() (cons (car forced) (lazyTake (- n 1) (cdr forced))))))))但是drop则有些不同:drop的时候我们不cons东西,我们只要将stream的前n个元素去掉,保留本来就已经被封装成stream的剩下的部分就好了;而且我们肯定不会「一点一点地」drop:如果我们需要用到一个drop过的stream,我们肯定会认为前面的元素早已经被drop了。但是我们仍然需要把drop这个操作本身delay掉,因为drop本身也有可能是不进行的:
(define (lazyDrop n s) (define (lazyDrop_ n s) (if (= n 0) s (let ((forced (force s))) (if (null? forced) '() (lazyDrop_ (- n 1) (cdr forced)))))) (delay (lazyDrop_ n s)))reverse稍微有些不一样:我们需要cons东西了。
(define (lazyReverse l) (define (reverse_ l r) (let ((forced (force l))) (if (null? forced) r (reverse_ (cdr l) (delay (cons (car forced) r)))))) (reverse_ l (delay '())))在这里我们只是build了一个stream;reverse_本身是一次到位的,因为在需要时会需要一个一次到位的结果。