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.
Source for wiki LazySequencesCowan version 22
author
cowan
comment
ipnr
127.11.51.1
name
LazySequencesCowan
readonly
0
text
`
{{{
#!html
<h1>Table of contents</h1>
<ul id="toc-table">
<li><a href="#Abstract">Abstract</a>
</li><li><a href="#Rationale">Rationale</a>
</li><li><a href="#ProcedureIndex">Procedure index</a>
<li><a href="#Specification">Specification</a>
<ul>
<li><a href="#Constructors">Constructors</a>
</li><li><a href="#Predicates">Predicates</a>
</li><li><a href="#Selectors">Selectors</a>
</li><li><a href="#Whole">The whole lazy sequence</a>
</li><li><a href="#FoldingMapping">Folding and mapping</a>
</li><li><a href="#Searching">Searching</a>
</li><li><a href="#LazyAssociationLists">Lazy association lists</a>
</li><li><a href="#Comparators">Comparators</a>
</li></ul>
</li><li><a href="#SampleImplementation">Sample Implementation</a>
</li><li><a href="#Acknowledgements">Acknowledgements</a>
</li><li><a href="#ReferencesLinks">References & links</a>
</li><li><a href="#Copyright">Copyright</a>
</li></ul>
<!--========================================================================-->
<h1><a name="Abstract">Abstract</a></h1>
<p>
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 <a href="http://srfi.schemers.org/srfi-121/srfi-121.html">SRFI 121</a> 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.</p>
<p>This proposal provides a set of procedures
suitable for operating on lazy sequences based
on <a href="http://srfi.schemers.org/srfi-1/srfi-1.html">SRFI 1</a>.</p>
<h1><a name="Rationale">Rationale</a></h1>
<p>Lazy sequences are more heavyweight than generators, on which they
are based, but they are more lightweight
than <a href="http://srfi.schemers.org/srfi-41/srfi-41.html">SRFI 41</a> streams.
However, streams are <i>even</i>, as explained in the SRFI 41 rationale;
that is, the initial state of a stream does not have any elements that
have already been realized. By contrast, lazy sequences are <i>odd</i>,
meaning that at least one element is realized at all times unless the lseq
is empty. Therefore, when constructing an lseq in an iterative lazy algorithm,
only the cdr side of the lazy pair is lazily evaluated; the car side is evaluated
immediately, even if it is never used.</p>
<p>In most cases this doesn't matter,
because calculating one additional item is a negligible overhead.
However, when you create a self-referential lazy structure,
in which the earlier elements of a sequence are used to calculate
the latter elements of itself, a bit of caution is needed;
code that is valid for circular streams may not terminate
if it is mechanically converted to use lazy sequences.
This eagerness is also visible when side effects are involved;
for example, a lazy character sequence reading from a port
may read one character ahead.</p>
<p>This proposal is less comprehensive than SRFI 1, because it omits
many procedures that process every element of their list arguments (at least,
when used in the absence of <code>call/cc</code>). Lseqs are meant
to be used with ordinary Scheme functions, which are strict; consequently,
neither left nor right folds are able to work on infinite sequences,
so the only difference between folding over an lseq and realizing it as
a list and using list fold is space efficiency (for which reason
<code>lseq-fold</code> is provided). The
linear-update procedures of SRFI 1 are also left out, as lazy sequences
are not intended to be mutated.</p>
<!--========================================================================-->
<h1><a name="ProcedureIndex">Procedure Index</a></h1>
<p>
Here is a short list of the procedures provided by this SRFI.
</p><div class="indent">
<dl>
<dt class="proc-index"> Constructors
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#generator->lseq">generator->lseq</a>
</pre>
</dd><dt class="proc-index"> Predicates
</dt><dd class="proc-index">
<pre class="proc-index">
<a href="#lseq-p">lseq?</a> <a href="#lseq=">lseq=</a>
</pre>
</dd><dt class="proc-index"> Selectors
</dt><dd class="proc-index">
<pre class="proc-index">
<a href="#lseq-car">lseq-car</a> <a href="#lseq-cdr">lseq-cdr</a>
<a href="#lseq-first">lseq-first</a> <a href="#lseq-second">lseq-second</a> <a href="#lseq-third">lseq-third</a> <a href="#lseq-fourth">lseq-fourth</a> <a href="#lseq-fifth">lseq-fifth</a>
<a href="#lseq-sixth">lseq-sixth</a> <a href="#lseq-seventh">lseq-seventh</a> <a href="#lseq-eighth">lseq-eighth</a> <a href="#lseq-ninth">lseq-ninth</a> <a href="#lseq-tenth">lseq-tenth</a>
<a href="#lseq-rest">lseq-rest</a> <a href="#lseq-ref">lseq-ref</a>
<a href="#lseq-take">lseq-take</a> <a href="#lseq-drop">lseq-drop</a> <a href="#lseq-split-at">lseq-split-at</a>
</pre>
</dd><dt class="proc-index"> The whole lazy sequence
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq-realize">lseq-realize</a> <a href="#lseq->generator">lseq->generator</a>
<a href="#lseq-length">lseq-length</a>
<a href="#lseq-append">lseq-append</a> <a href="#lseq-concatenate">lseq-concatenate</a>
<a href="#lseq-zip">lseq-zip</a> <a href="#lseq-unzip1">lseq-unzip1</a> <a href="#lseq-unzip2">lseq-unzip2</a>
<a href="#lseq-unzip3">lseq-unzip3</a> <a href="#lseq-unzip4">lseq-unzip4</a> <a href="#lseq-unzip5">lseq-unzip5</a>
</pre>
</dd><dt class="proc-index"> Folding and mapping
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq-map">lseq-map</a>
<a href="#lseq-fold">lseq-fold</a> <a href="#lseq-reduce">lseq-reduce</a>
<a href="#lseq-for-each">lseq-for-each</a> <a href="#lseq-pair-for-each">lseq-pair-for-each</a>
</pre>
</dd><dt class="proc-index"> Searching
</dt><dd class="proc-index"><pre class="proc-index">
<a href="#lseq-member">lseq-member</a> <a href="#lseq-memq">lseq-memq</a> <a href="#lseq-memv">lseq-memv</a>
<a href="#lseq-find">lseq-find</a> <a href="#lseq-find-rest">lseq-find-rest</a>
<a href="#lseq-any">lseq-any</a> <a href="#lseq-every">lseq-every</a>
<a href="#lseq-index">lseq-index</a>
<a href="#lseq-take-while">lseq-take-while</a> <a href="#lseq-drop-while">lseq-drop-while</a>
<a href="#lseq-span">lseq-span</a> <a href="#lseq-break">lseq-break</a>
</pre>
</dd><dt class="proc-index"> Lazy association lists
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq-assoc">lseq-assoc</a> <a href="#lseq-assq">lseq-assq</a> <a href="#lseq-assv">lseq-assv</a>
</pre>
</dd><dt class="proc-index"> Comparators
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq-comparator">lseq-comparator</a> <a href="#make-lseq-comparator">make-lseq-comparator</a>
</pre>
</dd></dl>
<!--========================================================================-->
<h1><a name="Specification">Specification</a></h1>
<p>Except as noted, if any of these procedures accepts multiple lseq arguments, then at
least one of them must be finite: that is, it must either be a proper list,
or contain a generator that eventually returns an end-of-file object.</p>
<p>
The templates given below obey the following conventions for procedure formals:
</p><table>
<tbody><tr valign="baseline"><th align="left"> <var>lseq</var>
</th><td> A lazy sequence
</td></tr><tr valign="baseline">
<th align="left"> <var>x</var>, <var>y</var>, <var>a</var>, <var>b</var>
</th><td> Any value
</td></tr><tr valign="baseline"><th align="left"> <var>object</var>, <var>value</var>
</th><td> Any value
</td></tr><tr valign="baseline"><th align="left"> <var>n</var>, <var>i</var>
</th><td> A natural number (an integer >= 0)
</td></tr><tr valign="baseline"><th align="left"> <var>proc</var>
</th><td> A procedure
</td></tr><tr valign="baseline"><th align="left"> <var>pred</var>
</th><td> A procedure whose return value is treated as a boolean
</td></tr><tr valign="baseline"><th align="left"> <var>generator</var>
</th><td> A procedure with no arguments that returns a sequence of values
</td></tr><tr valign="baseline"><th align="left"> <var>=</var>
</th><td> A boolean procedure taking two arguments
</td></tr></tbody></table>
<p>To interpret the examples, pretend that they are executed on a Scheme that prints lazy sequences with the syntax of lists.
<!--========================================================================-->
</p><h2><a name="Constructors">Constructors</a></h2>
<p>
Every list constructor procedure is also an lseq constructor procedure.
The procedure <code>generator->lseq</code> constructs an lseq based on the
values of a generator. In order to prepend a realized value to a generator,
simply use <code>cons</code>; to prepend more than one value, use SRFI 1's
<code>cons*</code>.
</p><dl>
<a name="generator->lseq"></a>
</dd><dt class="proc-def"> <code class="proc-def">generator->lseq</code> <var>generator -> lseq</var>
</dt><dd class="proc-def">
<p>Returns an lseq
whose elements are the values generated by <var>generator</var>. The exact behavior is as follows:</p>
<ul><li><var>Generator</var> is invoked with no arguments to produce an object <var>obj</var>.</li>
<li>If <var>obj</var> is an end-of-file object, the empty list is returned.</li>
<li>Otherwise, a newly allocated pair whose car is <var>obj</var> and whose
cdr is <var>generator</var> is returned.</li>
</ul>
<pre class="code-example">
(generator->lseq (make-repeating-generator 'c)) => (c c c ...)
</pre></dd></dl>
<!--========================================================================-->
<h2><a name="Predicates">Predicates</a></h2>
<dl>
<!--
==== lseq?
============================================================================-->
<dt class="proc-def">
<code class="proc-def">lseq?</code><var> x -> boolean</var>
<a name="lseq-p"></a>
</dt><dd class="proc-def">
<p>Returns <code>#t</code> iff <var>x</var> is an lseq, otherwise <code>#f</code>.
This procedure may return <code>#t</code> if <var>x</var> is an improper list
whose last car is a procedure that requires arguments, since there is no
portable way to examine a procedure to determine how many arguments it requires.
</p>
<!--
==== lseq=
============================================================================-->
</dd><dt class="proc-def">
<a name="list="></a>
<code class="proc-def">lseq=</code><var> elt= lseq<sub>1</sub> ... -> boolean</var>
</dt><dd class="proc-def">
<p>Determines lseq equality, given an element-equality procedure.
The lseq <var>A</var> equals the lseq <var>B</var>
if they are of the same length,
and their corresponding elements are equal,
as determined by <var>elt=</var>.
If the element-comparison procedure's first argument is
from <var>lseq<sub>i</sub></var>,
then its second argument is from <var>lseq<sub>i+1</sub></var>,
<em>i.e.</em> it is always called as
<code>(<var>elt=</var> <var>a</var> <var>b</var>)</code>
for <var>a</var> an element of lseq <var>A</var>,
and <var>b</var> an element of lseq <var>B</var>.</p>
<p>
In the <var>n</var>-ary case,
every <var>lseq<sub>i</sub></var> is compared to
<var>lseq<sub>i+1</sub></var>
(as opposed, for example, to comparing
<var>lseq<sub>1</sub></var> to <var>lseq<sub>i</sub></var>,
for <var>i</var>>1).
If there are no lseq arguments at all,
<code>lseq=</code> simply returns true.
</p><p>
The dynamic order in which the <var>elt=</var> procedure is
applied to pairs of elements is not specified.
For example, if <code>lseq=</code> is applied
to three lseqs, <var>A</var>, <var>B</var>, and <var>C</var>,
it may first completely compare <var>A</var> to <var>B</var>,
then compare <var>B</var> to <var>C</var>,
or it may compare the first elements of <var>A</var> and <var>B</var>,
then the first elements of <var>B</var> and <var>C</var>,
then the second elements of <var>A</var> and <var>B</var>, and so forth.
</p><p>
The equality procedure must be consistent with <code>eq?</code>.
That is, it must be the case that
</p><div class="indent">
<code>(eq? <var>x</var> <var>y</var>)</code> => <code>(<var>elt=</var> <var>x</var> <var>y</var>)</code>.
</div>
<p>Note that this implies that two lseqs which are <code>eq?</code>
are always <code>lseq=</code>, as well; implementations may exploit this
fact to "short-cut" the element-by-element comparisons.</p>
<pre class="code-example">(lseq= eq?) => #t ; Trivial cases
(lseq= eq? '(a)) => #t
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="Selectors">Selectors</a></h2>
<dl>
<!--
==== lseq-first
============================================================================-->
<dt class="proc-defi">
<a name="lseq-car"></a>
<code class="proc-def">lseq-car </code><var>lseq -> object </var>
</dt><dt class="proc-defn">
<a name="lseq-first"></a>
<code class="proc-def">lseq-first </code><var>lseq -> object </var>
</dt>
<p>These procedures are synonymous.
They return the first element of <var>lseq</var>. They
are included for completeness, as they are the same as <code>car</code>.
It is an error to apply them to an empty lseq.</p>
<!--
==== lseq-rest
============================================================================-->
<dt class="proc-defi">
<a name="lseq-cdr"></a>
<code class="proc-def">lseq-cdr </code><var>lseq -> lseq</var>
</dt><dt class="proc-defn">
<a name="lseq-rest"></a>
<code class="proc-def">lseq-rest </code><var>lseq -> lseq</var>
</dt>
<p>These procedures are synonymous.
They return an lseq with the contents of <var>lseq</var> except for the
first element. The exact behavior is as follows:</p>
<ul><li>If <var>lseq</var> is a pair whose cdr is a procedure, then the procedure
is invoked with no arguments to produce an object <var>obj</var>.</li>
<li>If <var>obj</var> is an end-of-file object, then the cdr of <var>lseq</var> is
set to the empty list, which is returned.</li>
<li>If <var>obj</var> is any other object, then a new pair is allocated whose car
is <i>obj</i> and whose cdr is the cdr of <var>lseq</var> (i.e. the procedure).
The cdr of <var>lseq</var> is set to the newly allocated pair, which is returned.</li>
<li>If <var>lseq</var> is a pair whose cdr is not a procedure, then the cdr is returned.</li>
<li>If <var>lseq</var> is not a pair, it is an error.</li>
<ul>
<p>Implementations that inline <code>cdr</code> are advised to inline <code>lseq-cdr</code> if
possible.</p>
<!--
==== lseq-tenth
==== lseq-ninth
==== lseq-eighth
==== lseq-seventh
==== lseq-sixth
==== lseq-fifth
==== lseq-fourth
==== lseq-third
==== lseq-second
============================================================================-->
</dd><dt class="proc-def1">
<a name="lseq-second"></a>
<code class="proc-def">lseq-second </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-third"></a>
<code class="proc-def">lseq-third </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-fourth"></a>
<code class="proc-def">lseq-fourth </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-fifth"></a>
<code class="proc-def">lseq-fifth </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-sixth"></a>
<code class="proc-def">lseq-sixth </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-seventh"></a>
<code class="proc-def">lseq-seventh </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-eighth"></a>
<code class="proc-def">lseq-eighth </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-ninth"></a>
<code class="proc-def">lseq-ninth </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-tenth"></a>
<code class="proc-def">lseq-tenth </code><var>lseq -> object </var>
</dt><dt class="proc-defn">
</dt><dd class="proc-def">
<p>Returns the second, third, ..., or tenth element of <var>lseq</var>.</p>
<pre class="code-example">(lseq-third '(a b c d e)) => c
</pre>
<!--
==== lseq-ref
============================================================================-->
<a name="lseq-ref"></a>
</dd><dt class="proc-def"><code class="proc-def">lseq-ref</code><var> lseq i -> value</var>
</dt><dd class="proc-def">
<p>Returns the <var>i</var>th element of <var>lseq</var>.
(This is the same as
<code>(lseq-first (lseq-drop <var>lseq</var> <var>i</var>))</code>.)
It is an error if <var>i</var> >= <var>n</var>,
where <var>n</var> is the length of <var>lseq</var>.</p>
<pre class="code-example">
(lseq-ref '(a b c d) 2) => c
</pre>
<!--
==== lseq-drop
==== lseq-take
============================================================================-->
</dd><dt class="proc-def1">
<a name="lseq-take"></a>
<code class="proc-def">lseq-take</code><var> lseq i -> list</var>
</dt><dt class="proc-defi">
<a name="lseq-drop"></a>
<code class="proc-def">lseq-drop</code><var> lseq i -> lseq</var>
</dt><dt class="proc-def">
</dt><dd class="proc-def">
<p><code>lseq-take</code> returns the first <var>i</var> elements of <var>lseq</var> as a proper list.<br/>
<code>lseq-drop</code> returns all but the first <var>i</var> elements of <var>lseq</var>.<br/></p>
<pre class="code-example">(lseq-take '(a b c d e) 2) => (a b)
(lseq-drop '(a b c d e) 2) => (c d e)
</pre>
<p><code>lseq-drop</code> is exactly equivalent to performing <var>i</var> <code>lseq-rest</code> operations on <var>lseq</var>.</p>
<!--
==== lseq-split-at
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-split-at"></a>
<code class="proc-def">lseq-split-at </code><var> lseq i -> [list lseq]</var>
</dt><dd class="proc-def">
<p>Splits the lseq <var>lseq</var>
at index <var>i</var>, returning two values, a list of the
first <var>i</var> elements, and an lseq of the remaining elements. It is equivalent
to</p>
<pre class="code-example">(values (lseq-take lseq i) (lseq-drop lseq i))
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="Whole">The whole lazy sequence</a></h2>
<!--
==== lseq-realize
============================================================================-->
<dl><dt class="proc-def">
<a name="lseq-realize"></a>
<code class="proc-def">lseq-realize</code><var> lseq -> list</var>
</dt><dd class="proc-def">
<p>Repeatedly applies <code>lseq-cdr</code> to <var>lseq</var>
until its generator (if there is one) has been exhausted,
and returns <var>lseq</var>, 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, <code>lseq-realize</code> will never return.</p>
</dd></dl>
<!--
==== lseq->generator
============================================================================-->
<dl><dt class="proc-def">
<a name="lseq->generator"></a>
<code class="proc-def">lseq->generator</code><var> lseq -> generator</var>
</dt><dd class="proc-def">
<p>Returns a generator which when invoked will return all the elements
of <var>lseq</var>, including any that have not yet been realized.</p>
</dd></dl>
<!--
==== lseq-length
============================================================================-->
<dt class="proc-def">
<a name="lseq-length"></a>
<code class="proc-def">lseq-length </code><var>lseq -> integer</var>
</dt><dd class="proc-def">
<p>Returns the length of its argument, which is the non-negative integer <var>n</var> such that <code>lseq-rest</code>
applied <var>n</var> times to the lseq produces an empty lseq.</p>
</dd></dl>
<!--
==== lseq-append
============================================================================-->
<dl>
<dt><code>lseq-append</code><i> lseq …</i></dt>
<dd><p>Returns an lseq that lazily contains all the elements of the <var>lseqs</var>.
</p>
</dd></dl>
<!--
==== lseq-concatenate
============================================================================-->
<dl>
<dt><code>lseq-concatenate</code><i> lseq</i></dt>
<dd><p>The <var>lseq</var> argument is an lseq of lseqs.
Returns an lseq that whose elements are all the elements of the first lseq,
then all the elements of the second one, then the third, etc.
</p>
<p>It is similar to <code>(apply lseq-append (lseq-realize lseq))</code>, except
that <code>lseq-concatenate</code> can work even if <var>lseq</var> contains an infinite
number of lseqs.</p>
</dd></dl>
<dl>
<!--
==== lseq-zip
============================================================================-->
<a name="lseq-zip"></a>
</dd><dt class="proc-def"><code class="proc-def">lseq-zip</code> <var>lseq<sub>1</sub> lseq<sub>2</sub> ... -> lseq</var>
</dt><dd class="proc-def">
<p>If <code>lseq-zip</code> is passed <var>n</var> lseqs, it returns an lseq as long as the shortest
of these lseqs, each element of which is an <var>n</var>-element list comprised
of the corresponding elements from the arguments. The lseqs can be infinite, as long as they are not all infinite.</p>
<pre class="code-example">(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))
</pre>
<!--
==== lseq-unzip5
==== lseq-unzip4
==== lseq-unzip3
==== lseq-unzip2
==== lseq-unzip1
============================================================================-->
<a name="lseq-unzip1"></a>
</dd><dt class="proc-def1"> <code class="proc-def">lseq-unzip1</code><var> list-of-lseqs -> lseq</var>
<a name="lseq-unzip2"></a>
</dt><dt class="proc-defi"> <code class="proc-def">lseq-unzip2</code><var> list-of-lseqs -> [lseq lseq]</var>
<a name="lseq-unzip3"></a>
</dt><dt class="proc-defi"> <code class="proc-def">lseq-unzip3</code><var> list-of-lseqs -> [lseq lseq lseq]</var>
<a name="lseq-unzip4"></a>
</dt><dt class="proc-defi"> <code class="proc-def">lseq-unzip4</code><var> list-of-lseqs -> [lseq lseq lseq lseq]</var>
<a name="lseq-unzip5"></a>
</dt><dt class="proc-defn"> <code class="proc-def">lseq-unzip5</code><var> lslist-of-lseqs -> [lseq lseq lseq lseq lseq]</var>
</dt><dd class="proc-def">
<p><code>lseq-unzip1</code> 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 <code>(lseq-map lseq-first lseqs)</code>.
<code>lseq-unzip2</code> 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. <code>lseq-unzip3</code> does the same for the first
three elements of the lseqs, and so forth.</p>
<pre class="code-example">(lseq-unzip2 (list '(1 one) '(2 two) '(3 three))) =>
(1 2 3)
(one two three)
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="FoldingMapping">Folding and mapping</a></h2>
<dl>
<!--
==== lseq-fold
============================================================================-->
<dt class="proc-def">
<a name="lseq-fold"></a>
<code class="proc-def">lseq-fold</code><var> kons knil lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
<p>The fundamental lseq iterator.
</p><p>
First, consider the single lseq-parameter case. If <var>lseq<sub>1</sub></var> = (<var>e<sub>1</sub></var> <var>e<sub>2</sub></var> ... <var>e<sub>n</sub></var>),
then this procedure returns
</p><div class="indent">
<code>(<var>kons</var> <var>e<sub>n</sub></var> ... (<var>kons</var> <var>e<sub>2</sub></var> (<var>kons</var> <var>e<sub>1</sub></var> <var>knil</var>)) ... )</code>
</div>
<p>That is, it obeys the (tail) recursion</p>
<pre class="code-example">(lseq-fold <var>kons</var> <var>knil</var> <var>lis</var>) = (lseq-fold <var>kons</var> (<var>kons</var> (lseq-first <var>lis</var>) <var>knil</var>) (lseq-last <var>lis</var>))
(lseq-fold <var>kons</var> <var>knil</var> '()) = <var>knil</var>
</pre>
Examples:
<pre class="code-example">(lseq-fold + 0 lseq) ; Add up the elements of lseq.
(lseq-fold cons '() lseq) ; Reverse lseq.
;; How many symbols in lseq?
(lseq-fold (lambda (x count) (if (symbol? x) (+ count 1) count))
0
lseq)
;; Length of the longest string in lseq:
(lseq-fold (lambda (s max-len) (max max-len (string-length s)))
0
lseq)
</pre>
<p>If <var>n</var> lseq arguments are provided, then the <var>kons</var> function must take
<var>n</var>+1 parameters: one element from each lseq, and the "seed" or fold
state, which is initially <var>knil</var>. The fold operation terminates when
the shortest lseq runs out of values:</p>
<pre class="code-example">(lseq-fold lseq* '() '(a b c) '(1 2 3 4 5)) => (c 3 b 2 a 1)
</pre>
<!--
==== lseq-reduce
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-reduce"></a>
<code class="proc-def">lseq-reduce</code><var> f ridentity lseq -> value</var>
</dt><dd class="proc-def">
<p><code>lseq-reduce</code> is a variant of <code>lseq-fold</code>.
</p><p>
<var>ridentity</var> should be a "right identity" of the procedure <var>f</var> — that is,
for any value <var>x</var> acceptable to <var>f</var>,
</p><pre class="code-example">(<var>f</var> <var>x</var> <var>ridentity</var>) = <var>x</var>
</pre>
<p><code>lseq-reduce</code> has the following definition:
<div class="indent">
If <var>lseq</var> = (), return <var>ridentity</var>;<br/>
Otherwise, return <code>(lseq-fold <var>f</var> (lseq-first <var>lseq</var>) (lseq-last <var>lseq</var>))</code>.
</div>
...in other words, we compute
<code>(lseq-fold <var>f</var> <var>ridentity</var> <var>lseq</var>)</code>.</p>
<p>
Note that <var>ridentity</var> is used <em>only</em> in an empty-lseq case.
You typically use <code>lseq-reduce</code> when applying <var>f</var> is expensive and you'd
like to avoid the extra application incurred when <code>lseq-fold</code> applies
<var>f</var> to the head of <var>lseq</var> and the identity value,
redundantly producing the same value passed in to <var>f</var>.
For example, if <var>f</var> involves searching a file directory or
performing a database query, this can be significant.
In general, however, <code>lseq-fold</code> is useful
in many contexts where <code>lseq-reduce</code> is not
(consider the examples given in the <code>lseq-fold</code> definition — only one of the
folds uses a function with a right identity.
The other four may not be performed with <code>lseq-reduce</code>).
</p><pre class="code-example">;; take the max of an lseq of non-negative integers.
(lseq-reduce max 0 nums)
</pre>
<!--
==== lseq-map
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-map"></a>
<code class="proc-def">lseq-map</code><var> proc lseq<sub>1</sub> lseq<sub>2</sub> ... -> lseq</var>
</dt><dd class="proc-def">
<p><var>proc</var> is a procedure taking as many arguments
as there are lseq arguments and returning a single value.
<code>lseq-map</code> applies <var>proc</var> element-wise to the elements
of the lseqs and returns an lseq of the results,
in order.
The dynamic order in which <var>proc</var>
is applied to the elements of the lseqs is unspecified.</p>
<pre class="code-example">(lseq-map lseq-second '((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) <em>or</em> (2 1)
</pre>
<p>
<!--
==== lseq-for-each
==== lseq-pair-for-each
============================================================================-->
</p></dd><dt class="proc-def1">
<a name="lseq-for-each"></a>
<code class="proc-def">lseq-for-each</code><var> proc lseq<sub>1</sub> lseq<sub>2</sub> ... -> unspecified</var>
</dt><dt class="proc-defn">
<a name="lseq-pair-for-each"></a>
<code class="proc-def">lseq-pair-for-each</code><var> proc lseq<sub>1</sub> lseq<sub>2</sub> ... -> unspecified</var>
</dt><dd class="proc-def">
<p>The arguments to <code>lseq-for-each</code> are like the arguments to
<code>lseq-map</code>, but
<code>lseq-for-each</code> calls <var>proc</var> for its side effects rather
than for its values.
Unlike <code>lseq-map</code>, <code>lseq-for-each</code> is guaranteed to call
<var>proc</var> on the elements of the lseqs in order from the first
element(s) to the last,
and the value returned by <code>lseq-for-each</code> is unspecified.</p>
<p>The procedure <code>lseq-pair-for-each</code> is the same as
<code>lseq-for-each</code>, except that it
calls <var>proc</var> on each pair rather than
each element.</p>
<pre class="code-example">(let ((v (make-vector 5)))
(lseq-for-each (lambda (lseq-)
(vector-set! v i (* i i)))
'(0 1 2 3 4))
v) => #(0 1 4 9 16)
</pre>
<p>
</dd></dl>
<!--========================================================================-->
</dd></dl><h2><a name="Searching">Searching</a></h2>
<p>
The following procedures all search lseqs for the leftmost element satisfying
some criteria.
<!--
==== lseq-find
============================================================================-->
<dt class="proc-def">
<a name="lseq-find"></a>
<code class="proc-def">lseq-find</code><var> pred lseq -> value</var>
</dt><dd class="proc-def">
<p>Return the first element of <var>lseq</var> that satisfies predicate <var>pred</var>;
false if no element does.</p>
<pre class="code-example">(lseq-find even? '(3 1 4 1 5 9)) => 4
</pre>
<p>Note that <code>lseq-find</code> has an ambiguity in its lookup semantics — if <code>lseq-find</code>
returns <code>#f</code>, you cannot tell (in general) if it found a <code>#f</code> element
that satisfied <var>pred</var>, 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 <code>#f</code> elements, or the lseq is
guaranteed to have an element satisfying <var>pred</var>. However, in cases
where this ambiguity can arise, you should use <code>lseq-find-tail</code> instead of
<code>lseq-find</code> — <code>lseq-find-tail</code> has no such ambiguity:</p>
<pre class="code-example">(cond ((lseq-find-tail pred lseq) => (lambda (lseq) ...))
(else ...)) ; Search failed.
</pre>
<!--
==== lseq-find-tail
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-find-tail"></a>
<code class="proc-def">lseq-find-tail</code><var> pred lseq -> lseq or false</var>
</dt><dd class="proc-def">
<p>Return the longest tail of <var>lseq</var> whose first element satisfies <var>pred</var>. If no element does,
return false.
</p><p>
<code>lseq-find-tail</code> can be viewed as a general-predicate variant of the <code>lseq-member</code>
function.
</p><p>
Examples:
</p><pre class="code-example">(lseq-find-tail even? '(3 1 37 -8 -5 0 0)) => (-8 -5 0 0)
(lseq-find-tail even? '(3 1 37 -5)) => #f
;; imember x lseq:
(lseq-find-tail (lambda (elt) (equal? x elt)) lseq)
</pre>
<p>
<code>lseq-find-tail</code> is essentially <code>lseq-drop-while</code>,
where the sense of the predicate is inverted:
<code>lseq-find-tail</code> searches until it finds an element satisfying
the predicate; <code>lseq-drop-while</code> searches until it finds an
element that <em>doesn't</em> satisfy the predicate.
<!--
==== lseq-take-while
============================================================================-->
</p></dd><dt class="proc-def">
<a name="lseq-take-while"></a>
<code class="proc-def">lseq-take-while </code><var> pred lseq -> lseq</var>
</dt><dd class="proc-def">
<p>Returns the longest initial prefix of <var>lseq</var> whose elements all
satisfy the predicate <var>pred</var>.</p>
<pre class="code-example">(lseq-take-while even? '(2 18 3 10 22 9)) => (2 18)
</pre>
<!--
==== lseq-drop-while
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-drop-while"></a>
<code class="proc-def">lseq-drop-while</code><var> pred lseq -> lseq</var>
</dt><dd class="proc-def">
<p>Drops the longest initial prefix of <var>lseq</var> whose elements all
satisfy the predicate <var>pred</var>, and returns the rest of the lseq.</p>
<pre class="code-example">(lseq-drop-while even? '(2 18 3 10 22 9)) => (3 10 22 9)
</pre>
<!--
==== lseq-span lseq-break
============================================================================-->
</dd><dt class="proc-def1">
<a name="lseq-span"></a>
<code class="proc-def">lseq-span </code><var> pred lseq -> [lseq lseq]</var>
</dt><dt class="proc-defn">
<a name="lseq-break"></a>
<code class="proc-def">lseq-break </code><var> pred lseq -> [lseq lseq]</var>
</dt><dd class="proc-def">
<p><code>lseq-span</code> splits the lseq into the longest initial prefix whose
elements all satisfy <var>pred</var>, and the remaining tail.
<code>lseq-break</code> inverts the sense of the predicate:
the tail commences with the first element of the input lseq
that satisfies the predicate.</p>
<p>
In other words:
<code>lseq-span</code> finds the initial span of elements
satisfying <var>pred</var>,
and <code>lseq-break</code> breaks the lseq at the first element
satisfying <var>pred</var>.
</p><p>
<code>lseq-span</code> is equivalent to
</p><pre class="code-example">(values (lseq-take-while <var>pred</var> <var>lseq</var>)
(lseq-drop-while <var>pred</var> <var>lseq</var>))
</pre>
<p>
</p><pre class="code-example">(lseq-span even? '(2 18 3 10 22 9)) =>
(2 18)
(3 10 22 9)
(lseq-break even? '(3 1 4 1 5 9)) =>
(3 1)
(4 1 5 9)
</pre>
<!--
==== lseq-any
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-any"></a>
<code class="proc-def">lseq-any</code><var> pred lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
<p>Applies the predicate across the lseqs, returning true if the predicate
returns true on any application.
</p><p>
If there are <var>n</var> lseq arguments <var>lseq<sub>1</sub></var> ... <var>lseq<sub>n</sub></var>, then <var>pred</var> must be a
procedure taking <var>n</var> arguments and returning a boolean result.
</p><p>
<code>lseq-any</code> applies <var>pred</var> to the first elements of the <var>lseq<sub>i</sub></var> parameters.
If this application returns a true value, <code>lseq-any</code> immediately returns
that value. Otherwise, it iterates, applying <var>pred</var> to the second
elements of the <var>lseq<sub>i</sub></var> 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, <code>lseq-any</code> returns <code>#f</code>.
The application of <var>pred</var> to the last element of the
lseqs is a tail call.
</p><p>
Note the difference between <code>lseq-find</code> and <code>lseq-any</code> — <code>lseq-find</code> returns the element
that satisfied the predicate; <code>lseq-any</code> returns the true value that the
predicate produced.
</p><p>
Like <code>lseq-every</code>, <code>lseq-any</code>'s name does not end with a question mark — this is to
indicate that it does not return a simple boolean (<code>#t</code> or <code>#f</code>), but a
general value.
</p><pre class="code-example">(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
</pre>
<!--
==== lseq-every
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-every"></a>
<code class="proc-def">lseq-every</code><var> pred lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
<p>Applies the predicate across the lseqs, returning true if the predicate
returns true on every application.
</p><p>
If there are <var>n</var> lseq arguments <var>lseq<sub>1</sub></var> ... <var>lseq<sub>n</sub></var>, then <var>pred</var> must be a
procedure taking <var>n</var> arguments and returning a boolean result.
</p><p>
<code>lseq-every</code> applies <var>pred</var> to the first elements of the <var>lseq<sub>i</sub></var> parameters.
If this application returns false, <code>lseq-every</code> immediately returns false.
Otherwise, it iterates, applying <var>pred</var> to the second elements of the
<var>lseq<sub>i</sub></var> 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, <code>lseq-every</code> returns
the true value produced by its final application of <var>pred</var>.
The application of <var>pred</var> to the last element of the lseqs
is a tail call.
</p><p>
If one of the <var>lseq<sub>i</sub></var> has no elements, <code>lseq-every</code> simply returns <code>#t</code>.
</p><p>
Like <code>lseq-any</code>, <code>lseq-every</code>'s name does not end with a question mark — this is to
indicate that it does not return a simple boolean (<code>#t</code> or <code>#f</code>), but a
general value.
<!--
==== lseq-index
============================================================================-->
</p></dd><dt class="proc-def">
<a name="lseq-index"></a>
<code class="proc-def">lseq-index</code><var> pred lseq<sub>1</sub> lseq<sub>2</sub> ... -> integer or false</var>
</dt><dd class="proc-def">
<p>Return the index of the leftmost element that satisfies <var>pred</var>.
</p><p>
If there are <var>n</var> lseq arguments <var>lseq<sub>1</sub></var> ... <var>lseq<sub>n</sub></var>, then <var>pred</var> must be a
function taking <var>n</var> arguments and returning a boolean result.
</p><p>
<code>lseq-index</code> applies <var>pred</var> to the first elements of the <var>lseq<sub>i</sub></var> parameters.
If this application returns true, <code>lseq-index</code> immediately returns zero.
Otherwise, it iterates, applying <var>pred</var> to the second elements of the
<var>lseq<sub>i</sub></var> parameters, then the third, and so forth. When it finds a tuple of
lseq elements that cause <var>pred</var> to return true, it stops and returns the
zero-based index of that position in the lseqs.
</p><p>
The iteration stops when one of the lseqs runs out of values; in this
case, <code>lseq-index</code> returns <code>#f</code>.
</p><pre class="code-example">(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
</pre>
<!--
==== lseq-member lseq-memq lseq-memv
============================================================================-->
</dd><dt class="proc-def1">
<a name="lseq-member"></a>
<code class="proc-def">lseq-member</code><var> x lseq [=] -> lseq</var>
</dt><dt class="proc-defi">
<a name="lseq-memq"></a>
<code class="proc-def">lseq-memq</code><var> x lseq -> lseq</var>
</dt><dt class="proc-defn">
<a name="lseq-memv"></a>
<code class="proc-def">lseq-memv</code><var> x lseq -> lseq</var>
</dt><dd class="proc-def">
<p>These procedures return the longest tail of <var>lseq</var> whose first element is
<var>x</var>, where the tails of <var>lseq</var> are the
non-empty lseqs returned by
<code>(lseq-drop <var>lseq</var> <var>i</var>)</code>
for <var>i</var> less than the length of <var>lseq</var>.
If <var>x</var> does
not occur in <var>lseq</var>, then <code>#f</code> is returned.
<code>lseq-memq</code> uses <code>eq?</code> to compare <var>x</var>
with the elements of <var>lseq</var>,
while <code>lseq-memv</code> uses <code>eqv?</code>, and
<code>lseq-member</code> uses <var>=</var>, which defaults to <code>equal?</code>.</p>
<pre class="code-example"> (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 (lseq 'a) '(b (a) c)) => #f
(lseq-member (lseq 'a)
'(b (a) c)) => ((a) c)
(lseq-memq 101 '(100 101 102)) => *unspecified*
(lseq-memv 101 '(100 101 102)) => (101 102)
</pre>
<p>
The comparison procedure is used to compare the elements <var>e<sub>i</sub></var> of <var>lseq</var>
to the key <var>x</var> in this way:
</p><div class="indent"><code>
(= <var>x</var> <var>e<sub>i</sub></var>) ; lseq is (E1 ... En)
</code></div>
<p>That is, the first argument is always <var>x</var>, and the second argument is
one of the lseq elements. Thus one can reliably find the first element
of <var>lseq</var> that is greater than five with
<code>(lseq-member 5 <var>lseq</var> <)</code>
</p><p>
Note that fully general lseq searching may be performed with
the <code>lseq-find-tail</code> and <code>lseq-find</code> procedures, <em>e.g.</em>
</p><pre class="code-example">(lseq-find-tail even? lseq) ; Find the first elt with an even key.
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="LazyAssociationLists">Lazy association lists</a></h2>
<p>
An "lazy association list" (or "lazy alist") is an lseq of pairs. The car of each pair
contains a key value, and the cdr 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.
</p><dl>
<!--
==== lseq-assoc lseq-assq lseq-assv
============================================================================-->
<dt class="proc-def1">
<a name="lseq-assoc"></a>
<code class="proc-def">lseq-assoc</code><var> key lseq-alist [=] -> lseq or #f</var>
</dt><dt class="proc-defi">
<a name="lseq-assq"></a>
<code class="proc-def">lseq-assq</code><var> key lseq-alist -> lseq or #f</var>
</dt><dt class="proc-defn">
<a name="lseq-assv"></a>
<code class="proc-def">lseq-assv</code><var> key lseq-alist -> lseq or #f</var>
</dt><dd class="proc-def">
<p>These procedures
find the first pair in <var>lseq-alist</var> whose car field is <var>key</var>,
and returns that pair.
If no pair in <var>lseq-alist</var> has <var>key</var> as its car,
then <code>#f</code> is returned.
<code>lseq-assq</code> uses <code>eq?</code> to compare <var>key</var>
with the car fields of the ipairs in <var>lseq-alist</var>,
while <code>lseq-assv</code> uses <code>eqv?</code>
and <code>lseq-assoc</code> uses <var>=</var>, which defaults to <code>equal?</code>.</p>
<pre class="code-example">(define e '((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) '(((a)) ((b)) ((c)))) => #f
(lseq-assoc (lseq 'a) '(((a)) ((b)) ((c)))) => ((a))
(lseq-assq 5 '((2 3) (5 7) (11 13))) => *unspecified*
(lseq-assv 5 '((2 3) (5 7) (11 13))) => (5 7)
</pre>
<p>
The comparison procedure is used to compare the elements <var>e<sub>i</sub></var> of <var>lseq</var>
to the <var>key</var> parameter in this way:
</p><div class="indent"><code>
(= <var>key</var> (lseq-first <var>e<sub>i</sub></var>)) ; lseq is (E1 ... En)
</code></div>
That is, the first argument is always <var>key</var>,
and the second argument is one of the lseq elements.
Thus one can reliably find the first entry
of <var>lseq-alist</var> whose key is greater than five with
<code>(lseq-assoc 5 <var>lseq-alist</var> <)</code>
</p><p>
Note that fully general lazy alist searching may be performed with
the <code>lseq-find-tail</code> and <code>lseq-find</code> procedures, <em>e.g.</em>
</p><pre class="code-example">;; Look up the first association in <var>lazy alist</var> with an even key:
(lseq-find (lambda (a) (even? (lseq-first a))) lazy alist)
</pre>
<!--========================================================================-->
<h2><a name="Comparators">Comparators</a></h2>
<dl>
<dt class="proc-def">
<a name="lseq-comparator"></a>
<code class="proc-def">lseq-pair-comparator</code>
</dt><dd class="proc-def">
<p>The <code>lseq-comparator</code> object is a SRFI-114 comparator suitable for comparing lseqs.
Note that it is <em>not</em> a procedure.
It compares lseqs using <code>default-comparator</code> on their first elements. If they are not equal, that value is returned. If they are equal, <code>lseq-comparator</code> is used on the <code>lseq-rest</code> of the lseqs and that value is returned.</p>
</dd>
<dt class="proc-def">
<a name="make-lseq-comparator"></a>
<code class="proc-def">make-lseq-comparator</code><var> comparator -> comparator</var>
</dt><dd class="proc-def">
<p>The <code>make-lseq-comparator</code> procedure returns a comparator suitable for comparing lseqs
using <var>element-comparator</var> to compare the elements.</p>
</dd>
</dl>
<!--========================================================================-->
<h1><a name="SampleImplementation">Sample Implementation</a></h1>
<p>The files in the implementation are as follows:</p>
<p>FIXME</p>
<!--========================================================================-->
<h1><a name="Acknowledgements">Acknowledgements</a></h1>
<p>
Without the work of Olin Shivers on <a href="http://srfi.schemers.org/srfi-1/srfi-1.html">SRFI 1</a>,
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.</p>
<p>Special thanks to Shiro Kawai, whose Gauche implementation of lazy sequences inspired this one.</p>
}}}
time
2015-05-29 01:57:37
version
22