This site is a static rendering of the Trac instance that was used by R7RS-WG1 for its work on R7RS-small (PDF), which was ratified in 2013. For more information, see Home. For a version of this page that may be more recent, see LazySequencesCowan in WG2's repo for R7RS-large.

Lazy­Sequences­Cowan

cowan
2015-01-09 04:39:39
6history
source

`

Table of contents

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.

Constructors
lseq          lseq*        list->lseq 
vector->lseq  string->lseq generator->lseq 
lseq-unfold   lseq-unfold-right
Predicates
lseq?         null-lseq?   lseq=
Selectors
lseq-first lseq-second  lseq-third lseq-fourth lseq-fifth
lseq-sixth lseq-seventh lseq-eighth lseq-ninth lseq-tenth
lseq-last  lseq-rest    lseq-ref
lseq-take       lseq-drop
lseq-take-right lseq-drop-right
isplit-at   
The whole lazy sequence
lseq-length 
lseq-append  lseq-concatenate  lseq-reverse
lseq-zip     lseq-unzip1 lseq-unzip2 lseq-unzip3 lseq-unzip4 lseq-unzip5
lseq-count
Folding and mapping
lseq-map        lseq-for-each
lseq-fold       lseq-fold-right
lseq-fold       lseq-fold-right
lseq-reduce     lseq-reduce-right 
Filtering and partitioning
lseq-filter     lseq-partition  lseq-remove

Searching
lseq-member       lseq-memq     lseq-memv
lseq-find         lseq-find-rest 
lseq-any          lseq-every
lseq-index
lseq-take-while   lseq-drop-while
lseq-span         lseq-break
Deleting
lseq-delete       lseq-delete-neighbor-dups 

Lazy association lists
lseq-assoc        lseq-assq       lseq-assv
lseq-alist-cons   lseq-alist-delete
Conversion
lseq->list        lseq-vector
lseq->string      lseq->generator
Comparators
lseq-comparator   make-lseq-comparator
Realization
lseq-realize!              lseq-realize-once!
lseq-realize-steps!        lseq-realize-while!

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:

lseq A lazy sequence
x, y, d, a 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.

It is an error to pass a dotted lseq to a procedure not defined to accept such an argument.

Constructors

lseq object ... -> lseq
Returns a newly allocated lseq of its arguments.
(lseq 'a (+ 3 4) 'c) =>  (a 7 c)
(lseq)               =>  ()
lseq* elt1 elt2 ... -> 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 p f g seed [tail-gen] -> lseq
lseq-unfold is best described by its basic recursion:
(lseq-unfold p f g seed) = 
    (if (p seed) (tail-gen seed)
        (lseq-pair (f seed)
              (lseq-unfold p f g (g seed))))
p
Determines when to stop unfolding.
f
Maps each seed value to the corresponding lseq element.
g
Maps each seed value to next seed value.
seed
The "state" value for the unfold.
tail-gen
Creates the tail of the lseq; defaults to (lambda (x) '())

In other words, we use g to generate a sequence of seed values

seed, g(seed), g2(seed), g3(seed), ...
These seed values are mapped to lseq elements by f, producing the elements of the result lseq in a left-to-right order. P says when to stop.

lseq-unfold is the fundamental recursive lseq constructor, just as lseq-fold-right is the fundamental recursive lseq consumer. While lseq-unfold may seem a bit abstract to novice functional programmers, it can be used in a number of ways:

;; Lseq of squares: 1^2 ... 10^2
(lseq-unfold (lambda (x) (> x 10))
        (lambda (x) (* x x))
	(lambda (x) (+ x 1))
	1)
		
(lseq-unfold null-lseq? icar icdr lis) ; Copy a proper lseq.

;; Read current input port into an lseq of values.
(lseq-unfold eof-object? values (lambda (x) (read)) (read))

;; Copy a possibly non-proper lseq:
(lseq-unfold not-ipair? icar icdr lis 
              values)

;; Append HEAD onto TAIL:
(lseq-unfold null-lseq? icar icdr head 
              (lambda (x) tail))
Interested functional programmers may enjoy noting that lseq-fold-right and lseq-unfold are in some sense inverses. That is, given operations knull?, kar, kdr, kons, and knil satisfying
(kons (kar x) (kdr x)) = x and (knull? knil) = #t
then
(lseq-fold-right kons knil (lseq-unfold knull? kar kdr x)) = x
and
(lseq-unfold knull? kar kdr (lseq-fold-right kons knil x)) = x.
This combinator sometimes is called an "anamorphism;" when an explicit tail-gen procedure is supplied, it is called an "apomorphism."
iunfold-right p f g seed [tail] -> lseq
lseq-unfold-right constructs an lseq with the following loop:
(let lp ((seed seed) (lis tail))
  (if (p seed) lis
      (lp (g seed)
          (lseq-pair (f seed) lis))))
p
Determines when to stop unfolding.
f
Maps each seed value to the corresponding lseq element.
g
Maps each seed value to next seed value.
seed
The "state" value for the unfold.
tail
lseq terminator; defaults to '().

In other words, we use g to generate a sequence of seed values

seed, g(seed), g2(seed), g3(seed), ...
These seed values are mapped to lseq elements by f, producing the elements of the result lseq in a right-to-left order. P says when to stop.

lseq-unfold-right is the fundamental iterative lseq constructor, just as lseq-fold is the fundamental iterative lseq consumer. While lseq-unfold-right may seem a bit abstract to novice functional programmers, it can be used in a number of ways:

;; Lseq of squares: 1^2 ... 10^2
(lseq-unfold-right zero? 
              (lambda (x) (* x x))
              (lambda (x) (- x 1))
              10)
	
;; Reverse a proper lseq.
(lseq-unfold-right null-lseq? icar icdr lis)

;; Read current input port into an lseq of values.
(lseq-unfold-right eof-object? values (lambda (x) (read)) (read))

;; (lseq-append-reverse rev-head tail)
(lseq-unfold-right null-lseq? icar icdr rev-head tail)
Interested functional programmers may enjoy noting that lseq-fold and lseq-unfold-right are in some sense inverses. That is, given operations knull?, kar, kdr, kons, and knil satisfying
(kons (kar x) (kdr x)) = x and (knull? knil) = #t
then
(lseq-fold kons knil (lseq-unfold-right knull? kar kdr x)) = x
and
(lseq-unfold-right knull? kar kdr (lseq-fold kons knil x)) = x.
This combinator presumably has some pretentious mathematical name; interested readers are invited to communicate it to the author.

Predicates

lseq? x -> boolean
True is returned iff x is an lseq.
null-lseq? lseq -> boolean
This procedure returns true if the argument is the empty lseq, and false otherwise.
lseq= elt= lseq1 ... -> 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 lseqi, then its second argument is from lseqi+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 lseqi is compared to lseqi+1 (as opposed, for example, to comparing lseq1 to lseqi, 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

ifirst   lseq -> object
isecond  lseq -> object
ithird   lseq -> object
ifourth  lseq -> object
ififth   lseq -> object
isixth   lseq -> object
iseventh lseq -> object
ieighth  lseq -> object
ininth   lseq -> object
itenth   lseq -> object
Returns the first, second, ..., tenth element of lseq.
(lseq-third (lq a b c d e)) => c
lseq-last lseq -> lseq
This procedure returns an lseq with the contents of lseq except for the first element. Note that it is an error to apply it to the empty lseq.
(lseq-first (lq a b c))       =>  a        (lseq-last (lq a b c))     =>  (b c)  
(lseq-first (lq (a) b c d))   =>  (a)	     (lseq-last (lq (a) b c d)) =>  (b c d)
(lseq-first (lseq-pair 1 2))      =>  1	     (lseq-last (lseq-pair 1 2))    =>  2      
(lseq-first '())              =>  *error*  (lseq-last '())            =>  *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.
isplit-at  lseq i -> [lseq object]
lseq-split-at splits the lseq lseq at index i, returning two values, an lseq of the first i elements, and an lseq of the remaining tail. It is equivalent to
(values (lseq-take lseq i) (lseq-drop lseq i))
ilast ipair -> object
last-ipair ipair -> ipair
Returns the last element of the non-empty, possibly dotted, lseq ipair. last-ipair returns the last ipair in the non-empty lseq pair.
(lseq-last (lq a b c))      => c
(last-ipair (lq a b c)) => (c)

Miscellaneous: length, append, concatenate, reverse, zip & count

ilength  lseq -> integer
Returns the length of its argument. It is an error to pass a value to lseq-length which is not a proper lseq (()-terminated).

The length of a proper lseq is a non-negative integer n such that lseq-last applied n times to the lseq produces the empty list.

iappend  lseq1 ... -> lseq
Returns an lseq consisting of the elements of lseq1 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 lseqi argument. This last argument may be any value at all; an improper lseq results if it is not a proper lseq. All other arguments must be proper lseqs.
(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)                  =>  ()
iconcatenate  lseq-of-lseqs -> value
Appends the elements of its argument together. That is, lseq-concatenate returns
(lseq-apply iappend lseq-of-lseqs)
or, equivalently,
(lseq-reduce-right iappend '() lseq-of-lseqs)

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 (lseq-apply iappend ...) idiom would fail when applied to long lists, but lseq-concatenate would continue to function properly.

As with lseq-append, the last element of the input list may be any value at all.

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)
iappend-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.)
izip lseq1 lseq2 ... -> 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 lseq comprised of the corresponding elements from the parameter lseqs.
(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))
iunzip1 lseq -> lseq
iunzip2 lseq -> [lseq lseq]
iunzip3 lseq -> [lseq lseq lseq]
iunzip4 lseq -> [lseq lseq lseq lseq]
iunzip5 lseq -> [lseq lseq lseq lseq lseq]
lseq-unzip1 takes an lseq 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 icar lseqs). lseq-unzip2 takes an lseq 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 (lq (1 one) (2 two) (3 three))) =>
    (1 2 3) 
    (one two three)
icount pred lseq1 lseq2 ... -> 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

Fold, unfold & map

ifold kons knil lseq1 lseq2 ... -> value
The fundamental lseq iterator.

First, consider the single lseq-parameter case. If lseq1 = (e1 e2 ... en), 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 lseq1 lseq2 ... -> value
The fundamental lseq recursion operator.

First, consider the single lseq-parameter case. If lseq1 = (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 lseq1 lseq2 ... -> 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 lseq1 lseq2 ... -> 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 the empty-list 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 lseq1 lseq2 ... -> 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 lseq1 lseq2 ... -> 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 lseq1 lseq2 ... -> 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)
imap-in-order f lseq1 lseq2 ... -> lseq
A variant of the lseq-map procedure that guarantees to apply f across the elements of the lseqi arguments in a left-to-right order. This is useful for mapping procedures that both have side effects and return useful values.

ipair-for-each f lseq1 lseq2 ... -> unspecific
Like lseq-for-each, but f is applied to successive sub-lseqs of the argument lseqs. That is, f is applied to the cells of the lseqs, rather than the lseqs' elements. These applications occur in left-to-right order.
(lseq-pair-for-each (lambda (lseq-pair) (display ipair) (newline)) (lq a b c)) ==>
    (a b c)
    (b c)
    (c)
ifilter-map f lseq1 lseq2 ... -> lseq
Like lseq-map, but only true values are saved.
(lseq-filter-map (lambda (x) (and (number? x) (* x x))) (lq a 1 b 3 c 7))
    => (1 9 49)
The dynamic order in which the various applications of f are made is not specified.

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)
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)
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)

Searching

The following procedures all search lseqs for a leftmost element satisfying some criteria. This means they do not always examine the entire lseq; thus, there is no efficient way for them to reliably detect and signal an error when passed a dotted lseq. Here are the general rules describing how these procedures work when applied to different kinds of lseqs:

Proper lseqs:
The standard, canonical behavior happens in this case.
Dotted lseqs:
It is an error to pass these procedures a dotted lseq that does not contain an element satisfying the search criteria. That is, it is an error if the procedure has to search all the way to the end of the dotted lseq. However, this SRFI does not specify anything at all about the behavior of these procedures when passed a dotted lseq containing an element satisfying the search criteria. It may finish successfully, signal an error, or perform some third action. Different implementations may provide different functionality in this case; code which is compliant with this SRFI may not rely on any particular behavior. Future SRFIs may refine this SRFI to define specific behavior in this case.

In brief, compliant code may not pass a dotted lseq argument to these procedures.

Here are some examples, using the lseq-find and lseq-any procedures as canonical representatives:

;; Proper lseq — success
(lseq-find even? (lq 1 2 3))	=> 2
(lseq-any  even? (lq 1 2 3))	=> #t

;; proper lseq — failure
(lseq-find even? (lq 1 7 3))	=> #f
(lseq-any  even? (lq 1 7 3))	=> #f

;; Failure is error on a dotted lseq.
(lseq-find even? (lseq-pair (1 (lseq-pair 3 x)))	=> error
(lseq-any  even? (lseq-pair (1 (lseq-pair 3 x)))	=> error

;; The dotted lseq contains an element satisfying the search.
;; This case is not specified — it could be success, an error, 
;; or some third possibility.
(lseq-find even? (lseq-pair (1 (lseq-pair 2 x)))	=> error/undefined
(lseq-any  even? (lseq-pair (1 (lseq-pair 2 x))))	=> error/undefined ; success, error or other.

ifind pred lseq -> value
Return the first element of lseq that satisfies predicate pred; false if no element does.
(lseq-find even? (lq 3 1 4 1 5 9)) => 4
Note that lseq-find has an ambiguity in its lookup semantics — if lseq-find returns #f, you cannot tell (lseq-n general) if it found a #f element that satisfied pred, or if it did not find any element at all. In many situations, this ambiguity cannot arise — either the lseq being searched is known not to contain any #f elements, or the lseq is guaranteed to have an element satisfying pred. However, in cases where this ambiguity can arise, you should use lseq-find-tail instead of lseq-findlseq-find-tail has no such ambiguity:
(cond ((lseq-find-tail pred lis) => (lambda (lseq-pair) ...)) ; Handle (lseq-first ipair)
      (else ...)) ; Search failed.
ifind-tail pred lseq -> ipair or false
Return the first ipair of lseq whose icar satisfies pred. If no ipair does, return false.

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

Examples:

(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-find-tail is essentially lseq-drop-while, 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.

itake-while  pred lseq -> lseq
Returns the longest initial prefix of lseq whose elements all satisfy the predicate pred.

(lseq-take-while even? (lq 2 18 3 10 22 9)) => (2 18)
idrop-while pred lseq -> lseq
idrops the longest initial prefix of lseq whose elements all satisfy the predicate pred, and returns the rest of the lseq.
(lseq-drop-while even? (lq 2 18 3 10 22 9)) => (3 10 22 9)
ispan   pred lseq -> [lseq lseq]
ibreak  pred lseq -> [lseq lseq]
lseq-span splits the lseq into the longest initial prefix whose elements all satisfy pred, and the remaining tail. lseq-break inverts the sense of the predicate: the tail commences with the first element of the input lseq that satisfies the predicate.

In other words: lseq-span finds the initial span of elements satisfying pred, and lseq-break breaks the lseq at the first element satisfying pred.

lseq-span is equivalent to

(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)
iany pred lseq1 lseq2 ... -> value
Applies the predicate across the lseqs, returning true if the predicate returns true on any application.

If there are n lseq arguments lseq1 ... lseqn, then pred must be a procedure taking n arguments and returning a boolean result.

lseq-any applies pred to the first elements of the lseqi parameters. If this application returns a true value, lseq-any immediately returns that value. Otherwise, it iterates, applying pred to the second elements of the lseqi parameters, then the third, and so forth. The iteration stops when a true value is produced or one of the lseqs runs out of values; in the latter case, lseq-any returns #f. The application of pred to the last element of the lseqs is a tail call.

Note the difference between lseq-find and lseq-anylseq-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? (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
ievery pred lseq1 lseq2 ... -> value
Applies the predicate across the lseqs, returning true if the predicate returns true on every application.

If there are n lseq arguments lseq1 ... lseqn, then pred must be a procedure taking n arguments and returning a boolean result.

lseq-every applies pred to the first elements of the lseqi parameters. If this application returns false, lseq-every immediately returns false. Otherwise, it iterates, applying pred to the second elements of the lseqi parameters, then the third, and so forth. The iteration stops when a false value is produced or one of the lseqs runs out of values. In the latter case, lseq-every returns the true value produced by its final application of pred. The application of pred to the last element of the lseqs is a tail call.

If one of the lseqi has no elements, lseq-every simply returns #t.

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-index pred lseq1 lseq2 ... -> integer or false
Return the index of the leftmost element that satisfies pred.

If there are n lseq arguments lseq1 ... lseqn, then pred must be a function taking n arguments and returning a boolean result.

lseq-index applies pred to the first elements of the lseqi parameters. If this application returns true, lseq-index immediately returns zero. Otherwise, it iterates, applying pred to the second elements of the lseqi parameters, then the third, and so forth. When it finds a tuple of lseq elements that cause pred to return true, it stops and returns the zero-based index of that position in the lseqs.

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

(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
imember x lseq [=] -> lseq
imemq x lseq -> lseq
imemv x lseq -> lseq
These procedures return the first sub-lseq of lseq whose icar is x, where the sub-lseqs 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 equal?.
    (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)

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

(= x ei) ; lseq is (E1 ... En)
That is, 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 and lseq-find procedures, e.g.

(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 ei 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(n2) 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 ialist:
(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 "ialist") 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 ialists are probably inappropriate for performance-critical use on large data; in these cases, immutable maps or some other alternative should be employed.

iassoc key ialist [=] -> ipair or #f
iassq key ialist -> ipair or #f
iassv key ialist -> ipair or #f
ialist must be an immutable association list — an lseq of ipairs. These procedures find the first ipair in ialist whose icar field is key, and returns that ipair. If no ipair in ialist has key as its icar, then #f is returned. lseq-assq uses eq? to compare key with the icar fields of the ipairs in ialist, 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 ei 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 ialist whose key is greater than five with (lseq-assoc 5 ialist <)

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

;; Look up the first association in ialist with an even key:
(lseq-find (lambda (a) (even? (lseq-first a))) ialist)
ialist-cons key datum ialist -> ialist
(lambda (key datum ialist) (lseq-pair (lseq-pair key datum) ialist))
Construct a new ialist entry mapping key -> datum onto ialist.
ialist-delete  key ialist [=] -> ialist
lseq-alist-delete deletes all associations from ialist 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 ialist argument. The ialist is not disordered — elements that appear in the result ialist occur in the same order as they occur in the argument ialist.

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

Conversion

These procedures convert between mutable and immutable pair structures.

pair->ipair pair -> ipair
ipair->pair ipair -> pair
These procedures, which are inverses, return an ipair and a pair respectively that have the same (lseq-)car and (lseq-)cdr fields as the argument.
list->lseq flist -> lseq
lseq->list lseq -> flist

These procedures return an lseq and a list respectively that have the same elements as the argument. The tails of dotted (lseq-)lists are preserved in the result, which makes the procedures not inverses when the tail of a dotted lseq is a list or vice versa. The empty list is converted to itself.

It is an error to apply list->lseq to a circular list.

tree->itree object -> object
itree->tree object -> object

These procedures walk a tree of pairs or ipairs respectively and make a deep copy of it, returning an isomorphic tree containing ipairs or pairs respectively. The result may share structure with the argument. If the argument is not of the expected type, it is returned.

These procedures are not inverses in the general case. For example, a pair of ipairs would be converted by tree->itree to an ipair of ipairs, which if converted by lseq-tree->tree would produce a pair of pairs.

gtree->itree object -> object
gtree->tree object -> object
These procedures walk a generalized tree consisting of pairs, ipairs, or a combination of both, and make a deep copy of it, returning an isomorphic tree containing only ipairs or pairs respectively. The result may share structure with the argument. If the argument is neither a pair nor an ipair, it is returned.

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 pairs using default-comparator on their first elements. If they are not equal, that value is returned. If they are equal, default-comparator is used on the 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.

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.