SRFI-127: Lazy Sequences

Lazy sequences (or lseqs, pronounced "ell-seeks") are a generalization of lists. In particular, an lseq is either a proper list or a dotted list whose last cdr is a SRFI 121 generator. A generator is a procedure that can be invoked with no arguments in order to lazily supply additional elements of the lseq. When a generator has no more elements to return, it returns an end-of-file object. Consequently, lazy sequences cannot reliably contain end-of-file objects.

This SRFI provides a set of procedures suitable for operating on lazy sequences based on SRFI-1.

SRFI-127: Lazy Sequences
SRFI Description
Lazy Sequences
Repository
Version History
License

SRFI Description

For a full description of this SRFI, see the full SRFI document. This documentation covers the API only.

Lazy Sequences

The templates given below obey the following conventions for procedure formals:

lseq: A lazy sequence
x, y, a, b: Any value
object, value: Any value
n, i: A natural number (an integer >= 0)
proc: A procedure
pred: A procedure whose return value is treated as a boolean
generator: A procedure with no arguments that returns a sequence of values
=: A boolean procedure taking two arguments

To interpret the examples, pretend that they are executed on a Scheme that prints lazy sequences with the syntax of lists, truncating them when they get too long.

Constructors

Every list constructor procedure is also an lseq constructor procedure. The procedure generator->lseq constructs an lseq based on the values of a generator. In order to prepend a value to an lseq, simply use cons; to prepend more than one value, use SRFI 1's cons*.

[procedure] (generator->lseq generator)

Returns an lseq whose elements are the values generated by generator. The exact behavior is as follows:

generator is invoked with no arguments to produce an object obj.
If obj is an end-of-file object, the empty list is returned.
Otherwise, a newly allocated pair whose car is obj and whose cdr is generator is returned.

(generator->lseq (make-iota-generator +inf.0 1)) ;=> (1 2 3 ...)

Predicates

[procedure] (lseq? x)

Returns #t if x is an lseq. This procedure may also return #t if x is an improper list whose last cdr is a procedure that requires arguments, since there is no portable way to examine a procedure to determine how many arguments it requires. Otherwise it returns #f.

[procedure] (lseq=? elt=? lseq1 lseq2)

Determines lseq equality, given an element-equality procedure. Two lseqs are equal if they are of the same length, and their corresponding elements are equal, as determined by elt=?. When elt=? is called, its first argument is always from lseq1 and its second argument is from lseq2.

The dynamic order in which the elt=? procedure is applied to pairs of elements is not specified.

The elt=? procedure must be consistent with eq?. This implies that two lseqs which are eq? are always lseq=?, as well; implementations may exploit this fact to "short-cut" the element-by-element equality tests.

Selectors

[procedure] (lseq-car lseq)
[procedure] (lseq-first lseq)

These procedures are synonymous. They return the first element of lseq. They are included for completeness, as they are the same as car. It is an error to apply them to an empty lseq.

[procedure] (lseq-cdr lseq)
[procedure] (lseq-rest lseq)

These procedures are synonymous. They return an lseq with the contents of lseq except for the first element. The exact behavior is as follows:

If lseq is a pair whose cdr is a procedure, then the procedure is invoked with no arguments to produce an object obj.
- If obj is an end-of-file object, then the cdr of lseq is set to the empty list, which is returned.
- If obj is any other object, then a new pair is allocated whose car is obj and whose cdr is the cdr of lseq (i.e. the procedure). The cdr of lseq is set to the newly allocated pair, which is returned.
If lseq is a pair whose cdr is not a procedure, then the cdr is returned.
If lseq is not a pair, it is an error.

Implementations that inline cdr are advised to inline lseq-cdr if possible.

[procedure] (lseq-ref lseq i)

Returns the ith element of lseq. (This is the same as (lseq-first (lseq-drop lseq i))). It is an error if i >= n, where n is the length of lseq.

(lseq-ref '(a b c d) 2) ;=> c

[procedure] (lseq-take lseq i)
[procedure] (lseq-drop lseq i)

lseq-take lazily returns the first i elements of lseq. lseq-drop returns all but the first i elements of lseq.

(lseq-take '(a b c d e)  2) ;=> (a b)
(lseq-drop '(a b c d e)  2) ;=> (c d e)

lseq-drop is exactly equivalent to performing i lseq-rest operations on lseq.

The Whole Lazy Sequence

[procedure] (lseq-realize lseq)

Repeatedly applies lseq-cdr to lseq until its generator (if there is one) has been exhausted, and returns lseq, which is now guaranteed to be a proper list. This procedure can be called on an arbitrary lseq before passing it to a procedure which only accepts lists. However, if the generator never returns an end-of-file object, lseq-realize will never return.

[procedure] (lseq->generator lseq)

Returns a generator which when invoked will return all the elements of lseq, including any that have not yet been realized.

[procedure] (lseq-length lseq)

Returns the length of its argument, which is the non-negative integer n such that lseq-rest applied n times to the lseq produces an empty lseq. lseq must be finite, or this procedure will not return.

[procedure] (lseq-append lseq ...)

Returns an lseq that lazily contains all the elements of all the lseqs in order.

[procedure] (lseq-zip lseq1 lseq2 ...)

If lseq-zip is passed n lseqs, it lazily returns an lseq each element of which is an n-element list comprised of the corresponding elements from the lseqs. If any of the lseqs are finite in length, the result is as long as the shortest lseq.

(lseq-zip '(one two three)
          (generator->lseq (make-iota-generator +inf.0 1 1))
          (generator->lseq (make-repeating-generator) '(odd even))))
 ;=> ((one 1 odd) (two 2 even) (three 3 odd))

(lseq-zip '(1 2 3)) ;=> ((1) (2) (3))

Mapping and Filtering

[procedure] (lseq-map proc lseq1 lseq2 ...)

The lseq-map procedure lazily applies proc element-wise to the corresponding elements of the lseqs, where proc is a procedure taking as many arguments as there are lseqs and returning a single value, and returns an lseq of the results in order. The dynamic order in which proc is applied to the elements of the lseqs is unspecified.

(lseq-map
 (lambda (x) (lseq-car (lseq-cdr x)))
 '((a b) (d e) (g h)))
 ;=>  (b e h)

(lseq-map (lambda (n) (expt n n))
 (make-iota-generator +inf.0 1 1)
 ;=> (1 4 27 256 3125 ...)

 (lseq-map + '(1 2 3) '(4 5 6)) =>  (5 7 9)

 (let ((count 0))
  (lseq-map (lambda (ignored)
             (set! count (+ count 1))
             count)
   '(a b)))
 ;=>  (1 2) or (2 1)

[procedure] (lseq-for-each proc lseq1 lseq2 ...)

The arguments to lseq-for-each are like the arguments to lseq-map, but lseq-for-each calls proc for its side effects rather than for its values. Unlike lseq-map, lseq-for-each is guaranteed to call proc on the elements of the lseqs in order from the first element(s) to the last, and the value returned by lseq-for-each is unspecified. If none of the lseqs are finite, lseq-for-each never returns.

(let ((v (make-vector 5)))
  (lseq-for-each (let ((count 0))
                   (lambda (i)
                     (vector-set! v count (* i i))
                     (set! count (+ count 1))))
                 '(0 1 2 3 4))
  v)
 ;=> (#0 1 2 3 4)

[procedure] (lseq-filter pred lseq)
[procedure] (lseq-remove pred lseq)

The procedure lseq-filter lazily returns an lseq that contains only the elements of lseq that satisfy pred.

The procedure lseq-remove is the same as lseq-filter, except that it returns elements that do not satisfy pred. These procedures are guaranteed to call pred on the elements of the lseqs in sequence order.

(lseq-filter odd? (generator->lseq (make-range-generator 1 5)))
 ;=>  (1 3)

(lseq-remove odd? (generator->lseq (make-range-generator 1 5)))
 ;=>  (2 4)

Searching

The following procedures all search lseqs for the leftmost element satisfying some criterion.

[procedure] (lseq-find pred lseq)

Return the first element of lseq that satisfies predicate pred, or #f if no element does. It cannot reliably be applied to lseqs that include #f as an element; use lseq-find-tail instead. The predicate is guaranteed to be evaluated on the elements of lseq in sequence order, and only as often as necessary.

(lseq-find even? '(3 1 4 1 5 9 2 6)) ;=> 4

[procedure] (lseq-find-tail pred lseq)

Returns the longest tail of lseq whose first element satisfies pred, or #f if no element does. The predicate is guaranteed to be evaluated on the elements of lseq in sequence order, and only as often as necessary.

lseq-find-tail can be viewed as a general-predicate variant of the lseq-member function.

Examples:

(lseq-find-tail even? '(3 1 37 -8 -5 0 0)) ;=> (-8 -5 0 0)
(lseq-find-tail even? '(3 1 37 -5))        ;=> #f

;; equivalent to (lseq-member elt lseq)
(lseq-find-tail (lambda (elt) (equal? x elt)) lseq)

[procedure] (lseq-take-while pred lseq)

Lazily returns the longest initial prefix of lseq whose elements all satisfy the predicate pred.

(lseq-take-while even? '(2 18 3 10 22 9)) ;=> (2 18)

[procedure] (lseq-drop-while pred lseq)

Drops the longest initial prefix of lseq whose elements all satisfy the predicate pred, and returns the rest of the lseq.

(lseq-drop-while even? '(2 18 3 10 22 9)) ;=> (3 10 22 9)

Note that lseq-drop-while is essentially lseq-find-tail where the sense of the predicate is inverted: lseq-find-tail searches until it finds an element satisfying the predicate; lseq-drop-while searches until it finds an element that doesn't satisfy the predicate.

[procedure] (lseq-any pred lseq1 lseq2 ...)

Applies pred to successive elements of the lseqs, returning true if pred returns true on any application. If an application returns a true value, lseq-any immediately returns that value. Otherwise, it iterates until a true value is produced or one of the lseqs runs out of values; in the latter case, lseq-any returns #f. It is an error if pred does not accept the same number of arguments as there are lseqs and return a boolean result.

Note the difference between lseq-find and lseq-any -- lseq-find returns the element that satisfied the predicate; lseq-any returns the true value that the predicate produced.

Like lseq-every, lseq-any's name does not end with a question mark -- this is to indicate that it does not return a simple boolean (#t or #f), but a general value.

(lseq-any integer? '(a 3 b 2.7))       ;=> #t
(lseq-any integer? '(a 3.1 b 2.7))     ;=> #f
(lseq-any < '(3 1 4 1 5) '(2 7 1 8 2)) ;=> #t

(define (factorial n)
  (cond
    ((< n 0) #f)
    ((= n 0) 1)
    (else (* n (factorial (- n 1))))))
(lseq-any factorial '(-1 -2 3 4))      ;=> 6

[procedure] (lseq-every pred lseq1 lseq2 ...)

Applies pred to successive elements of the lseqs, returning true if the predicate returns true on every application. If an application returns a false value, lseq-every immediately returns that value. Otherwise, it iterates until a false value is produced or one of the lseqs runs out of values; in the latter case, lseq-every returns the last value returned by pred, or #t if pred was never invoked. It is an error if pred does not accept the same number of arguments as there are lseqs and return a boolean result.

Like lseq-any, lseq-every's name does not end with a question mark -- this is to indicate that it does not return a simple boolean (#t or #f), but a general value.

(lseq-every factorial '(1 2 3 4)) ;=> 24

[procedure] (lseq-index pred lseq1 lseq2 ...)

Return the index of the leftmost element that satisfies pred.

Applies pred to successive elements of the lseqs, returning an index usable with lseq-ref if the predicate returns true. Otherwise, it iterates until one of the lseqs runs out of values, in which case #f is returned. It is an error if pred does not accept the same number of arguments as there are lseqs and return a boolean result.

The iteration stops when one of the lseqs runs out of values; in this case, lseq-index returns #f.

(lseq-index even? '(3 1 4 1 5 9))                ;=> 2
(lseq-index < '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) ;=> 1
(lseq-index = '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) ;=> #f

[procedure] (lseq-member x lseq [ pred ])
[procedure] (lseq-memq x lseq)
[procedure] (lseq-memv x lseq)

These procedures return the longest tail of lseq whose first element is x, where the tails of lseq are the non-empty lseqs returned by (lseq-drop lseq i) for i less than the length of lseq. If x does not occur in lseq, then #f is returned. lseq-memq uses eq? to compare x with the elements of lseq, while lseq-memv uses eqv?, and lseq-member uses pred, which defaults to equal?.

(lseq-memq 'a '(a b c))           ;=>  (a b c)
(lseq-memq 'b '(a b c))           ;=>  (b c)
(lseq-memq 'a '(b c d))           ;=>  #f
(lseq-memq (list 'a) '(b (a) c))  ;=>  #f
(lseq-member (list 'a)
             '(b (a) c))          ;=>  ((a) c)
(lseq-memq 101 '(100 101 102))    ;=>  *unspecified*
(lseq-memv 101 '(100 101 102))    ;=>  (101 102)

The equality procedure is used to compare the elements ei of lseq to the key x in this way: the first argument is always x, and the second argument is one of the lseq elements. Thus one can reliably find the first element of lseq that is greater than five with (lseq-member 5 lseq <)

Note that fully general lseq searching may be performed with the lseq-find-tail procedure, e.g.

(lseq-find-tail even? lseq) ; Find the first elt with an even key.

Repository

Github

Version History

1.2: Removes hardcoded .so extension from setup files.
1.1: Fixes typo in meta file.
1.0: Initial release

License

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.