You are looking at historical revision 29275 of this page. It may differ significantly from its current revision.

Lazy lists

Lists in Scheme and Lisp are eager. Since the procedure calling regime in these languages is "Call by value", a list argument of a procedure call is completely constructed before the procedure is called. This is fine for small lists, but it excludes practically the chaining of procedure calls with large list arguments. On the other hand such a chaining is a tremendously powerful modularization technique, as demonstrated by purely functional languages like Haskell.

The traditional tools for implementation of lazy evaluation consist of the two Scheme primitives delay and force (cf. the classic "Structure and Interpretation of Computer Porgrams" by Abelson and Sussman, usually abbreveated "SICP"). But there is a better method as shown by Moritz Heidkamp in his lazy-Lst Module, which in turn is meant to replace the stream datatype in SRFI-41. Moritz' approach is inspired by the Lisp dialect Clojure, which also motivated the beautiful macros in his clojurian module. The fundamental idea is to store the structure of a lazy list in a record, but to realize this list only as much as needed. This way a large (even infinite) list can be created instantaneously without realizing it and will be realized only if and as much as used.

This module is based on Heidkamp's implementation with one essential addition: The length of the list is stored in the record and can thus be referenced without realizing the whole list. After all, some operations like reverse are only meaningful for finite lists, so one must know beforehand if a list is finite to avoid infinite loops.

But knowing the length of a list at the moment of its creation, lazy lists can replace ordinary lists as a datatype. And ordinary list operations can be replaced by lazy list operations. This is the reason for the other difference of this module with Moritz' lazy-Lst, a cosmetic difference: Lazy list operations are named with the same name as ordinary ones, only capitalized at the beginning. So Cons, Car, Cdr ... are the replacements of cons, car, cdr etc. Some operators have a different argument order, thow, so that the clojurian chaining macro ->> works well. The consistent argument order is as follows: procedure arguments appear first, lazy list arguments last. For example (Ref n Lst) replaces (list-ref Lst n), (Drop n Lst) replaces (list-tail Lst n), etc.

Storing the length in the list record has another advantage: I can and will use my own multi-methods library to wrap the routines by method calls, since methods check their arguments automatically and there effects as well. This allows to implement the routines proper without any defenses - this is done in the module %lazy-lists - and do all the wrapping in the lazy-lists module. In other words, both modules have exactly the same interface (with one exception: the documentation procedure lazy-lists in the latter). The routines of the former are imported into the latter with the prefix %, so that they can be used there unwrapped.

lazy-lists

[procedure] (lazy-lists)

returns a sorted list of all exported symbols. Additional information of each method can be supplied by calls of method-assumptions and method-effects.

make-lazy

[procedure] (Make-lazy len thunk)

lazy constructor. len is either a not-negative fixnum or #f for infinite Lists

Lazy

[syntax] (Lazy len xpr . xprs)

convenience wrapper to Make-lazy constructor, avoiding a thunk.

Nil

empty lazy list

List?

[procedure] (List? xpr)

lazy version of list?

List-finite?

[procedure] (List-finite? xpr)

is xpr a finite List?

List-infinite?

[procedure] (List-infinite? xpr)

is xpr an infinite List?

List-not-null?

[procedure] (List-not-null? xpr)

is xpr a non-empty List?

Lists-one-finite?

[procedure] (Lists-one-finite? . Lsts)

is Lsts a nonempty list of Lists, at least one of it beeing finite?

Length

[procedure] (Length Lst)

lazy version of length, returning a fixnum or #f

Cons

[procedure] (Cons var Lst)

lazy version of cons

Rest

[procedure] (Rest Lst)

lazy version of cdr

Cdr

[procedure] (Cdr Lst)

lazy version of cdr

First

[procedure] (First Lst)

lazy version of car

Car

[procedure] (Car Lst)

lazy version of car

Ref

[procedure] (Ref n Lst)

lazy version of list-ref with changed argument order, realizing the Lst argument upto n.

Null?

[procedure] (Null? Lst)

lazy version of null?

Zip

[procedure] (Zip Lst1 Lst2)

interleave two lazy lists, both might be infinite

Some?

[procedure] (Some? ok? Lst)

does some item of Lst fulfill ok?

Every?

[procedure] (Every? ok? Lst)

does every item of Lst fulfill ok?

Fold-right*

[procedure] (Fold-right* op base . Lsts)

create a lazy list of right folds changing order or List items

Fold-left*

[procedure] (Fold-left* op base . Lsts)

create a lazy list of left folds

Fold-right

[procedure] (Fold-right op base . Lsts)

lazy version of fold-right, one of the Lsts must be finite.

Fold-left

[procedure] (Fold-left op base . Lsts)

lazy version of fold-left, one of the Lsts must be finite.

Sieve

[procedure] (Sieve =? Lst)

sieve of Erathostenes with respect to =?

Split-with

[procedure] (Split-with ok? Lst)

split a finite lazy list at first index fulfilling ok?

Split-at

[procedure] (Split-at n Lst)

split a List at fixed position

List->vector

[procedure] (List->vector Lst)

transform a finite lazy list into a vector

vector->List

[procedure] (vector->List vec)

transform a vector into a finite lazy list

Sort

[procedure] (Sort <? Lst)

sort a finite lazy list with respect to <?

Merge

[procedure] (Merge <? Lst1 Lst2)

merge two sorted finite lazy lists with respect to <?

Sorted?

[procedure] (Sorted? <? Lst)

is the finite lazy lst sorted with respect to <?

Cycle

[procedure] (Cycle Lst)

create infinite List by cycling finite List Lst

Reverse*

[procedure] (Reverse* Lst)

List of successive reversed subLists

Reverse

[procedure] (Reverse Lst)

lazy version of reverse. Lst must be finite

Append

[procedure] (Append . Lsts)

lazy version of append. If one of the Lsts is infinite, it's the last one to be appended.

Iterate

[procedure] (Iterate proc x)

create infinite List by applying proc succesively to x

Repeatedly

[procedure] (Repeatedly thunk)

create infinite List of return values of thunk

Repeat

[procedure] (Repeat x)

create infinite List of x

input->List

[procedure] (input->List port read-proc)

transform input port into List with read-proc

For-each

[procedure] (For-each proc . Lsts)

lazy version of for-each. At least one of the Lsts must be finite. For-each terminates at its length.

Filter

[procedure] (Filter ok? Lst)

lazy version of filter

Map

[procedure] (Map proc . Lsts)

lazy version of map, terminates at the shortest Length.

Assoc

[procedure] (Assoc key aLst)

lazy version of assoq

Assv

[procedure] (Assv key aLst)

lazy version of assv

Assq

[procedure] (Assq key aLst)

lazy version of assq

Assp

[procedure] (Assp ok? aLst)

return #f or first pair, whose Car fulfills ok?

Equal?

[procedure] (Equal? Lst1 Lst2)

lazy version of equal?

Eqv?

[procedure] (Eqv? Lst1 Lst2)

lazy version of eqv?

Eq?

[procedure] (Eq? Lst1 Lst2)

lazy version of eq?

Equ?

[procedure] (Equ? =? Lst1 Lst2)

compare two Lists with predicate =?

Member

[procedure] (Member var Lst)

lazy version of member

Memv

[procedure] (Memv var Lst)

lazy version of memv

Memq

[procedure] (Memq var Lst)

lazy version of memq

Memp

[procedure] (Memp ok? Lst)

Tail of items not fulfilling ok?

Index

[procedure] (Index ok? Lst)

return index of first item fulfilling ok?

Drop-upto

[procedure] (Drop-upto ok? Lst)

Tail of items not fulfilling ok? Lst must be finite.

Take-upto

[procedure] (Take-upto ok? Lst)

List of head items fulfilling ok? Lst must be finite.

Drop

[procedure] (Drop n Lst)

lazy version of list-tail with changed argument order

Take

[procedure] (Take n Lst)

List of first n items of Lst

List

[procedure] (List . args)

lazy version of list. Constructs a finite List.

list->List

[procedure] (list->List lst)

transform ordinary list into finite lazy list

List->list

[procedure] (List->list Lst)

transform finite lazy into ordinary list

Realize

[procedure] (Realize Lst)

realize a finite List

Realized?

[procedure] (Realized? Lst)

Is Lst realized?

Primes

[procedure] (Primes)

lazy list of prime numbers

Cardinals

[procedure] (Cardinals)

lazy list of non negative integers

Interval

[procedure] (Interval from upto)

List of integers from (included) upto (excluded)

Usage

 
(require-library lazy-lists multi-methods)
(import lazy-lists methods)

Examples

 

(require-library lazy-lists multi-methods)
(import lazy-lists methods)

(define (cons-right var lst)
  (if (null? lst)
    (cons var lst)
    (cons (car lst) (cons-right var (cdr lst)))))

(define (Within eps Lst)
  (let loop ((Lst Lst))
    (let ((a (Ref 0 Lst)) (b (Ref 1 Lst)))
      (if (< (abs (- a b)) eps)
        b
        (loop (Rest Lst))))))

(define (Relative eps Lst)
  (let loop ((Lst Lst))
    (let ((a (Ref 0 Lst)) (b (Ref 1 Lst)))
      (if (<= (abs (/ a b)) (* (abs b) eps))
        b
        (loop (Rest Lst))))))

(define (Newton x) ; fixed point for square root
  (lambda (a) (/ (+ a (/ x a)) 2))) 

(define (Sums Lst) ; List of sums
  (letrec ((sums (Cons 0 (Map + Lst (Lazy (Length Lst) sums)))))
    (Rest sums)))

(define (First-five) (List 0 1 2 3 4))
(define (Fibs)
  (Append (List 0 1) (Lazy #f (Map + (Rest (Fibs)) (Fibs)))))

;; some tests
(Length (First-five)) ;-> 5
(Length (Rest (First-five))) ;-> 4
(Length (Rest (Cardinals))) ;-> #f
(Length (Take 5 (Cardinals))) ;-> 5
(Length (Cardinals)) ;-> #f
(Length (Drop 5 (Cardinals))) ;-> #f
(First (Drop 5 (Cardinals))) ;-> 5
(List->list (First-five)) ;-> '(0 1 2 3 4)
(List->list (Take 5 (Cardinals))) ;-> '(0 1 2 3 4)
(Length (Interval 2 10)) ;-> (- 10 2)
(List->list (Interval 2 10)) ;-> '(2 3 4 5 6 7 8 9)
(List->list (Interval 10 2)) ;-> '(10 9 8 7 6 5 4 3)
(receive (head index tail) (Split-with (cut = <> 3) (First-five))
	(cons (First tail) (List->list head))) ;-> '(3 0 1 2)
(receive (head index tail) (Split-with (cut = <> 5) (Take 10 (Cardinals)))
	(append (List->list tail) (List->list head))) ;-> '(5 6 7 8 9 0 1 2 3 4)
(Index (cut = <> 2) (First-five)) ;-> 2
(Index (cut = <> 20) (First-five)) ;-> 5
(List->list (Take-upto (cut = <> 5) (Take 10 (Cardinals))))
     ;-> '(0 1 2 3 4)
(Length (Take-upto (cut = <> 5) (Take 10 (Cardinals)))) ;-> 5
(Length (Drop-upto (cut = <> 5) (Take 10 (Cardinals)))) ;-> 5
(First (Drop-upto (cut = <> 5) (Take 10 (Cardinals)))) ;-> 5
(Length (Drop-upto (cut = <> 2) (First-five))) ;-> 3
(First (Drop-upto (cut = <> 2) (First-five))) ;-> 2
(List->list (Memp odd? (First-five))) ;-> '(1 2 3 4)
(List->list (Memv 5 (Take 10 (Cardinals)))) ;-> '(5 6 7 8 9)
(Assv 5 (Take 10 (Map (lambda (x) (list x x)) (Cardinals))))
  ;-> '(5 5)
(Assv 10 (Map (lambda (x) (list x x)) (First-five))) ;-> #f
(Equal? (Cardinals) (Cardinals)) ;-> #f
(Equal? (Cardinals) (First-five)) ;-> #f
(Equal? (First-five) (First-five)) ;-> #t
(Length (Take 10 (Cardinals))) ;-> 10
(List->list (Take 5 (Filter odd? (Drop 1 (Cardinals)))))
  ;-> '(1 3 5 7 9)
(Length (Cardinals)) ;-> #f
(List->list (Map add1 (First-five))) ;-> '(1 2 3 4 5)
(List->list (Map + (First-five) (Take 5 (Cardinals))))
  ;-> '(0 2 4 6 8)
(Length (Map + (Cardinals) (Cardinals))) ;-> #f
(Length (Filter odd? (First-five))) ;-> 2
(List->list (Filter odd? (First-five))) ;-> '(1 3)
(Length (Filter odd? (Cardinals))) ;-> #f
(Ref 20 (Sieve = (Zip (Cardinals) (Cardinals)))) ;-> 20
(List->list (Sieve = (Zip (First-five) (First-five))))
  ;-> '(0 1 2 3 4)
(Ref 25 (Cardinals)) ;-> 25
(Ref 2 (First-five)) ;-> 2
(List->list (Take 3 (Repeat #f))) ;-> '(#f #f #f)
(List->list (Take 3 (Repeatedly (lambda () 1))))
  ;-> '(1 1 1)
(List->list (Take 3 (Iterate add1 0))) ;-> '(0 1 2)
(Length (Iterate add1 0)) ;-> #f
(Length (Append (First-five) (First-five))) ;-> 10
(List->list  (Append (First-five) (First-five)))
  ;-> '(0 1 2 3 4 0 1 2 3 4)
(List->list (Take 12 (Append (First-five) (Cardinals))))
  ; -> '(0 1 2 3 4 0 1 2 3 4 5 6)
(Length (Append (First-five) (Cardinals))) ; -> #f
(List->list (Reverse (First-five))) ; -> '(4 3 2 1 0)
(List->list (Reverse (Take 5 (Cardinals)))) ; -> '(4 3 2 1 0)
(Length (Reverse (First-five))) ; -> 5
(Length (Reverse* (Cardinals))) ; -> #f
(List->list (Ref 5 (Reverse* (Cardinals)))) ; -> '(5 4 3 2 1 0)
(List->list (Take 10 (Cycle (First-five))))
  ; -> '(0 1 2 3 4 0 1 2 3 4)
(Length (Cycle (First-five))) ; -> #f
(List->list (Sort < (First-five))) ; -> '(0 1 2 3 4)
(Length (Sort < (First-five))) ; -> 5
(List->list (Sort < (List 3 1 0 2 4))) ; -> '(0 1 2 3 4)
(receive (head tail) (Split-at 5 (Cardinals))
	(cons (First tail) (List->list head)))
; -> '(5 0 1 2 3 4)
(receive (head tail) (Split-at 15 (Take 5 (Cardinals)))
	(append (List->list tail) (List->list head)))
; -> '(0 1 2 3 4)
(Fold-left + 0 (Take 5 (Cardinals))) ; -> 10
(Fold-left + 0 (First-five) (First-five)) ; -> 20
(Fold-left * 1 (List 1 2 3 4)) ; -> 24
(Fold-left cons '() (Take 5 (Cardinals)))
  ; -> '(((((() . 0) . 1) . 2) . 3) . 4)
(Ref 4 (Fold-left* cons '() (Cardinals)))
  ; -> '(((((() . 0) . 1) . 2) . 3) . 4)
(Fold-right + 0 (Take 5 (Cardinals))) ; -> 10
(Fold-right + 0 (First-five) (First-five)) ; -> 20
;; list
(Fold-right cons '() (First-five))
  ; -> '(0 1 2 3 4)
;; append
(Fold-right cons '(a b c) (First-five))
  ; -> '(0 1 2 3 4 a b c)
(Ref 4 (Fold-right* cons '() (Cardinals)))
  ; -> '(4 3 2 1 0)) ; note changed order
(Ref 4 (Fold-right* cons-right '() (Cardinals)))
  ; -> '(0 1 2 3 4)
(Ref 4 (Fold-right* cons '(a b c) (Cardinals)))
  ; -> '(4 3 2 1 0 a b c) ; note changed order
(Ref 4 (Fold-right* cons-right '(a b c) (Cardinals)))
  ; -> '(a b c 0 1 2 3 4)
(List->list (vector->List '#(0 1 2 3 4))) ; -> '(0 1 2 3 4)
(Null? (vector->List '#())) ; -> #t
(List->vector (Take 5 (Cardinals))) ; -> '#(0 1 2 3 4)
(List->vector (First-five)) ; -> '#(0 1 2 3 4)
(List->vector Nil) ; -> '#()
(Every? odd? (Take 15 (Filter odd? (Cardinals)))) ; -> #t
(Every? odd? (Take 15 (Cardinals))) ; -> #f
(Every? odd? Nil) ; -> #t
(Some? odd? Nil) ; -> #f
(Some? odd? (Take 5 (Filter even? (Cardinals)))) ; -> #f
(Some? odd? (First-five)) ; -> #t
(Length (Zip (Cardinals) (First-five))) ; -> #f
(Length (Zip (First-five) (Cardinals))) ; -> #f
(Length (Zip (Cardinals) (Cardinals))) ; -> #f
(Length (Zip (First-five) (First-five))) ; -> 10
(Eqv? (Take 14 (Zip (Cardinals) (First-five)))
      (List 0 0 1 1 2 2 3 3 4 4 5 6 7 8)) ; -> #t
(Eqv? (Take 14 (Zip (Cardinals) (Cardinals)))
      (List 0 0 1 1 2 2 3 3 4 4 5 5 6 6)) ; -> #t
(Eqv? (Zip (First-five) (First-five))
      (List 0 0 1 1 2 2 3 3 4 4)) ; -> #t
(Ref 50 (Primes)) ; -> 233
(Eqv? (Take 5 (Primes)) (List 2 3 5 7 11)) ; -> #t
(Eqv? (Take 10 (Fibs)) (List  0 1 1 2 3 5 8 13 21 34)) ; -> #t
;; compute square root
(let ((eps 0.000001))
  (< (abs (- (sqrt 2) (Within eps (Iterate (Newton 2) 2)))) eps)) ; -> #t
(List->list (Sums (First-five))) ; -> '(0 1 3 6 10)

Author

Juergen Lorenz

Initial version

Aug 1, 2012

Updated

Jun 28, 2013

License

 
Copyright (c) 2012-2013, Juergen Lorenz, Moritz Heidkamp
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of the author nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Version History
0.4
List-finite? corrected, List-infinite? and Realize added
0.3
dependency changed from contracts to multi-methods, additional predicates introduced
0.2
dependency on clojurian removed
0.1
initial import