From oleg@pobox.com Wed Dec 23 15:01:28 1998
From: oleg@pobox.com
Subject: Lazy Fibonacci Scheme
Date: Wed, 23 Dec 1998 23:02:36 GMT
Reply-To: oleg@pobox.com
Keywords: lazy evaluation, delay, stream, Haskell, Scheme
Newsgroups: comp.lang.scheme,comp.lang.functional
Organization: Deja News - The Leader in Internet Discussion
References: <75mhnf$un4$1@newsfeeds.rpi.edu>
Summary: Fibonacci sequence as a lazy Scheme "stream"
X-Article-Creation-Date: Wed Dec 23 23:02:36 1998 GMT
X-Http-User-Agent: Mozilla/4.08 (Macintosh; I; PPC, Nav)
Content-Length: 3502
Status: RO
Although (potentially infinite) streams are not built in into Scheme,
they are rather easily emulated, as this article tries to show. It
presents a "stream"-lined Fibonacci sequence re-written from a
previously published Haskell code, which was beautiful indeed. The
difference between these two particular snippets is in the number of
parentheses.
Let me first give a less generic but more optimal solution:
; which is actually a 'map' over two lazy lists ("streams")
(define (pointwise f L1 L2)
(let ((L1 (force L1)) (L2 (force L2)))
(cond
((null? L1) '())
((null? L2) '())
(else (cons (f (car L1) (car L2))
(delay (pointwise f (cdr L1) (cdr L2))))))))
(define fibs (cons 1 (cons 1 (delay (pointwise + fibs (cdr fibs))))))
; Give the n-th element of a lazy list
(define (n-th L n)
(let ((L (force L)))
(if (positive? n) (n-th (cdr L) (- n 1))
(car L))))
(n-th fibs 0) => 1
(n-th fibs 1) => 1
(n-th fibs 2) => 2
(n-th fibs 3) => 3
(n-th fibs 4) => 5
(do ((i 0 (+ 1 i))) ((> i 10) (newline))
(display (n-th fibs i)) (display #\space))
1 1 2 3 5 8 13 21 34 55 89
(time (n-th fibs 300))
31 ms real time
20 ms cpu time (20 user, 0 system)
no collections
100744 bytes allocated
no minor faults
no major faults
359579325206583560961765665172189099052367214309267232255589801
(time (n-th fibs 300))
13 ms real time
10 ms cpu time (10 user, 0 system)
no collections
26488 bytes allocated
no minor faults
no major faults
359579325206583560961765665172189099052367214309267232255589801
The second time around was sure faster. Laziness does pay off!
Let me spice it up, with macros:
; Lazy cons
(define-macro (l-cons x y) `(cons ,x (delay ,y)))
; Eager null? car and cdr
; Note, Gambit's null? car and cdr force their arguments
; by default. The following macros can be regular
; functions as well.
(define-macro (e-null? x) `(null? (force ,x)))
(define-macro (e-car x) `(car (force ,x)))
(define-macro (e-cdr x) `(cdr (force ,x)))
I'll write lazy Scheme code right beneath the Haskell code from the
original article by Art Duncan,
http://x7.dejanews.com/getdoc.xp?AN=424665065
>Assume we already have a lazy function called 'pointwise' defined by
>
> pointwise f [] _ = []
> pointwise f _ [] = []
> pointwise f (x:xs) (y:ys) = f x y : pointwise f xs ys
(define (pointwise f L1 L2)
(cond
((e-null? L1) '())
((e-null? L2) '())
(else (l-cons (f (e-car L1) (e-car L2))
(pointwise f (e-cdr L1) (e-cdr L2))))))
>We can then define the fibonacci numbers as
> fibs = 1 : 1 : pointwise (+) fibs (tail fibs)
(define fibs (l-cons 1 (l-cons 1 (pointwise + fibs (e-cdr fibs)))
I think a regular cdr would've sufficed too.
(define (n-th L n)
(if (positive? n) (n-th (e-cdr L) (- n 1)) (e-car L)))
(do ((i 0 (+ 1 i))) ((> i 10) (newline))
(display (n-th fibs i)) (display #\space))
1 1 2 3 5 8 13 21 34 55 89
The following short article gives another example: a lazy list
flattener.
http://pobox.com/~oleg/ftp/Scheme/misc.html#lazy-flattener
This flattener is not only properly tail recursive, it's
tail-infective as well: it works like a virus. The flattener can
handle even circular "lists" - a really infinite data structure. I
don't quite comprehend how the code does this, yet it somehow works.