Thursday, April 06, 2006


Lazy Lists

After much pondering I finally sat down and wrote some λ-expressions for infinite lists of integers, factorials, and Fibonacci numbers - it was a fun exercise, and didn't take long. A fundamental requirement I had was that the standard list operators (car and cdr) could be applied to both normal lists (constructed by cons) and the infinite lists, and not have to create separate stream-car and stream-cdr operators (as is done in Scheme). Before embarking on the exercise I thought this requirement would cause some difficulty, but after starting it became apparent that with lazy evaluation it was a complete furphy. I think that I'm beginning to develop a taste for laziness, at least when comes to evaluation of expressions!

Below are the expressions I came up with (written in Elle). The use of the paradoxical operator Y makes the expressions look more complicated than they really are, but the use of recursion is essential in obtaining the infinite list behaviour.

(define car (lambda(p)(p(lambda(h t)h))))
(define cdr (lambda(p)(p(lambda(h t)t))))
(define Y(lambda (f)(lambda(x)f(x x))(lambda(x)f(x x))))
(define integers (Y (lambda (f n p) p n (f (+ n 1))) 0))
(define factorial (Y (lambda (f n v p) p v (f (+ n 1) (* v n))) 1 1))
(define fibonacci (Y (lambda (f m n p) p n (f n (+ m n))) 0 1))
You might like to verify the following identities:
(car integers) -> 1
(car (cdr integers)) -> 2
(car (cdr (cdr integers))) -> 3
(car (cdr (cdr factorial))) -> 6
(car (cdr (cdr (cdr (cdr fibonacci))))) -> 5

This page is powered by Blogger. Isn't yours?