## TOC »

- Lazy lists
- lazy-lists
- make-lazy
- Lazy
- Nil
- List?
- List-finite?
- List-infinite?
- List-not-null?
- Lists-one-finite?
- Admissible?
- Length
- Cons
- Rest
- Cdr
- First
- Car
- At
- Ref
- Null?
- Zip
- Unzip
- Some?
- Every?
- Fold-right*
- Fold-left*
- Fold-right
- Fold-left
- Sieve
- Split-with
- Split-at
- List->vector
- vector->List
- Sort
- Merge
- Sorted?
- Cycle
- Reverse*
- Reverse
- Append
- Range
- Iterate
- Repeatedly
- Repeat
- input->List
- For-each
- Filter
- Remp
- Remove
- Remq
- Remv
- Map
- Assoc
- Assv
- Assq
- Assp
- Equal?
- Eqv?
- Eq?
- Equ?
- Member
- Memv
- Memq
- Memp
- Count-while
- Drop-while
- Take-while
- Drop
- Take
- List
- list->List
- List->list
- Realize
- Realized?
- Primes
- Cardinals
- assume-in

- Usage
- Examples
- Author
- Initial version
- Updated
- License
- Version History

## 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 Miranda or Haskell.

The traditional tools for the 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-seq 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 type, but to realize resulting record only as much as needed. This way a large (even infinite) list can be created instantaneously without realizing it and it will be realized only if and as much as used.

This module is based on Heidkamp's implementation with one essential addition: A boolean named finite? is stored in the record type and can thus be referenced without realizing the resulting record. 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 finiteness 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-seq, a cosmetic difference: Lazy list operations are named with the same name as ordinary ones, only capitalized at the beginning. So accessors Car, Cdr ... are the replacements of 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 (At n Lst) replaces (list-ref lst n), (Drop n Lst) replaces (list-tail lst n), etc. But (List-ref Lst n) and (List-tail Lst n) is still there for convenience, but discouraged.

Storing the finiteness in the list record type has another advantage: One can check finiteness of a lazy list argument at the start of a routine. One could use assert for that, but that would mean to always do all checks provided you don't compile in unsafe mode, which makes all code unsafe. So I provided another macro instead, assume-in, which does any error-checking only if a special feature, assumptions-checked, is registerd.

#### lazy-lists

`lazy-lists``#!optional``sym`proceduredocumentation procedure: returns a sorted list of all exported symbols with no argument or the signature of sym when called with argument.

#### make-lazy

`Make-lazy``finite?``thunk`procedurelazy constructor.

#### Lazy

`(Lazy finite? xpr . xprs)`syntaxconvenience wrapper to Make-lazy constructor, avoiding a thunk.

#### Nil

empty lazy list

#### List?

`List?``xpr`procedurelazy version of list?

#### List-finite?

`List-finite?``xpr`procedureis xpr a finite List?

#### List-infinite?

`List-infinite?``xpr`procedureis xpr an infinite List?

#### List-not-null?

`List-not-null?``xpr`procedureis xpr a non-empty List?

#### Lists-one-finite?

`Lists-one-finite?``#!rest``Lsts`procedureis Lsts a nonempty list of Lists, at least one of it being finite?

#### Admissible?

`Admissible?``n``Lst`procedurechecks if n is an admissible index for the lazy-list Lst. Deprecated, makes finite Lists eager. Moreover traverses a List twice, when used in a check

#### Length

`Length``Lst`procedurelazy version of length, returning a fixnum or #f

#### Cons

`Cons``var``Lst`procedurelazy version of cons. Deprecated, use (Lazy finite? (cons var Lst)) instead

#### Rest

`Rest``Lst`procedurelazy version of cdr

#### Cdr

`Cdr``Lst`procedurelazy version of cdr

#### First

`First``Lst`procedurelazy version of car

#### Car

`Car``Lst`procedurelazy version of car

#### At

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

#### Ref

`Ref``n``Lst`procedurealias for At, deprecated.

#### Null?

`Null?``Lst`procedurelazy version of null?

#### Zip

`Zip``Lst1``Lst2`procedureinterleave two lazy lists, both might be infinite

#### Unzip

`Unzip``Lst`proceduresplits a lazy list in two by alternatingly putting the items of Lst into the first or the second result lazy list.

#### Some?

`Some?``ok?``Lst`proceduredoes some item of Lst fulfill ok?

#### Every?

`Every?``ok?``Lst`proceduredoes every item of Lst fulfill ok?

#### Fold-right*

`Fold-right*``op``base``Lst``#!rest``Lsts`procedurecreate a lazy list of right folds changing order or List items

#### Fold-left*

`Fold-left*``op``base``Lst``#!rest``Lsts`procedurecreate a lazy list of left folds

#### Fold-right

`Fold-right``op``base``Lst``#!rest``Lsts`procedurelazy version of fold-right, one of the Lsts must be finite.

#### Fold-left

`Fold-left``op``base``Lst``#!rest``Lsts`procedurelazy version of fold-left, one of the Lsts must be finite.

#### Sieve

`Sieve``=?``Lst`proceduresieve of Erathostenes with respect to =?

#### Split-with

`Split-with``ok?``Lst`proceduresplit a finite lazy list at first index not fulfilling ok?

#### Split-at

`Split-at``n``Lst`proceduresplit a List at fixed position

#### List->vector

`List->vector``Lst`proceduretransform a finite lazy list into a vector

#### vector->List

`vector->List``vec`proceduretransform a vector into a finite lazy list

#### Sort

`Sort``<?``Lst`proceduresort a finite lazy list with respect to <?

#### Merge

`Merge``<?``Lst1``Lst2`proceduremerge two sorted finite lazy lists with respect to <?

#### Sorted?

`Sorted?``<?``Lst`procedureis the finite lazy lst sorted with respect to <?

#### Cycle

`(Cycle [n] Lst)`procedurecreate finite List of Length n or infinite List by cycling finite List Lst

#### Reverse*

`Reverse*``Lst`procedureList of successive reversed subLists

#### Reverse

`Reverse``Lst`procedurelazy version of reverse. Lst must be finite

#### Append

`Append``#!rest``Lsts`procedurelazy version of append. If one of the Lsts is infinite, it's the last one to be appended.

#### Range

`(Range [from] upto [step])`procedureList of integers from (included) upto (excluded) with step

#### Iterate

`Iterate``fn``x``#!optional``times`procedurecreate finite List of Length times or infinite List by applying fn succesively to x

#### Repeatedly

`Repeatedly``thunk``#!optional``times`procedurecreate finite List of Length times or infinite List of return values of thunk

#### Repeat

`Repeat``x``#!optional``times`procedurecreate finite List of Length times or infinite List of x

#### input->List

`input->List``port``read-proc`proceduretransform input port into List with read-proc

#### For-each

`For-each``proc``#!rest``Lsts`procedurelazy version of for-each. At least one of the Lsts must be finite. For-each terminates at its length.

#### Filter

`Filter``ok?``Lst`procedurelazy version of filter

#### Remp

`Remp``ok?``Lst`procedureremoves all items which pass the ok? predicate.

#### Remove

`Remove``item``Lst`procedureremoves all items form Lst which are equal? to item.

#### Remq

`Remq``item``Lst`procedureremoves all items form Lst which are eq? to item.

#### Remv

`Remv``item``Lst`procedureremoves all items form Lst which are eqv? to item.

#### Map

`Map``proc``#!rest``Lsts`procedurelazy version of map, terminates at the shortest Length.

#### Assoc

`Assoc``key``aLst`procedurelazy version of assoq

#### Assv

`Assv``key``aLst`procedurelazy version of assv

#### Assq

`Assq``key``aLst`procedurelazy version of assq

#### Assp

`Assp``ok?``aLst`procedurereturn #f or first pair, whose Car fulfills ok?

#### Equal?

`Equal?``Lst1``Lst2`procedurelazy version of equal?

#### Eqv?

`Eqv?``Lst1``Lst2`procedurelazy version of eqv?

#### Eq?

`Eq?``Lst1``Lst2`procedurelazy version of eq?

#### Equ?

`Equ?``=?``Lst1``Lst2`procedurecompare two Lists with predicate =?

#### Member

`Member``var``Lst`procedurelazy version of member

#### Memv

`Memv``var``Lst`procedurelazy version of memv

#### Memq

`Memq``var``Lst`procedurelazy version of memq

#### Memp

`Memp``ok?``Lst`procedureTail of items not fulfilling ok?

#### Count-while

`Count-while``ok?``Lst`procedurereturn index of first item not fulfilling ok?

#### Drop-while

`Drop-while``ok?``Lst`procedureTail of items not fulfilling ok? Lst must be finite.

#### Take-while

`Take-while``ok?``Lst`procedureList of items fulfilling ok? Lst must be finite.

#### Drop

`Drop``n``Lst`procedurelazy version of list-tail with changed argument order

#### Take

`Take``n``Lst`procedureList of first n items of Lst

#### List

`List``#!rest``args`procedurelazy version of list. Constructs a finite List.

#### list->List

`list->List``lst`proceduretransform ordinary list into finite lazy list

#### List->list

`List->list``Lst`proceduretransform finite lazy into ordinary list

#### Realize

`Realize``Lst`procedurerealize a finite List

#### Realized?

`Realized?``Lst`procedureIs Lst realized?

#### Primes

`Primes`procedurelazy list of prime numbers

#### Cardinals

`Cardinals`procedurelazy list of non negative integers

#### assume-in

`(assume-in sym test . tests)`syntaxChecks if all the assumptions test ... in the routine with name sym are valid and provides a meaningful error-message otherwise, provided the feature assumptions-checked is registered. Checks nothing if the feature is not registered.

## Usage

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

## Examples

(require-library lazy-lists) (import lazy-lists) (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 (At 0 Lst)) (b (At 1 Lst))) (if (< (abs (- a b)) eps) b (loop (Rest Lst)))))) (define (Relative eps Lst) (let loop ((Lst Lst)) (let ((a (At 0 Lst)) (b (At 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 (let loop ((n 1)) (Lazy #f (cons (apply + (List->list (Take n Lst))) (loop (fx+ n 1)))))) (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 (Range 2 10)) ;-> (- 10 2) (List->list (Range 2 10)) ;-> '(2 3 4 5 6 7 8 9) (List->list (Range 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-while (cut < <> 5) (Take 10 (Cardinals)))) ;-> '(0 1 2 3 4) (Length (Take-while (cut < <> 5) (Take 10 (Cardinals)))) ;-> 5 (Length (Drop-while (cut < <> 5) (Take 10 (Cardinals)))) ;-> 5 (First (Drop-while (cut < <> 5) (Take 10 (Cardinals)))) ;-> 5 (Length (Drop-while (cut < <> 2) (First-five))) ;-> 3 (First (Drop-while (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 (At 20 (Sieve = (Zip (Cardinals) (Cardinals)))) ;-> 20 (List->list (Sieve = (Zip (First-five) (First-five)))) ;-> '(0 1 2 3 4) (At 25 (Cardinals)) ;-> 25 (At 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 (At 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) (At 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) (At 4 (Fold-right* cons '() (Cardinals))) ; -> '(4 3 2 1 0)) ; note changed order (At 4 (Fold-right* cons-right '() (Cardinals))) ; -> '(0 1 2 3 4) (At 4 (Fold-right* cons '(a b c) (Cardinals))) ; -> '(4 3 2 1 0 a b c) ; note changed order (At 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 (At 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 (Take 5 (Cardinals)))) ; -> '(0 1 3 6 10)

## Author

## Initial version

Aug 1, 2012

## Updated

Mar 03, 2017

## License

Copyright (c) 2012-2017, Juergen Lorenz 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.9
- replaced length slot with finite? slot to keep lazyness of finite lists
- 0.8.1
- fixed bug in documentation procedure lazy-lists
- 0.8
- new procedures lazy-lists Unzip Remp Remove Remq Remv
- 0.7
- assumptions checked with assume-in
- 0.6
- dependency on methods removed
- 0.5.2
- tests updated
- 0.5.1
- tests updated
- 0.5
- Repeat(edly), Iterate, Cycle with an optinal arg, Split-with semantics changed, ...-upto changed to ...-while
- 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