Lazy Evaluation and Streams

Racket: racket/stream and #lang lazy. Common Lisp: libraries like series and lazy-seq implementations. Streams model infinite data, signal processing, and separation of generation from consumption.

;; SICP streams: delay the tail
(define-syntax cons-stream
  (syntax-rules ()
    ((_ a b) (cons a (delay b)))))
(define (stream-car s) (car s))
(define (stream-cdr s) (force (cdr s)))
(define the-empty-stream '())
(define stream-null? null?)

(define (integers-from n) (cons-stream n (integers-from (+ n 1))))
(define naturals (integers-from 0))

(define (stream-take s n)
  (if (= n 0) '() (cons (stream-car s) (stream-take (stream-cdr s) (- n 1)))))
(define (stream-filter pred s)
  (if (pred (stream-car s))
      (cons-stream (stream-car s) (stream-filter pred (stream-cdr s)))
      (stream-filter pred (stream-cdr s))))
(define (stream-map f s) (cons-stream (f (stream-car s)) (stream-map f (stream-cdr s))))

(stream-take (stream-filter even? naturals) 5)    ; (0 2 4 6 8)

;; Sieve of Eratosthenes as a stream
(define (sieve s)
  (cons-stream (stream-car s)
               (sieve (stream-filter (lambda (x) (not (= 0 (remainder x (stream-car s)))))
                                     (stream-cdr s)))))
(stream-take (sieve (integers-from 2)) 10)        ; (2 3 5 7 11 13 17 19 23 29)

;; Clojure: lazy sequences are the default for map/filter/range/iterate
(def fibs (lazy-cat [0 1] (map + fibs (rest fibs))))
(take 10 fibs)                           ; (0 1 1 2 3 5 8 13 21 34)
(take 5 (filter even? (range)))          ; (0 2 4 6 8)