2005/06/10

結局、遅延評価バージョンを書いてみた。

; lcar, lcdr, ltake は "Gauche リファレンスマニュアル" の例を流用
; http://www.shiro.dreamhost.com/scheme/gauche/man/gauche-refj_90.html#SEC94
(use srfi-1)

(define (lcar lis) ;; lazy car
(car (force lis)))

(define (lcdr lis) ;; lazy cdr
(cdr (force lis)))

(define (ltake lis n) ;; lazy take
(if (<= n 0) '() (cons (lcar lis) (ltake (lcdr lis) (- n 1)))))

(define (lfilter pred ls) ;; lazy filter. i know it's not cps.
(if (pred (lcar ls))
(cons (lcar ls) (delay (lfilter pred (lcdr ls))))
(lfilter pred (lcdr ls))))

(define (integers-above num)
(let mkls ((x num))
(delay (cons x (mkls (+ x 1))))))

(define primes
(let prime-list ((ls (integers-above 2)))
(cons (lcar ls)
(delay (prime-list (lfilter (lambda (x) (> (modulo x (lcar ls)) 0)) (lcdr ls)))))))

gosh> (ltake primes 25)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

お膳立てが多いけど、primes プロシージャに関しては Haskell バージョンと同等になったと思う。

No comments :