`

Table of contents

• Abstract
• Rationale
• Procedure index
• Quotation
• The procedures
  • Constructors
  • Predicates
  • Selectors
  • The whole lazy sequence
  • Folding and mapping
  • Filtering and partitioning
  • Searching
  • Deletion
  • Immutable association lists
  • Conversion
  • Comparators
  • Realization
• Sample Implementation
• Acknowledgements
• References & links
• Copyright

Abstract

ABSTRACT

Rationale

RATIONALE

Note: In the prose, lazy sequences are known as lseqs throughout.

Procedure Index

Here is a short list of the procedures provided by this SRFI.

Quotation

The syntax keyword lq is provided as part of this SRFI. It is analogous to quote, taking an arbitrary number of literals and constructing an lseq from them, with any pairs in the literals converted to ipairs. It is useful for providing constant lazy sequences.

The procedures

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

To interpret the examples, pretend that they are executed on a Scheme that prints lazy sequences with the syntax of lists.

Constructors

lseq object ... -> lseq

Returns a newly allocated lseq of its arguments.

(lseq 'a (+ 3 4) 'c) =>  (a 7 c)
(lseq)               =>  ()

lseq* elt₁ elt₂ ... -> lseq

Like lseq, but the last argument is an lseq.

(lseq* 1 2 3 (lseq 4)) => (1 2 3 4)

list->lseq list -> lseq

vector->lseq vector -> lseq

string->lseq string -> lseq

generator->lseq generator -> lseq

Returns an lseq whose elements are the elements of list, vector, string, or the values generated by generator.

(list->lseq '(c c c c c)) => (c c c c)
(vector->lseq #(c c c c c)) => (c c c c)
(string->lseq "cccc") => (#\c #\c #\c #\c)
(generator->lseq (circular-generator 'c)) => (c c c ...)

lseq-unfold stop? mapper successor seed -> lseq

Creates a newly allocated lseq, and performs the following algorithm with the current seed set to seed:

If the result of applying the predicate stop? to the current seed is true, return the lseq. Otherwise, apply the procedure mapper to the current seed, returning a value which is appended to the lseq. Then get a new seed by applying the procedure successor to the current seed, and repeat this algorithm.

;; Lseq of squares: 1^2 ... 10^2
(lseq-unfold (lambda (x) (> x 10))
        (lambda (x) (* x x))
	(lambda (x) (+ x 1))
	1)

lseq-unfold-right stop? mapper successor seed -> lseq

Creates a newly allocated lseq, and performs the following algorithm with the current seed set to seed:

If the result of applying the predicate stop? to the current seed is true, return the lseq. Otherwise, apply the procedure mapper to the current seed, returning a value which is prepended to the lseq. Then get a new seed by applying the procedure successor to the current seed, and repeat this algorithm.

;; Lseq of squares: 10^2 ... 1^2
(lseq-unfold (lambda (x) (> x 10))
        (lambda (x) (* x x))
	(lambda (x) (+ x 1))
	1)

Predicates

lseq? x -> boolean

Returns #t iff x is an lseq, otherwise #f.

null-lseq? lseq -> boolean

This procedure returns #t if the argument is an empty lseq, and #f otherwise.

lseq= elt= lseq₁ ... -> boolean

Determines lseq equality, given an element-equality procedure. The lseq A equals the lseq B if they are of the same length, and their corresponding elements are equal, as determined by elt=. If the element-comparison procedure's first argument is from lseq_i, then its second argument is from lseq_i+1, i.e. it is always called as (elt= a b) for a an element of lseq A, and b an element of lseq B.

In the n-ary case, every lseq_i is compared to lseq_i+1 (as opposed, for example, to comparing lseq₁ to lseq_i, for i>1). If there are no lseq arguments at all, lseq= simply returns true.

Note that the dynamic order in which the elt= procedure is applied to pairs of elements is not specified. For example, if lseq= is applied to three lseqs, A, B, and C, it may first completely compare A to B, then compare B to C, or it may compare the first elements of A and B, then the first elements of B and C, then the second elements of A and B, and so forth.

The equality procedure must be consistent with eq?. That is, it must be the case that

(eq? x y) => (elt= x y).

Note that 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 comparisons.

(lseq= eq?) => #t       ; Trivial cases
(lseq= eq? (lq a)) => #t

Selectors

lseq-first   lseq -> object

lseq-second  lseq -> object

lseq-third   lseq -> object

lseq-fourth  lseq -> object

lseq-fifth   lseq -> object

lseq-sixth   lseq -> object

lseq-seventh lseq -> object

lseq-eighth  lseq -> object

lseq-ninth   lseq -> object

lseq-tenth   lseq -> object

lseq-last   lseq -> object

Returns the first, second, ..., tenth, last element of lseq.

(lseq-third (lq a b c d e)) => c

lseq-rest lseq -> lseq

Returns an lseq with the contents of lseq except for the first element. Note that it is an error to apply it to an empty lseq.

(lseq-first (lq a b c))       =>  a        (lseq-rest (lq a b c))         =>  (b c)  
(lseq-first (lq (a) b c d))   =>  (a)	      (lseq-rest (lq (a) b c d))     =>  (b c d)
(lseq-first (lseq-pair 1 2))  =>  1	      (lseq-rest (lseq-pair 1 2))    =>  2      
(lseq-first '())              =>  *error*  (lseq-rest '())                =>  *error*

lseq-ref lseq i -> value

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 (lq a b c d) 2) => c

lseq-take lseq i -> lseq

lseq-drop lseq i -> object

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

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

For a legal i, lseq-take and lseq-drop partition lseq in a manner which can be inverted with lseq-append:

(lseq-append (lseq-take lseq i) (lseq-drop lseq i)) = lseq

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

lseq-take-right lseq i -> object

lseq-drop-right lseq i -> lseq

lseq-take-right returns the last i elements of lseq.
lseq-drop-right returns all but the last i elements of lseq.

(lseq-take-right (lq a b c d e) 2) => (d e)
(lseq-drop-right (lq a b c d e) 2) => (a b c)

For a legal i, lseq-take-right and lseq-drop-right partition lseq in a manner which can be inverted with lseq-append:

(lseq-append (lseq-take lseq i) (lseq-drop lseq i)) = lseq

lseq-take-right's return value is guaranteed to share a common tail with lseq.

lseq-split-at  lseq i -> [lseq object]

Splits the lseq lseq at index i, returning two values, an lseq of the first i elements, and an lseq of the remaining elements. It is equivalent to

(values (lseq-take lseq i) (lseq-drop lseq i))

The whole lazy sequence

lseq-length  lseq -> integer

Returns the length of its argument, which is the non-negative integer n such that lseq-last applied n times to the lseq produces an empty lseq.

lseq-append  lseq₁ ... -> lseq

Returns an lseq consisting of the elements of lseq₁ followed by the elements of the other lseq parameters.

(lseq-append (lq x) (lq y))        =>  (x y)
(lseq-append (lq a) (lq b c d))    =>  (a b c d)
(lseq-append (lq a (b)) (lq (c)))  =>  (a (b) (c))

The resulting lseq is always newly allocated, except that it shares structure with the final lseq_i argument.

(lseq-append (lq a b) (lseq-pair 'c 'd))  =>  (a b c . d)
(lseq-append '() 'a)           =>  a
(lseq-append (lq x y))         =>  (x y)
(lseq-append)                  =>  ()

lseq-concatenate  list-of-lseqs -> value

Appends the elements of its argument together.

Note that some Scheme implementations do not support passing more than a certain number (e.g., 64) of arguments to an n-ary procedure. In these implementations, the (apply lseq-append ...) idiom would fail when applied to long lists, but lseq-concatenate would continue to function properly.

ireverse  lseq -> lseq

Returns a newly allocated lseq consisting of the elements of lseq in reverse order.

(lseq-reverse (lq a b c)) =>  (c b a)
(lseq-reverse (lq a (b c) d (e (f))))
    =>  ((e (f)) d (b c) a)

lseq-append-reverse  rev-head tail -> lseq

lseq-append-reverse returns (lseq-append (lseq-reverse rev-head) tail). It is provided because it is a common operation — a common list-processing style calls for this exact operation to transfer values accumulated in reverse order onto the front of another lseq, and because the implementation is significantly more efficient than the simple composition it replaces. (But note that this pattern of iterative computation followed by a reverse can frequently be rewritten as a recursion, dispensing with the reverse and lseq-append-reverse steps, and shifting temporary, intermediate storage from the heap to the stack, which is typically a win for reasons of cache locality and eager storage reclamation.)

lseq-zip lseq₁ lseq₂ ... -> lseq

(lambda lseqs (lseq-apply imap lseq lseqs))

If lseq-zip is passed n lseqs, it returns an lseq as long as the shortest of these lseqs, each element of which is an n-element list comprised of the corresponding elements from the arguments.

(lseq-zip (lq one two three) 
     (lq 1 2 3)
     (lq odd even odd even odd even odd even))
    => ((one 1 odd) (two 2 even) (three 3 odd))

(lseq-zip (lq 1 2 3)) => ((1) (2) (3))

lseq-unzip1 list-of-lseqs -> lseq

lseq-unzip2 list-of-lseqs -> [lseq lseq]

lseq-unzip3 list-of-lseqs -> [lseq lseq lseq]

lseq-unzip4 list-of-lseqs -> [lseq lseq lseq lseq]

lseq-unzip5 lslist-of-lseqs eq -> [lseq lseq lseq lseq lseq]

lseq-unzip1 takes a list of lseqs, where every lseq must contain at least one element, and returns an lseq containing the initial element of each such lseq. That is, it returns (lseq-map lseq-first lseqs). lseq-unzip2 takes a list of lseqs, where every lseq must contain at least two elements, and returns two values: an lseq of the first elements, and an lseq of the second elements. lseq-unzip3 does the same for the first three elements of the lseqs, and so forth.

(lseq-unzip2 (list (lq 1 one) (lq 2 two) (lq 3 three))) =>
    (1 2 3) 
    (one two three)

lseq-count pred lseq₁ lseq₂ ... -> integer

pred is a procedure taking as many arguments as there are lseqs and returning a single value. It is applied element-wise to the elements of the lseqs, and a count is tallied of the number of elements that produce a true value. This count is returned. count is "iterative" in that it is guaranteed to apply pred to the lseq elements in a left-to-right order. The counting stops when the shortest lseq expires.

(count even? (lq 3 1 4 1 5 9 2 5 6)) => 3
(count < (lq 1 2 4 8) (lq 2 4 6 8 10 12 14 16)) => 3

Folding and mapping

ifold kons knil lseq₁ lseq₂ ... -> value

The fundamental lseq iterator.

First, consider the single lseq-parameter case. If lseq₁ = (e₁ e₂ ... e_n), then this procedure returns

(kons en ... (kons e2 (kons e1 knil)) ... )

That is, it obeys the (tail) recursion

(lseq-fold kons knil lis) = (lseq-fold kons (kons (lseq-first lis) knil) (lseq-last lis))
(lseq-fold kons knil '()) = knil

Examples:

(lseq-fold + 0 lis)			; Add up the elements of LIS.

(lseq-fold ipair '() lis)		; Reverse LIS.

(lseq-fold ipair tail rev-head)	; See APPEND-REVERSE.

;; How many symbols in LIS?
(lseq-fold (lambda (x count) (if (symbol? x) (+ count 1) count))
      0
      lis)

;; Length of the longest string in LIS:
(lseq-fold (lambda (s max-len) (max max-len (string-length s)))
      0
      lis)

If n lseq arguments are provided, then the kons function must take n+1 parameters: one element from each lseq, and the "seed" or fold state, which is initially knil. The fold operation terminates when the shortest lseq runs out of values:

(lseq-fold ipair* '() (lq a b c) (lq 1 2 3 4 5)) => (c 3 b 2 a 1)

ifold-right kons knil lseq₁ lseq₂ ... -> value

The fundamental lseq recursion operator.

First, consider the single lseq-parameter case. If lseq₁ = (e1 e2 ... en), then this procedure returns

(kons e1 (kons e2 ... (kons en knil)))

That is, it obeys the recursion

(lseq-fold-right kons knil lis) = (kons (lseq-first lis) (lseq-fold-right kons knil (lseq-last lis)))
(lseq-fold-right kons knil '()) = knil

Examples:

(lseq-fold-right ipair '() lis)		; Copy LIS.

;; Filter the even numbers out of LIS.
(lseq-fold-right (lambda (x l) (if (even? x) (lseq-pair x l) l)) '() lis))

If n lseq arguments are provided, then the kons procedure must take n+1 parameters: one element from each lseq, and the "seed" or fold state, which is initially knil. The fold operation terminates when the shortest lseq runs out of values:

(lseq-fold-right ipair* '() (lq a b c) (lq 1 2 3 4 5)) => (a 1 b 2 c 3)

ipair-fold kons knil lseq₁ lseq₂ ... -> value

Analogous to fold, but kons is applied to successive sub-lseqs of the lseqs, rather than successive elements — that is, kons is applied to the ipairs making up the lists, giving this (tail) recursion:

(lseq-pair-fold kons knil lis) = (let ((tail (lseq-last lis)))
                              (lseq-pair-fold kons (kons lis knil) tail))
(lseq-pair-fold kons knil '()) = knil

Example:

(lseq-pair-fold ipair '() (lq a b c)) => ((c) (b c) (a b c))

ipair-fold-right kons knil lseq₁ lseq₂ ... -> value

Holds the same relationship with lseq-fold-right that lseq-pair-fold holds with lseq-fold. Obeys the recursion

(lseq-pair-fold-right kons knil lis) = 
    (kons lis (lseq-pair-fold-right kons knil (lseq-last lis)))
(lseq-pair-fold-right kons knil '()) = knil

Example:

(lseq-pair-fold-right ipair '() (lq a b c)) => ((a b c) (b c) (c))

ireduce f ridentity lseq -> value

lseq-reduce is a variant of lseq-fold.

ridentity should be a "right identity" of the procedure f — that is, for any value x acceptable to f,

(f x ridentity) = x

lseq-reduce has the following definition:

If lseq = (), return ridentity;
Otherwise, return (lseq-fold f (lseq-first lseq) (lseq-last lseq)).

...in other words, we compute (lseq-fold f ridentity lseq).

Note that ridentity is used only in an empty-lseq case. You typically use lseq-reduce when applying f is expensive and you'd like to avoid the extra application incurred when lseq-fold applies f to the head of lseq and the identity value, redundantly producing the same value passed in to f. For example, if f involves searching a file directory or performing a database query, this can be significant. In general, however, lseq-fold is useful in many contexts where lseq-reduce is not (consider the examples given in the lseq-fold definition — only one of the five folds uses a function with a right identity. The other four may not be performed with lseq-reduce).

;; take the max of an lseq of non-negative integers.
(lseq-reduce max 0 nums) ; i.e., (lseq-apply max 0 nums)

ireduce-right f ridentity lseq -> value

lseq-reduce-right is the fold-right variant of lseq-reduce. It obeys the following definition:

(lseq-reduce-right f ridentity '()) = ridentity
(lseq-reduce-right f ridentity (lq e1)) = (f e1 ridentity) = e1
(lseq-reduce-right f ridentity (lq e1 e2 ...)) =
    (f e1 (lseq-reduce f ridentity (e2 ...)))

...in other words, we compute (lseq-fold-right f ridentity lseq).

;; Append a bunch of lseqs together.
;; I.e., (lseq-apply iappend lseq-of-lseqs)
(lseq-reduce-right iappend '() lseq-of-lseqs)

imap proc lseq₁ lseq₂ ... -> lseq

proc is a procedure taking as many arguments as there are lseq arguments and returning a single value. lseq-map applies proc element-wise to the elements of the lseqs 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 icadr (lq (a b) (d e) (g h))) =>  (b e h)

(lseq-map (lambda (n) (expt n n))
     (lq 1 2 3 4 5))
    =>  (1 4 27 256 3125)

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

(let ((count 0))
  (lseq-map (lambda (lseq-gnored)
         (set! count (+ count 1))
         count)
       (lq a b))) =>  (1 2) or (2 1)

ifor-each proc lseq₁ lseq₂ ... -> unspecified

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.

(let ((v (make-vector 5)))
  (lseq-for-each (lambda (lseq-)
              (vector-set! v i (* i i)))
            (lq 0 1 2 3 4))
  v)  =>  #(0 1 4 9 16)

iappend-map  f lseq₁ lseq₂ ... -> value

Equivalent to

(lseq-apply iappend (lseq-map f lseq1 lseq2 ...))

and

(lseq-apply iappend (lseq-map f lseq1 lseq2 ...))

Map f over the elements of the lseqs, just as in the lseq-map function. However, the results of the applications are appended together (using lseq-append) to make the final result.

The dynamic order in which the various applications of f are made is not specified.

Example:

(lseq-append-map (lambda (x) (lseq x (- x))) (lq 1 3 8))
    => (1 -1 3 -3 8 -8)

Filtering & partitioning

ifilter pred lseq -> lseq

Return all the elements of lseq that satisfy predicate pred. The lseq is not disordered — elements that appear in the result lseq occur in the same order as they occur in the argument lseq. The returned lseq may share a common tail with the argument lseq. The dynamic order in which the various applications of pred are made is not specified.

(lseq-filter even? (lq 0 7 8 8 43 -4)) => (0 8 8 -4)

iremove pred lseq -> lseq

Returns lseq without the elements that satisfy predicate pred:

(lambda (pred lseq) (lseq-filter (lambda (x) (not (pred x))) lseq))

The lseq is not disordered — elements that appear in the result lseq occur in the same order as they occur in the argument lseq. The returned lseq may share a common tail with the argument lseq. The dynamic order in which the various applications of pred are made is not specified.

(lseq-remove even? (lq 0 7 8 8 43 -4)) => (7 43)

ipartition pred lseq -> [lseq lseq]

Partitions the elements of lseq with predicate pred, and returns two values: the lseq of in-elements and the lseq of out-elements. The lseq is not disordered — elements occur in the result lseqs in the same order as they occur in the argument lseq. The dynamic order in which the various applications of pred are made is not specified. One of the returned lseqs may share a common tail with the argument lseq.

(lseq-partition symbol? (lq one 2 3 four five 6)) => 
    (one four five)
    (2 3 6)

Searching

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

(lseq-find even? (lq 3 1 4 1 5 9)) => 4

(cond ((lseq-find-tail pred lis) => (lambda (lseq-pair) ...)) ; Handle (lseq-first ipair)
      (else ...)) ; Search failed.

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

;; IMEMBER X LIS:
(lseq-find-tail (lambda (elt) (equal? x elt)) lis)

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

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

(values (lseq-take-while pred lseq) 
        (lseq-drop-while pred lseq))

(lseq-span even? (lq 2 18 3 10 22 9)) =>
  (2 18)
  (3 10 22 9)

(lseq-break even? (lq 3 1 4 1 5 9)) =>
  (3 1)
  (4 1 5 9)

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

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

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

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

Deletion

idelete  x lseq [=] -> lseq

lseq-delete uses the comparison procedure =, which defaults to equal?, to find all elements of lseq that are equal to x, and deletes them from lseq. The dynamic order in which the various applications of = are made is not specified.

The lseq is not disordered — elements that appear in the result lseq occur in the same order as they occur in the argument lseq. The result may share a common tail with the argument lseq.

Note that fully general element deletion can be performed with the lseq-remove procedures, e.g.:

;; idelete all the even elements from LIS:
(lseq-remove even? lis)

The comparison procedure is used in this way: (= x ei). That is, x is always the first argument, and an lseq element is always the second argument. The comparison procedure will be used to compare each element of lseq exactly once; the order in which it is applied to the various e_i is not specified. Thus, one can reliably remove all the numbers greater than five from an lseq with (lseq-delete 5 lseq <)

idelete-duplicates  lseq [=] -> lseq

lseq-delete-duplicates removes duplicate elements from the lseq argument. If there are multiple equal elements in the argument lseq, the result lseq only contains the first or leftmost of these elements in the result. The order of these surviving elements is the same as in the original lseq — lseq-delete-duplicates does not disorder the lseq (hence it is useful for "cleaning up" immutable association lists).

The = parameter is used to compare the elements of the lseq; it defaults to equal?. If x comes before y in lseq, then the comparison is performed (= x y). The comparison procedure will be used to compare each pair of elements in lseq no more than once; the order in which it is applied to the various pairs is not specified.

Implementations of lseq-delete-duplicates are allowed to share common tails between argument and result lseqs — for example, if the lseq argument contains only unique elements, it may simply return exactly this lseq.

Be aware that, in general, lseq-delete-duplicates runs in time O(n²) for n-element lseqs. Uniquifying long lseqs can be accomplished in O(n lg n) time by sorting the lseq to bring equal elements together, then using a linear-time algorithm to remove equal elements. Alternatively, one can use algorithms based on element-marking, with linear-time results.

(lseq-delete-duplicates (lq a b a c a b c z)) => (a b c z)

;; Clean up an lazy alist:
(lseq-delete-duplicates (lq (a . 3) (b . 7) (a . 9) (c . 1))
                   (lambda (x y) (eq? (lseq-first x) (lseq-first y))))
    => ((a . 3) (b . 7) (c . 1))

Immutable association lists

An "immutable association list" (or "lazy alist") is an lseq of ipairs. The icar of each ipair contains a key value, and the icdr contains the associated data value. They can be used to construct simple look-up tables in Scheme. Note that lazy alists are probably inappropriate for performance-critical use on large data; in these cases, immutable maps or some other alternative should be employed.

iassoc key lazy alist [=] -> ipair or #f

iassq key lazy alist -> ipair or #f

iassv key lazy alist -> ipair or #f

lazy alist must be an immutable association list — an lseq of ipairs. These procedures find the first ipair in lazy alist whose icar field is key, and returns that ipair. If no ipair in lazy alist has key as its icar, then #f is returned. lseq-assq uses eq? to compare key with the icar fields of the ipairs in lazy alist, while lseq-assv uses eqv? and lseq-assoc uses equal?.

(define e (lq (a 1) (b 2) (c 3)))
(lseq-assq 'a e)                               =>  (a 1)
(lseq-assq 'b e)                               =>  (b 2)
(lseq-assq 'd e)                               =>  #f
(lseq-assq (lseq 'a) (lq ((a)) ((b)) ((c))))  =>  #f
(lseq-assoc (lseq 'a) (lq ((a)) ((b)) ((c)))) =>  ((a))
(lseq-assq 5 (lq (2 3) (5 7) (11 13)))	   =>  *unspecified*
(lseq-assv 5 (lq (2 3) (5 7) (11 13)))	   =>  (5 7)

The comparison procedure is used to compare the elements e_i of lseq to the key parameter in this way:

(= key (lseq-first ei)) ; lseq is (E1 ... En)

That is, the first argument is always key, and the second argument is one of the lseq elements. Thus one can reliably find the first entry of lazy alist whose key is greater than five with (lseq-assoc 5 lazy alist <)

Note that fully general lazy alist searching may be performed with the lseq-find-tail and lseq-find procedures, e.g.

;; Look up the first association in lazy alist with an even key:
(lseq-find (lambda (a) (even? (lseq-first a))) lazy alist)

lazy alist-cons key datum lazy alist -> lazy alist

(lambda (key datum lazy alist) (lseq-pair (lseq-pair key datum) lazy alist))

Construct a new lazy alist entry mapping key -> datum onto lazy alist.

lazy alist-delete  key lazy alist [=] -> lazy alist

lseq-alist-delete deletes all associations from lazy alist with the given key, using key-comparison procedure =, which defaults to equal?. The dynamic order in which the various applications of = are made is not specified.

Return values may share common tails with the lazy alist argument. The lazy alist is not disordered — elements that appear in the result lazy alist occur in the same order as they occur in the argument lazy alist.

The comparison procedure is used to compare the element keys k_i of lazy alist's entries to the key parameter in this way: (= key ki). Thus, one can reliably remove all entries of lazy alist whose key is greater than five with (lseq-alist-delete 5 lazy alist <)

Conversion

These procedures convert between mutable and immutable pair structures.

lseq->list lseq -> list

lseq->vector lseq -> vector

lseq->string lseq -> string

lseq->generator lseq -> generator

These procedures return a list, a vector, a string, or a generator that have the same elements as the argument.

Comparators

ipair-comparator

The lseq-comparator object is a SRFI-114 comparator suitable for comparing lseqs. Note that it is not a procedure. It compares lseqs using default-comparator on their first elements. If they are not equal, that value is returned. If they are equal, lseq-comparator is used on the lseq-rest of the lseqs and that value is returned.

make-lseq-comparator comparator -> comparator

The make-lseq-comparator procedure returns a comparator suitable for comparing lseqs using element-comparator to compare the elements.

Realization

These procedures have no directly visible effects on their lseq arguments. However, they force the generator inside the lazy sequence to produce all its arguments and store them internally, which means that later operations may be faster, particularly if the generator is slow. They return an unspecified value.

realize! lseq

Realizes all the values of lseq.

realize-once! lseq

Realizes exactly one additional value of lseq. If no additional values are available, does nothing.

realize-steps! lseq n

Realizes at most n values of lseq.

realize-until! lseq pred

Realizes values of lseq until at least one value satisfies pred.

Sample Implementation

An lseq is a SRFI 117 queue plus a generator. Queues can be shared between lseqs, which means that you are not allowed to remove anything from them, and the only addition operation is lseq-realize-once!, which realizes one value and adds it to the back of the queue.

The sample implementation of this SRFI depends on SRFI 9 (or R7RS) records. The files in the implementation are as follows:

FIXME

Acknowledgements

Without the work of Olin Shivers on SRFI 1, this SRFI would not exist. Everyone acknowledged there is transitively acknowledged here. This is not to imply that either Olin or anyone else necessarily endorses the final results, of course.