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 2
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><li><a href="#GeneralDiscussion">General discussion</a></li>
<li><a href="#Quotation">Quotation</a></li>
<li><a href="#TheProcedures">The procedures</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="#Miscellaneous">Miscellaneous: length, append, reverse, zip & count</a>
</li><li><a href="#FoldUnfoldMap">Fold, unfold, and map</a>
</li><li><a href="#FilteringPartitioning">Filtering & partitioning</a>
</li><li><a href="#Searching">Searching</a>
</li><li><a href="#Deletion">Deletion</a>
</li><li><a href="#lseq-mmutableassociationLists">Immutable association lists</a>
</li><li><a href="#Replacers">Replacers</a>
</li><li><a href="#Conversion">Conversion</a>
</li><li><a href="#ProcedureApplication">Procedure application</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>
ABSTRACT</p>
<h1><a name="Rationale">Rationale</a></h1>
<p>RATIONALE</p>
<p>
Note: In the prose, lazy sequences are known as lseqs throughout.
</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="#lseq">lseq</a> <a href="#lseq*">lseq*</a> <a href="#list->lseq">list->lseq</a>
<a href="#vector->lseq">vector->lseq</a> <a href="#string->lseq">string->lseq</a> <a href="#generator->lseq">generator->lseq</a>
<a href="#lseq-unfold">lseq-unfold</a> <a href="#lseq-unfold-right">lseq-unfold-right</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="#null-lseq-p">null-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-ref">lseq-ref</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-take">lseq-take</a> <a href="#lseq-drop">lseq-drop</a>
<a href="#lseq-take-right">lseq-take-right</a> <a href="#lseq-drop-right">lseq-drop-right</a>
<a href="#lseq-split-at">isplit-at</a>
</pre>
</dd><dt class="proc-index"> The whole lazy sequence
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq-length">lseq-length</a>
<a href="#lseq-append">lseq-append</a> <a href="#lseq-concatenate">lseq-concatenate</a> <a href="#lseq-reverse">lseq-reverse</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>
<a href="#lseq-count">lseq-count</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-for-each">lseq-for-each</a>
<a href="#lseq-fold">lseq-fold</a> <a href="#lseq-fold-right">lseq-fold-right</a>
<a href="#lseq-fold-subseq">lseq-fold</a> <a href="#lseq-fold-subseq-right">lseq-fold-right</a>
<a href="#lseq-reduce">lseq-reduce</a> <a href="#lseq-reduce-right">lseq-reduce-right</a>
</pre>
</dd><dt class="proc-index"> Filtering and partitioning
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq-filter">lseq-filter</a> <a href="#lseq-partition">lseq-partition</a> <a href="#lseq-remove">lseq-remove</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"> Deleting
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq-delete">lseq-delete</a> <a href="#lseq-delete-neighbor-dups">lseq-delete-neighbor-dups</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>
<a href="#lseq-alist-cons">lseq-alist-cons</a> <a href="#lseq-alist-delete">lseq-alist-delete</a>
</pre>
</dd><dt class="proc-index"> Replacement
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#replace-icar">replace-icar</a> <a href="#replace-icdr">replace-icdr</a>
</pre>
</dd><dt class="proc-index"> Conversion
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq->list">lseq->list</a> <a href="#lseq->vector">lseq-vector</a>
<a href="#lseq->string">lseq->string</a> <a href="lseq->generator">lseq->generator</a>
</pre>
</dd><dt class="proc-index"> Procedure application
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq-apply">iapply</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><dt class="proc-index"> Realization
</dt><dd class="proc-index">
<pre class="proc-index"><a href="#lseq-realize!">lseq-realize!</a> <a href="#lseq-realize-once!">lseq-realize-once!</a>
<a href="#lseq-realize-steps!">lseq-realize-steps!</a> <a href="#lseq-realize-while!">lseq-realize-while!</a>
</pre>
</dd></dl>
</div>
<!--========================================================================-->
<h1><a name="TheProcedures">The procedures</a></h1>
<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 proper (<code>()</code>-terminated) lseq
</td></tr><tr valign="baseline"><th align="left"> <var>lseq</var>
</th><td> A proper or dotted lseq
</td></tr><tr valign="baseline"><th align="left"> <var>ipair</var>
</th><td> An immutable pair
</td></tr><tr valign="baseline">
<th align="left"> <var>x</var>, <var>y</var>, <var>d</var>, <var>a</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>=</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>
<p>
It is an error to pass a dotted lseq to a procedure not
defined to accept such an argument.
<!--========================================================================-->
</p><h2><a name="Constructors">Constructors</a></h2>
<p>
</p><dl>
<!--
==== lseq
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq"></a>
<code class="proc-def">lseq</code> <var>object ... -> lseq</var>
</dt><dd class="proc-def">
Returns a newly allocated lseq of its arguments.
<pre class="code-example">(lseq 'a (+ 3 4) 'c) => (a 7 c)
(lseq) => ()
</pre>
==== lseq*
============================================================================-->
<a name="lseq*"></a>
</dd><dt class="proc-def"><code class="proc-def">lseq*</code><var> elt<sub>1</sub> elt<sub>2</sub> ... -> lseq</var>
</dt><dd class="proc-def">
Like <code>lseq</code>,
but the last argument is an lseq.
</code></div>
<pre class="code-example">(lseq* 1 2 3 (lseq 4)) => (1 2 3 4)
</pre>
<!--
==== list->lseq, vector->lseq, string->lseq, generator->lseq
============================================================================-->
<a name="list->lseq"></a>
</dd><dt class="proc-def1"> <code class="proc-def">list->lseq</code> <var>list -> lseq</var>
<a name="list->lseq"></a>
</dd><dt class="proc-defn"> <code class="proc-def">vector->lseq</code> <var>vector -> lseq</var>
<a name="list->lseq"></a>
</dd><dt class="proc-defn"> <code class="proc-def">list->lseq</code> <var>string -> lseq</var>
<a name="list->lseq"></a>
</dd><dt class="proc-def"> <code class="proc-def">list->lseq</code> <var>generator -> lseq</var>
</dt><dd class="proc-def">
Returns an lseq
whose elements are the elements of <var>list, vector, string</var>,
or the values generated by <var>generator</var>.
<pre class="code-example">(list->lseq '(c c c c c)) => (c c c c)
</pre>
<!--
==== lseq-unfold
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-unfold"></a>
<code class="proc-def">lseq-unfold</code><var> p f g seed [tail-gen] -> lseq</var>
</dt><dd class="proc-def">
<code>lseq-unfold</code> is best described by its basic recursion:
<pre class="code-example">(lseq-unfold <var>p</var> <var>f</var> <var>g</var> <var>seed</var>) =
(if (<var>p</var> <var>seed</var>) (<var>tail-gen</var> <var>seed</var>)
(lseq-pair (<var>f</var> <var>seed</var>)
(lseq-unfold <var>p</var> <var>f</var> <var>g</var> (<var>g</var> <var>seed</var>))))
</pre>
<dl>
<dt> <var>p</var> </dt><dd> Determines when to stop unfolding.
</dd><dt> <var>f</var> </dt><dd> Maps each seed value to the corresponding lseq element.
</dd><dt> <var>g</var> </dt><dd> Maps each seed value to next seed value.
</dd><dt> <var>seed</var> </dt><dd> The "state" value for the unfold.
</dd><dt> <var>tail-gen</var> </dt><dd> Creates the tail of the lseq;
defaults to <code>(lambda (x) '())</code>
</dd></dl>
<p>
In other words, we use <var>g</var> to generate a sequence of seed values
</p><div class="indent">
<var>seed</var>, <var>g</var>(<var>seed</var>), <var>g<sup>2</sup></var>(<var>seed</var>), <var>g<sup>3</sup></var>(<var>seed</var>), ...
</div>
These seed values are mapped to lseq elements by <var>f</var>,
producing the elements of the result lseq in a left-to-right order.
<var>P</var> says when to stop.
<p>
<code>lseq-unfold</code> is the fundamental recursive lseq constructor,
just as <code>lseq-fold-right</code> is
the fundamental recursive lseq consumer.
While <code>lseq-unfold</code> may seem a bit abstract
to novice functional programmers, it can be used in a number of ways:
</p><pre class="code-example">;; 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))
</pre>
Interested functional programmers may enjoy noting that
<code>lseq-fold-right</code> and <code>lseq-unfold</code>
are in some sense inverses.
That is, given operations <var>knull?</var>, <var>kar</var>,
<var>kdr</var>, <var>kons</var>, and <var>knil</var> satisfying
<div class="indent">
<code>(<var>kons</var> (<var>kar</var> <var>x</var>) (<var>kdr</var> <var>x</var>))</code> = <code>x</code>
and
<code>(<var>knull?</var> <var>knil</var>)</code> = <code>#t</code>
</div>
then
<div class="indent">
<code>(lseq-fold-right <var>kons</var> <var>knil</var> (lseq-unfold <var>knull?</var> <var>kar</var> <var>kdr</var> <var>x</var>))</code> = <var>x</var>
</div>
and
<div class="indent">
<code>(lseq-unfold <var>knull?</var> <var>kar</var> <var>kdr</var> (lseq-fold-right <var>kons</var> <var>knil</var> <var>x</var>))</code> = <var>x</var>.
</div>
This combinator sometimes is called an "anamorphism;" when an
explicit <var>tail-gen</var> procedure is supplied, it is called an
"apomorphism."
<!--
==== lseq-unfold-right
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-unfold-right"></a>
<code class="proc-def">iunfold-right</code><var> p f g seed [tail] -> lseq</var>
</dt><dd class="proc-def">
<code>lseq-unfold-right</code> constructs an lseq with the following loop:
<pre class="code-example">(let lp ((seed seed) (lis tail))
(if (p seed) lis
(lp (g seed)
(lseq-pair (f seed) lis))))
</pre>
<dl>
<dt> <var>p</var> </dt><dd> Determines when to stop unfolding.
</dd><dt> <var>f</var> </dt><dd> Maps each seed value to the corresponding lseq element.
</dd><dt> <var>g</var> </dt><dd> Maps each seed value to next seed value.
</dd><dt> <var>seed</var> </dt><dd> The "state" value for the unfold.
</dd><dt> <var>tail</var> </dt><dd> lseq terminator; defaults to <code>'()</code>.
</dd></dl>
<p>
In other words, we use <var>g</var> to generate a sequence of seed values
</p><div class="indent">
<var>seed</var>, <var>g</var>(<var>seed</var>), <var>g<sup>2</sup></var>(<var>seed</var>), <var>g<sup>3</sup></var>(<var>seed</var>), ...
</div>
These seed values are mapped to lseq elements by <var>f</var>,
producing the elements of the result lseq in a right-to-left order.
<var>P</var> says when to stop.
<p>
<code>lseq-unfold-right</code> is the fundamental iterative lseq constructor,
just as <code>lseq-fold</code> is the
fundamental iterative lseq consumer.
While <code>lseq-unfold-right</code> may seem a bit abstract
to novice functional programmers, it can be used in a number of ways:
</p><pre class="code-example">;; 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)
</pre>
Interested functional programmers may enjoy noting that
<code>lseq-fold</code> and <code>lseq-unfold-right</code>
are in some sense inverses.
That is, given operations <var>knull?</var>, <var>kar</var>,
<var>kdr</var>, <var>kons</var>, and <var>knil</var> satisfying
<div class="indent">
<code>(<var>kons</var> (<var>kar</var> <var>x</var>) (<var>kdr</var> <var>x</var>))</code> = <code>x</code>
and
<code>(<var>knull?</var> <var>knil</var>)</code> = <code>#t</code>
</div>
then
<div class="indent">
<code>(lseq-fold <var>kons</var> <var>knil</var> (lseq-unfold-right <var>knull?</var> <var>kar</var> <var>kdr</var> <var>x</var>))</code> = <var>x</var>
</div>
and
<div class="indent">
<code>(lseq-unfold-right <var>knull?</var> <var>kar</var> <var>kdr</var> (lseq-fold <var>kons</var> <var>knil</var> <var>x</var>))</code> = <var>x</var>.
</div>
This combinator presumably has some pretentious mathematical name;
interested readers are invited to communicate it to the author.
<!--========================================================================-->
<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">
True is returned iff <var>x</var> is an lseq.
<!--
==== null-lseq?
============================================================================-->
<a name="null-lseq-p"></a>
</dd><dt class="proc-def"><code class="proc-def">null-lseq?</code><var> lseq -> boolean</var>
</dt><dd class="proc-def">
This procedure returns true if
the argument is the empty lseq, and false otherwise.
<!--
==== 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">
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>
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>
Note that 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>
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.
<pre class="code-example">(lseq= eq?) => #t ; Trivial cases
(lseq= eq? (lseq-q a)) => #t
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="Selectors">Selectors</a></h2>
<dl>
<!--
==== lseq-tenth
==== lseq-ninth
==== lseq-eighth
==== lseq-seventh
==== lseq-sixth
==== lseq-fifth
==== lseq-fourth
==== lseq-third
==== lseq-second
==== lseq-first
============================================================================-->
</dd><dt class="proc-def1">
<a name="lseq-first"></a>
<code class="proc-def">ifirst </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-second"></a>
<code class="proc-def">isecond </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-third"></a>
<code class="proc-def">ithird </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-fourth"></a>
<code class="proc-def">ifourth </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-fifth"></a>
<code class="proc-def">ififth </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-sixth"></a>
<code class="proc-def">isixth </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-seventh"></a>
<code class="proc-def">iseventh </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-eighth"></a>
<code class="proc-def">ieighth </code><var>lseq -> object </var>
</dt><dt class="proc-defi">
<a name="lseq-ninth"></a>
<code class="proc-def">ininth </code><var>lseq -> object </var>
</dt><dt class="proc-defn">
<a name="lseq-tenth"></a>
<code class="proc-def">itenth </code><var>lseq -> object </var>
</dt><dd class="proc-def">
Returns the first, second, ..., tenth element of <var>lseq</var>.
<pre class="code-example">(lseq-third (lq a b c d e)) => c
</pre>
<!--
==== lseq-rest
============================================================================-->
<a name="lseq-rest"></a>
<dt class="proc-def"><code class="proc-def">lseq-last</code><var> lseq -> lseq</var>
</dt><dd class="proc-def">
This procedure returns an lseq with the contents of <var>lseq</i> except for the
first element.
Note that it is an error to apply it to the empty lseq.
<pre class="code-example">(lseq-car (lseq-q a b c)) => a (lseq-cdr (lseq-q a b c)) => (b c)
(lseq-car (lseq-q (a) b c d)) => (a) (lseq-cdr (lseq-q (a) b c d)) => (b c d)
(lseq-car (lseq-pair 1 2)) => 1 (lseq-cdr (lseq-pair 1 2)) => 2
(lseq-car '()) => *error* (lseq-cdr '()) => *error*
</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">
Returns the <var>i</var><sup>th</sup> 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>.
<pre class="code-example">
(lseq-ref (lq 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 -> lseq</var>
</dt><dt class="proc-defi">
<a name="lseq-drop"></a>
<code class="proc-def">lseq-drop</code><var> lseq i -> object</var>
</dt><dt class="proc-def">
</dt><dd class="proc-def">
<code>lseq-take</code> returns the first <var>i</var> elements of <var>lseq</var>.<br/>
<code>lseq-drop</code> returns all but the first <var>i</var> elements of <var>lseq</var>.<br/>
<pre class="code-example">(lseq-take (lq a b c d e) 2) => (a b)
(lseq-drop (lq a b c d e) 2) => (c d e)
</pre>
For a legal <var>i</var>, <code>lseq-take</code> and <code>lseq-drop</code> partition <var>lseq</var> in a manner which
can be inverted with <code>lseq-append</code>:
<pre class="code-example">(lseq-append (lseq-take <var>lseq</var> <var>i</var>) (lseq-drop <var>lseq</var> <var>i</var>)) = <var>lseq</var>
</pre>
<code>lseq-drop</code> is exactly equivalent to performing <var>i</var> <code>lseq-rest</code> operations on <var>lseq</var>.
<!--
==== lseq-drop-right
==== lseq-take-right
============================================================================-->
</dd><dt class="proc-def1">
<a name="lseq-take-right"></a>
<code class="proc-def">lseq-take-right</code><var> lseq i -> object</var>
</dt><dt class="proc-defn">
<a name="lseq-drop-right"></a>
<code class="proc-def">lseq-drop-right</code><var> lseq i -> lseq</var>
</dt><dd class="proc-def">
<code>lseq-take-right</code> returns the last <var>i</var> elements of <var>lseq</var>.<br/>
<code>lseq-drop-right</code> returns all but the last <var>i</var> elements of <var>lseq</var>.
<pre class="code-example">(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)
</pre>
For a legal <var>i</var>, <code>lseq-take-right</code> and <code>lseq-drop-right</code> partition <var>lseq</var> in a manner
which can be inverted with <code>lseq-append</code>:
<pre class="code-example">(lseq-append (lseq-take <var>lseq</var> <var>i</var>) (lseq-drop <var>lseq</var> <var>i</var>)) = <var>lseq</var>
</pre>
<code>lseq-take-right</code>'s return value is guaranteed to share a common tail with <var>lseq</var>.
<!--
==== lseq-split-at
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-split-at"></a>
<code class="proc-def">isplit-at </code><var> lseq i -> [lseq object]</var>
</dt><dd class="proc-def">
<code>lseq-split-at</code> splits the lseq <var>lseq</var>
at index <var>i</var>, returning two values, an lseq of the
first <var>i</var> elements, and an lseq of the remaining tail. It is equivalent
to
<pre class="code-example">(values (lseq-take lseq i) (lseq-drop lseq i))
</pre>
<!--
==== last-ipair
==== lseq-last
============================================================================-->
</dd><dt class="proc-def1">
<a name="lseq-last"></a>
<code class="proc-def">ilast</code><var> ipair -> object</var>
</dt><dt class="proc-defn">
<a name="last-ipair"></a>
<code class="proc-def">last-ipair</code><var> ipair -> ipair</var>
</dt><dd class="proc-def">
Returns the last element of the non-empty, possibly dotted, lseq <var>ipair</var>.
<code>last-ipair</code> returns the last ipair in the non-empty
lseq <var>pair</var>.
<pre class="code-example">(lseq-last (lseq-q a b c)) => c
(last-ipair (lseq-q a b c)) => (c)
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="Miscellaneous">Miscellaneous: length, append, concatenate, reverse, zip & count</a></h2>
<dl>
<!--
==== lseq-length
============================================================================-->
<dt class="proc-def">
<a name="lseq-length"></a>
<code class="proc-def">ilength </code><var>lseq -> integer</var>
</dt><dd class="proc-def">
Returns the length of its argument.
It is an error to pass a value to <code>lseq-length</code> which is not a proper
lseq (<code>()</code>-terminated).<p>
The length of a proper lseq is a non-negative integer <var>n</var> such that <code>lseq-cdr</code>
applied <var>n</var> times to the lseq produces the empty list.
<!--
==== lseq-append
============================================================================-->
</p></dd><dt class="proc-def">
<a name="lseq-append"></a>
<code class="proc-def">iappend </code><var> lseq<sub>1</sub> ... -> lseq</var>
</dt><dd class="proc-def">
Returns an lseq consisting of the elements
of <var>lseq<sub>1</sub></var>
followed by the elements of the other lseq parameters.
<pre class="code-example">(lseq-append (lseq-q x) (lseq-q y)) => (x y)
(lseq-append (lseq-q a) (lseq-q b c d)) => (a b c d)
(lseq-append (lseq-q a (b)) (lseq-q (c))) => (a (b) (c))
</pre>
The resulting lseq is always newly allocated, except that it
shares structure with the final <var>lseq<sub>i</sub></var> 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.
<pre class="code-example">(lseq-append (lseq-q a b) (lseq-pair 'c 'd)) => (a b c . d)
(lseq-append '() 'a) => a
(lseq-append (lseq-q x y)) => (x y)
(lseq-append) => ()
</pre>
<!--
==== lseq-concatenate
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-concatenate"></a>
<code class="proc-def">iconcatenate </code><var> lseq-of-lseqs -> value</var>
</dt><dd class="proc-def">
Appends the elements of its argument together.
That is, <code>lseq-concatenate</code> returns
<pre class="code-example">(lseq-apply iappend lseq-of-lseqs)
</pre>
or, equivalently,
<pre class="code-example">(lseq-reduce-right iappend '() lseq-of-lseqs)
</pre>
<p>
Note that some Scheme implementations do not support passing more than a
certain number (<em>e.g.</em>, 64) of arguments to an n-ary procedure.
In these implementations, the <code>(lseq-apply iappend ...)</code> idiom
would fail when applied to long lists,
but <code>lseq-concatenate</code> would continue to function properly.
</p><p>
As with <code>lseq-append</code>,
the last element of the input list may be any value at all.
<!--
==== lseq-reverse
============================================================================-->
</p></dd><dt class="proc-def">
<a name="lseq-reverse"></a>
<code class="proc-def">ireverse </code><var> lseq -> lseq</var>
</dt><dd class="proc-def">
Returns a newly allocated lseq consisting of
the elements of <var>lseq</var> in reverse order.
<pre class="code-example">(lseq-reverse (lseq-q a b c)) => (c b a)
(lseq-reverse (lseq-q a (b c) d (e (f))))
=> ((e (f)) d (b c) a)
</pre>
<!--
==== lseq-append-reverse
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-append-reverse"></a>
<code class="proc-def">iappend-reverse </code><var>rev-head tail -> lseq</var>
</dt><dd class="proc-def">
<code>lseq-append-reverse</code> returns
<code>(lseq-append (lseq-reverse <var>rev-head</var>) <var>tail</var>)</code>.
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 <code>reverse</code> and <code>lseq-append-reverse</code> 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
============================================================================-->
<a name="lseq-zip"></a>
</dd><dt class="proc-def"><code class="proc-def">izip</code> <var>lseq<sub>1</sub> lseq<sub>2</sub> ... -> lseq</var>
</dt><dd class="proc-def">
<pre>(lambda lseqs (lseq-apply imap lseq lseqs))
</pre>
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 lseq comprised
of the corresponding elements from the parameter lseqs.
<pre class="code-example">(lseq-zip (lseq-q one two three)
(lseq-q 1 2 3)
(lseq-q odd even odd even odd even odd even))
=> ((one 1 odd) (two 2 even) (three 3 odd))
(lseq-zip (lseq-q 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">iunzip1</code><var> lseq -> lseq</var>
<a name="lseq-unzip2"></a>
</dt><dt class="proc-defi"> <code class="proc-def">iunzip2</code><var> lseq -> [lseq lseq]</var>
<a name="lseq-unzip3"></a>
</dt><dt class="proc-defi"> <code class="proc-def">iunzip3</code><var> lseq -> [lseq lseq lseq]</var>
<a name="lseq-unzip4"></a>
</dt><dt class="proc-defi"> <code class="proc-def">iunzip4</code><var> lseq -> [lseq lseq lseq lseq]</var>
<a name="lseq-unzip5"></a>
</dt><dt class="proc-defn"> <code class="proc-def">iunzip5</code><var> lseq -> [lseq lseq lseq lseq lseq]</var>
</dt><dd class="proc-def">
<code>lseq-unzip1</code> 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 <code>(lseq-map icar lseqs)</code>.
<code>lseq-unzip2</code> 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. <code>lseq-unzip3</code> does the same for the first
three elements of the lseqs, and so forth.
<pre class="code-example">(lseq-unzip2 (lseq-q (1 one) (2 two) (3 three))) =>
(1 2 3)
(one two three)
</pre>
<!--
==== lseq-count
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-count"></a>
<code class="proc-def">icount</code><var> pred lseq<sub>1</sub> lseq<sub>2</sub> ... -> integer</var>
</dt><dd class="proc-def">
<var>pred</var> 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 <var>lseq</var>s, and a count is
tallied of the number of elements that produce a true value. This count
is returned. <code>count</code> is "iterative" in that it is guaranteed
to apply <var>pred</var> to the <var>lseq</var> elements in a
left-to-right order.
The counting stops when the shortest lseq expires.
<pre class="code-example">(count even? (lseq-q 3 1 4 1 5 9 2 5 6)) => 3
(count < (lseq-q 1 2 4 8) (lseq-q 2 4 6 8 10 12 14 16)) => 3
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="FoldUnfoldMap">Fold, unfold & map</a></h2>
<dl>
<!--
==== lseq-fold
============================================================================-->
<dt class="proc-def">
<a name="lseq-fold"></a>
<code class="proc-def">ifold</code><var> kons knil lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
The fundamental lseq iterator.
<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>
That is, it obeys the (tail) recursion
<pre class="code-example">(lseq-fold <var>kons</var> <var>knil</var> <var>lis</var>) = (lseq-fold <var>kons</var> (<var>kons</var> (lseq-car <var>lis</var>) <var>knil</var>) (lseq-cdr <var>lis</var>))
(lseq-fold <var>kons</var> <var>knil</var> '()) = <var>knil</var>
</pre>
Examples:
<pre class="code-example">(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)
</pre>
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:
<pre class="code-example">(lseq-fold ipair* '() (lseq-q a b c) (lseq-q 1 2 3 4 5)) => (c 3 b 2 a 1)
</pre>
<!--
==== lseq-fold-right
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-fold-right"></a>
<code class="proc-def">ifold-right</code><var> kons knil lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
The fundamental lseq recursion operator.
<p>
First, consider the single lseq-parameter case. If <var>lseq<sub>1</sub></var> = <code>(<var>e<sub>1</sub></var> <var>e<sub>2</sub></var> ... <var>e<sub>n</sub></var>)</code>,
then this procedure returns
</p><div class="indent"><code>
(<var>kons</var> <var>e<sub>1</sub></var> (<var>kons</var> <var>e<sub>2</sub></var> ... (<var>kons</var> <var>e<sub>n</sub></var> <var>knil</var>)))
</code></div>
That is, it obeys the recursion
<pre class="code-example">(lseq-fold-right <var>kons</var> <var>knil</var> <var>lis</var>) = (<var>kons</var> (lseq-car <var>lis</var>) (lseq-fold-right <var>kons</var> <var>knil</var> (lseq-cdr <var>lis</var>)))
(lseq-fold-right <var>kons</var> <var>knil</var> '()) = <var>knil</var>
</pre>
Examples:
<pre class="code-example">(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))
</pre>
If <var>n</var> lseq arguments are provided, then the <var>kons</var> procedure 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:
<pre class="code-example">(lseq-fold-right ipair* '() (lseq-q a b c) (lseq-q 1 2 3 4 5)) => (a 1 b 2 c 3)
</pre>
<!--
==== lseq-pair-fold
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-pair-fold"></a>
<code class="proc-def">ipair-fold</code><var> kons knil lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
Analogous to <code>fold</code>, but <var>kons</var> is applied to successive sub-lseqs of the
lseqs, rather than successive elements — that is, <var>kons</var> is applied to the
ipairs making up the lists, giving this (tail) recursion:
<pre class="code-example">(lseq-pair-fold <var>kons</var> <var>knil</var> <var>lis</var>) = (let ((tail (lseq-cdr <var>lis</var>)))
(lseq-pair-fold <var>kons</var> (<var>kons</var> <var>lis</var> <var>knil</var>) tail))
(lseq-pair-fold <var>kons</var> <var>knil</var> <code>'()</code>) = <var>knil</var>
</pre>
<p>
Example:
</p><pre class="code-example">(lseq-pair-fold ipair '() (lseq-q a b c)) => ((c) (b c) (a b c))
</pre>
<!--
==== lseq-pair-fold-right
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-pair-fold-right"></a>
<code class="proc-def">ipair-fold-right</code><var> kons knil lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
Holds the same relationship with <code>lseq-fold-right</code> that <code>lseq-pair-fold</code> holds with <code>lseq-fold</code>.
Obeys the recursion
<pre class="code-example">(lseq-pair-fold-right <var>kons</var> <var>knil</var> <var>lis</var>) =
(<var>kons</var> <var>lis</var> (lseq-pair-fold-right <var>kons</var> <var>knil</var> (lseq-cdr <var>lis</var>)))
(lseq-pair-fold-right <var>kons</var> <var>knil</var> <code>'()</code>) = <var>knil</var>
</pre>
Example:
<pre class="code-example">(lseq-pair-fold-right ipair '() (lseq-q a b c)) => ((a b c) (b c) (c))
</pre>
<!--
==== lseq-reduce
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-reduce"></a>
<code class="proc-def">ireduce</code><var> f ridentity lseq -> value</var>
</dt><dd class="proc-def">
<code>lseq-reduce</code> is a variant of <code>lseq-fold</code>.
<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>
<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-car <var>lseq</var>) (lseq-cdr <var>lseq</var>))</code>.
</div>
...in other words, we compute
<code>(lseq-fold <var>f</var> <var>ridentity</var> <var>lseq</var>)</code>.
<p>
Note that <var>ridentity</var> is used <em>only</em> in the empty-list 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
five 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) ; i.e., (lseq-apply max 0 nums)
</pre>
<!--
==== lseq-reduce-right
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-reduce-right"></a>
<code class="proc-def">ireduce-right</code><var> f ridentity lseq -> value</var>
</dt><dd class="proc-def">
<code>lseq-reduce-right</code> is the fold-right variant of <code>lseq-reduce</code>.
It obeys the following definition:
<pre class="code-example">(lseq-reduce-right <var>f</var> <var>ridentity</var> '()) = <var>ridentity</var>
(lseq-reduce-right <var>f</var> <var>ridentity</var> (lseq-q <var>e<sub>1</sub></var>)) = (<var>f</var> <var>e<sub>1</sub></var> <var>ridentity</var>) = <var>e<sub>1</sub></var>
(lseq-reduce-right <var>f</var> <var>ridentity</var> (lseq-q <var>e<sub>1</sub></var> <var>e<sub>2</sub></var> ...)) =
(<var>f</var> <var>e<sub>1</sub></var> (lseq-reduce <var>f</var> <var>ridentity</var> (<var>e<sub>2</sub></var> ...)))
</pre>
...in other words, we compute
<code>(lseq-fold-right <var>f</var> <var>ridentity</var> <var>lseq</var>)</code>.
<pre class="code-example">;; Append a bunch of lseqs together.
;; I.e., (lseq-apply iappend lseq-of-lseqs)
(lseq-reduce-right iappend '() lseq-of-lseqs)
</pre>
<!--
==== lseq-map
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-map"></a>
<code class="proc-def">imap</code><var> proc lseq<sub>1</sub> lseq<sub>2</sub> ... -> lseq</var>
</dt><dd class="proc-def">
<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.
<pre class="code-example">(lseq-map icadr (lseq-q (a b) (d e) (g h))) => (b e h)
(lseq-map (lambda (n) (expt n n))
(lseq-q 1 2 3 4 5))
=> (1 4 27 256 3125)
(lseq-map + (lseq-q 1 2 3) (lseq-q 4 5 6)) => (5 7 9)
(let ((count 0))
(lseq-map (lambda (lseq-gnored)
(set! count (+ count 1))
count)
(lseq-q a b))) => (1 2) <em>or</em> (2 1)
</pre>
<p>
<!--
==== lseq-for-each
============================================================================-->
</p></dd><dt class="proc-def">
<a name="lseq-for-each"></a>
<code class="proc-def">ifor-each</code><var> proc lseq<sub>1</sub> lseq<sub>2</sub> ... -> unspecified</var>
</dt><dd class="proc-def">
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.
<pre class="code-example">(let ((v (make-vector 5)))
(lseq-for-each (lambda (lseq-)
(vector-set! v i (* i i)))
(lseq-q 0 1 2 3 4))
v) => #(0 1 4 9 16)
</pre>
<p>
<!--
==== lseq-append-map
============================================================================-->
</p></dd><dt class="proc-def">
<a name="lseq-append-map"></a>
<code class="proc-def">iappend-map </code><var>f lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
Equivalent to
<div class="indent"><code>
(lseq-apply iappend (lseq-map <var>f</var> <var>lseq<sub>1</sub></var> <var>lseq<sub>2</sub></var> ...))
</code></div>
and
<div class="indent"><code>
(lseq-apply iappend (lseq-map <var>f</var> <var>lseq<sub>1</sub></var> <var>lseq<sub>2</sub></var> ...))
</code></div>
Map <var>f</var> over the elements of the lseqs, just as in the <code>lseq-map</code> function.
However, the results of the applications are appended together (using <code>lseq-append</code>) to
make the final result.
<p>
The dynamic order in which the various applications of <var>f</var> are made is
not specified.
</p><p>
Example:
</p><pre class="code-example">(lseq-append-map (lambda (x) (lseq x (- x))) (lseq-q 1 3 8))
=> (1 -1 3 -3 8 -8)
</pre>
<!--
==== lseq-map-in-order
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-map-in-order"></a>
<code class="proc-def">imap-in-order </code><var>f</var> <var>lseq<sub>1</sub> lseq<sub>2</sub> ... -> lseq</var>
</dt><dd class="proc-def">
A variant of the <code>lseq-map</code> procedure that guarantees to apply <var>f</var> across
the elements of the <var>lseq<sub>i</sub></var> arguments in a left-to-right order. This
is useful for mapping procedures that both have side effects and
return useful values.
<p>
<!--
==== lseq-pair-for-each
============================================================================-->
</p></dd><dt class="proc-def">
<a name="lseq-pair-for-each"></a>
<code class="proc-def">ipair-for-each </code><var>f lseq<sub>1</sub> lseq<sub>2</sub> ... -> unspecific</var>
</dt><dd class="proc-def">
Like <code>lseq-for-each</code>, but <var>f</var> is applied to successive sub-lseqs of the argument
lseqs. That is, <var>f</var> is applied to the cells of the lseqs, rather
than the lseqs' elements. These applications occur in left-to-right
order.
<pre class="code-example">(lseq-pair-for-each (lambda (lseq-pair) (display ipair) (newline)) (lseq-q a b c)) ==>
(a b c)
(b c)
(c)
</pre>
<!--
==== lseq-filter-map
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-filter-map"></a>
<code class="proc-def">ifilter-map</code><var> f lseq<sub>1</sub> lseq<sub>2</sub> ... -> lseq</var>
</dt><dd class="proc-def">
Like <code>lseq-map</code>, but only true values are saved.
<pre class="code-example">(lseq-filter-map (lambda (x) (and (number? x) (* x x))) (lseq-q a 1 b 3 c 7))
=> (1 9 49)
</pre>
The dynamic order in which the various applications of <var>f</var> are made is
not specified.
<p>
</p></dd></dl>
<!--========================================================================-->
<h2><a name="FilteringPartitioning">Filtering & partitioning</a></h2>
<dl>
<!--
==== lseq-filter
============================================================================-->
<dt class="proc-def">
<a name="lseq-filter"></a>
<code class="proc-def">ifilter</code><var> pred lseq -> lseq</var>
</dt><dd class="proc-def">
Return all the elements of <var>lseq</var> that satisfy predicate <var>pred</var>.
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 <var>pred</var> are made is
not specified.
<pre class="code-example">(lseq-filter even? (lseq-q 0 7 8 8 43 -4)) => (0 8 8 -4)
</pre>
<!--
==== lseq-partition
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-partition"></a>
<code class="proc-def">ipartition</code><var> pred lseq -> [lseq lseq]</var>
</dt><dd class="proc-def">
Partitions the elements of <var>lseq</var> with predicate <var>pred</var>, 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 <var>pred</var> are made is
not specified. One of the returned lseqs may share a common tail with the
argument lseq.
<pre class="code-example">(lseq-partition symbol? (lseq-q one 2 3 four five 6)) =>
(one four five)
(2 3 6)
</pre>
<!--
==== lseq-remove
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-remove"></a>
<code class="proc-def">iremove</code><var> pred lseq -> lseq</var>
</dt><dd class="proc-def">
Returns <var>lseq</var> without the elements that satisfy predicate <var>pred</var>:
<pre class="code-example">(lambda (pred lseq) (lseq-filter (lambda (x) (not (pred x))) lseq))
</pre>
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 <var>pred</var> are made is
not specified.
<pre class="code-example">(lseq-remove even? (lseq-q 0 7 8 8 43 -4)) => (7 43)
</pre>
<!--========================================================================-->
</dd></dl><h2><a name="Searching">Searching</a></h2>
<p>
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:
</p><dl>
<dt> Proper lseqs:
</dt><dd> The standard, canonical behavior happens in this case.
</dd><dt> Dotted lseqs:
</dt><dd> 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 <em>not</em> 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.
<p>
In brief, compliant code may not pass a dotted
lseq argument to these procedures.
</p></dd></dl>
<p>
Here are some examples, using the <code>lseq-find</code> and <code>lseq-any</code> procedures as canonical
representatives:
</p><pre class="code-example">;; Proper lseq — success
(lseq-find even? (lseq-q 1 2 3)) => 2
(lseq-any even? (lseq-q 1 2 3)) => #t
;; proper lseq — failure
(lseq-find even? (lseq-q 1 7 3)) => #f
(lseq-any even? (lseq-q 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.
</pre>
<dl>
<!--
==== lseq-find
============================================================================-->
<dt class="proc-def">
<a name="lseq-find"></a>
<code class="proc-def">ifind</code><var> pred lseq -> value</var>
</dt><dd class="proc-def">
Return the first element of <var>lseq</var> that satisfies predicate <var>pred</var>;
false if no element does.
<pre class="code-example">(lseq-find even? (lseq-q 3 1 4 1 5 9)) => 4
</pre>
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 (lseq-n 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:
<pre class="code-example">(cond ((lseq-find-tail pred lis) => (lambda (lseq-pair) ...)) ; Handle (lseq-car ipair)
(else ...)) ; Search failed.
</pre>
<!--
==== lseq-find-tail
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-find-tail"></a>
<code class="proc-def">ifind-tail</code><var> pred lseq -> ipair or false</var>
</dt><dd class="proc-def">
Return the first ipair of <var>lseq</var> whose icar satisfies <var>pred</var>. If no ipair does,
return false.
<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? (lseq-q 3 1 37 -8 -5 0 0)) => (-8 -5 0 0)
(lseq-find-tail even? (lseq-q 3 1 37 -5)) => #f
;; IMEMBER X LIS:
(lseq-find-tail (lambda (elt) (equal? x elt)) lis)
</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">itake-while </code><var> pred lseq -> lseq</var>
</dt><dd class="proc-def">
Returns the longest initial prefix of <var>lseq</var> whose elements all
satisfy the predicate <var>pred</var>.
<p>
</p><pre class="code-example">(lseq-take-while even? (lseq-q 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">idrop-while</code><var> pred lseq -> lseq</var>
</dt><dd class="proc-def">
idrops the longest initial prefix of <var>lseq</var> whose elements all
satisfy the predicate <var>pred</var>, and returns the rest of the lseq.
<pre class="code-example">(lseq-drop-while even? (lseq-q 2 18 3 10 22 9)) => (3 10 22 9)
</pre>
<!--
==== lseq-span ibreak
============================================================================-->
</dd><dt class="proc-def1">
<a name="lseq-span"></a>
<code class="proc-def">ispan </code><var> pred lseq -> [lseq lseq]</var>
</dt><dt class="proc-defn">
<a name="lseq-break"></a>
<code class="proc-def">ibreak </code><var> pred lseq -> [lseq lseq]</var>
</dt><dd class="proc-def">
<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>
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? (lseq-q 2 18 3 10 22 9)) =>
(2 18)
(3 10 22 9)
(lseq-break even? (lseq-q 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">iany</code><var> pred lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
Applies the predicate across the lseqs, returning true if the predicate
returns true on any application.
<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? (lseq-q a 3 b 2.7)) => #t
(lseq-any integer? (lseq-q a 3.1 b 2.7)) => #f
(lseq-any < (lseq-q 3 1 4 1 5)
(lseq-q 2 7 1 8 2)) => #t
</pre>
<!--
==== lseq-every
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-every"></a>
<code class="proc-def">ievery</code><var> pred lseq<sub>1</sub> lseq<sub>2</sub> ... -> value</var>
</dt><dd class="proc-def">
Applies the predicate across the lseqs, returning true if the predicate
returns true on every application.
<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">
Return the index of the leftmost element that satisfies <var>pred</var>.
<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? (lseq-q 3 1 4 1 5 9)) => 2
(lseq-index < (lseq-q 3 1 4 1 5 9 2 5 6) (lseq-q 2 7 1 8 2)) => 1
(lseq-index = (lseq-q 3 1 4 1 5 9 2 5 6) (lseq-q 2 7 1 8 2)) => #f
</pre>
<!--
==== lseq-member imemq imemv
============================================================================-->
</dd><dt class="proc-def1">
<a name="lseq-member"></a>
<code class="proc-def">imember</code><var> x lseq [=] -> lseq</var>
</dt><dt class="proc-defi">
<a name="lseq-memq"></a>
<code class="proc-def">imemq</code><var> x lseq -> lseq</var>
</dt><dt class="proc-defn">
<a name="lseq-memv"></a>
<code class="proc-def">imemv</code><var> x lseq -> lseq</var>
</dt><dd class="proc-def">
These procedures return the first sub-lseq of <var>lseq</var> whose icar is
<var>x</var>, where the sub-lseqs 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 <code>equal?</code>.
<pre class="code-example"> (lseq-memq 'a (lseq-q a b c)) => (a b c)
(lseq-memq 'b (lseq-q a b c)) => (b c)
(lseq-memq 'a (lseq-q b c d)) => #f
(lseq-memq (lseq 'a) (lseq-q b (a) c)) => #f
(lseq-member (lseq 'a)
(lseq-q b (a) c)) => ((a) c)
(lseq-memq 101 (lseq-q 100 101 102)) => *unspecified*
(lseq-memv 101 (lseq-q 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>
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>
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="Deletion">Deletion</a></h2>
<p>
</p><dl>
<!--
==== lseq-delete
============================================================================-->
<dt class="proc-def">
<a name="lseq-delete"></a>
<code class="proc-def">idelete </code><var>x lseq [=] -> lseq</var>
</dt><dd class="proc-def">
<code>lseq-delete</code> uses the comparison procedure =, which defaults to <code>equal?</code>, to find
all elements of <var>lseq</var> that are equal to <var>x</var>, and deletes them from <var>lseq</var>. The
dynamic order in which the various applications of <var>=</var> are made is not
specified.
<p>
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.
</p><p>
Note that fully general element deletion can be performed with the <code>lseq-remove</code>
procedures, <em>e.g.</em>:
</p><pre class="code-example">;; idelete all the even elements from LIS:
(lseq-remove even? lis)
</pre>
The comparison procedure is used in this way:
<code>(= <var>x</var> <var>e<sub>i</sub></var>)</code>.
That is, <var>x</var> 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 <var>lseq</var> exactly once; the order in which it is applied to the
various <var>e<sub>i</sub></var> is not specified. Thus, one can reliably remove all the
numbers greater than five from an lseq with
<code>(lseq-delete 5 lseq <)</code>
<!--
==== lseq-delete-duplicates
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-delete-duplicates"></a>
<code class="proc-def">idelete-duplicates </code><var>lseq [=] -> lseq</var>
</dt><dd class="proc-def">
<code>lseq-delete-duplicates</code> 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 — <code>lseq-delete-duplicates</code> does not disorder the lseq (hence it is useful
for "cleaning up" immutable association lists).
<p>
The <var>=</var> parameter is used to compare the elements of the lseq; it defaults
to <code>equal?</code>. If <var>x</var> comes before <var>y</var> in <var>lseq</var>, then the comparison is performed
<code>(= <var>x</var> <var>y</var>)</code>.
The comparison procedure will be used to compare each pair of elements in
<var>lseq</var> no more than once;
the order in which it is applied to the various pairs is not specified.
</p><p>
Implementations of <code>lseq-delete-duplicates</code>
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.
</p><p>
Be aware that, in general, <code>lseq-delete-duplicates</code>
runs in time O(n<sup>2</sup>) for <var>n</var>-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.
</p><pre class="code-example">(lseq-delete-duplicates (lseq-q a b a c a b c z)) => (a b c z)
;; Clean up an ialist:
(lseq-delete-duplicates (lseq-q (a . 3) (b . 7) (a . 9) (c . 1))
(lambda (x y) (eq? (lseq-car x) (lseq-car y))))
=> ((a . 3) (b . 7) (c . 1))
</pre>
</dd></dl>
<!--========================================================================-->
<h2><a name="lseq-mmutableassociationLists">Immutable association lists</a></h2>
<p>
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.
</p><dl>
<!--
==== lseq-assoc iassq iassv
============================================================================-->
<dt class="proc-def1">
<a name="lseq-assoc"></a>
<code class="proc-def">iassoc</code><var> key ialist [=] -> ipair or #f</var>
</dt><dt class="proc-defi">
<a name="lseq-assq"></a>
<code class="proc-def">iassq</code><var> key ialist -> ipair or #f</var>
</dt><dt class="proc-defn">
<a name="lseq-assv"></a>
<code class="proc-def">iassv</code><var> key ialist -> ipair or #f</var>
</dt><dd class="proc-def">
<var>ialist</var> must be an immutable association list — an lseq of ipairs.
These procedures
find the first ipair in <var>ialist</var> whose icar field is <var>key</var>,
and returns that ipair.
If no ipair in <var>ialist</var> has <var>key</var> as its icar,
then <code>#f</code> is returned.
<code>lseq-assq</code> uses <code>eq?</code> to compare <var>key</var>
with the icar fields of the ipairs in <var>ialist</var>,
while <code>lseq-assv</code> uses <code>eqv?</code>
and <code>lseq-assoc</code> uses <code>equal?</code>.
<pre class="code-example">(define e (lseq-q (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) (lseq-q ((a)) ((b)) ((c)))) => #f
(lseq-assoc (lseq 'a) (lseq-q ((a)) ((b)) ((c)))) => ((a))
(lseq-assq 5 (lseq-q (2 3) (5 7) (11 13))) => *unspecified*
(lseq-assv 5 (lseq-q (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-car <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>ialist</var> whose key is greater than five with
<code>(lseq-assoc 5 <var>ialist</var> <)</code>
<p>
Note that fully general ialist 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>ialist</var> with an even key:
(lseq-find (lambda (a) (even? (lseq-car a))) ialist)
</pre>
<!--
==== lseq-alist-cons
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-alist-cons"></a>
<code class="proc-def">ialist-cons</code><var> key datum ialist -> ialist</var>
</dt><dd class="proc-def">
<pre>(lambda (key datum ialist) (lseq-pair (lseq-pair key datum) ialist))
</pre>
Construct a new ialist entry mapping <var>key</var> -> <var>datum</var> onto <var>ialist</var>.
<!--
==== lseq-alist-delete
============================================================================-->
</dd><dt class="proc-def">
<a name="lseq-alist-delete"></a>
<code class="proc-def">ialist-delete </code><var>key ialist [=] -> ialist</var>
</dt><dd class="proc-def">
<code>lseq-alist-delete</code> deletes all associations from <var>ialist</var> with the given <var>key</var>,
using key-comparison procedure =, which defaults to <code>equal?</code>.
The dynamic order in which the various applications of <var>=</var> are made is not
specified.
<p>
Return values may share common tails with the <var>ialist</var> 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.
</p><p>
The comparison procedure is used to compare the element keys <var>k<sub>i</sub></var> of <var>ialist</var>'s
entries to the <var>key</var> parameter in this way:
<code>(= <var>key</var> <var>k<sub>i</sub></var>)</code>.
Thus, one can reliably remove all entries of <var>ialist</var> whose key is greater
than five with
<code>(lseq-alist-delete 5 <var>ialist</var> <)</code>
</p></dd></dl>
<!--========================================================================-->
<h2><a name="Replacement">Replacement</a></h2>
<p>
These two procedures are analogues of the primitive
side-effect operations on pairs, <code>set-car!</code> and <code>set-cdr!</code>.
</p><dl>
<!--
==== replace-icar replace-icdr
============================================================================-->
<dt class="proc-def">
<a name="replace-icar"></a>
<code class="proc-def">replace-icar</code><var> ipair object -> ipair</var>
</dt><dd class="proc-def">
This procedure returns an ipair with <var>object</var> in the icar field
and the icdr of <var>ipair</var> in the icdr field.
</dd><dt class="proc-def">
<a name="replace-icdr"></a>
<code class="proc-def">replace-icdr</code><var> ipair object -> ipair</var>
</dt><dd class="proc-def">
This procedure returns an ipair with <var>object</var> in the icdr field
and the icar of <var>ipair</var> in the icar field.
</dd></dl>
<!--========================================================================-->
<h2><a name="Conversion">Conversion</a></h2>
<p>
These procedures convert between mutable and immutable pair structures.
</p><dl>
<!--
==== pair->ipair ipair->pair
============================================================================-->
<dt class="proc-def1">
<a name="pair->ipair"></a>
<code class="proc-def">pair->ipair</code><var> pair -> ipair</var>
</dt><dt class="proc-defn">
<a name="lseq-pair->pair"></a>
<code class="proc-def">ipair->pair</code><var> ipair -> pair</var>
</dt><dd class="proc-def">
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 lseq->list
============================================================================-->
</dd><dt class="proc-def1">
<a name="list->lseq"></a>
<code class="proc-def">list->lseq</code><var> flist -> lseq</var>
</dt><dt class="proc-defn">
<a name="lseq->list"></a>
<code class="proc-def">lseq->list</code><var> lseq -> flist</var>
</dt><dd class="proc-def">
<p>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.</p>
<p>It is an error to apply <code>list->lseq</code> to a circular list.</p>
<!--
==== pair->ipair ipair->pair
============================================================================-->
</dd><dt class="proc-def1">
<a name="tree->itree"></a>
<code class="proc-def">tree->itree</code><var> object -> object</var>
</dt><dt class="proc-defn">
<a name="lseq-tree->tree"></a>
<code class="proc-def">itree->tree</code><var> object -> object</var>
</dt><dd class="proc-def">
<p>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.</p>
<p>These procedures are not inverses in the general case. For example,
a pair of ipairs would be converted by <code>tree->itree</code> to
an ipair of ipairs, which if converted by <code>lseq-tree->tree</code>
would produce a pair of pairs.</p>
<!--
==== pair->ipair ipair->pair
============================================================================-->
</dd><dt class="proc-def1">
<a name="gtree->itree"></a>
<code class="proc-def">gtree->itree</code><var> object -> object</var>
</dt><dt class="proc-defn">
<a name="gtree->tree"></a>
<code class="proc-def">gtree->tree</code><var> object -> object</var>
</dt><dd class="proc-def">
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.
</dd></dl>
<!--========================================================================-->
<h2><a name="ProcedureApplication">Procedure Application</a></h2>
<p>
This procedure allows a procedure to be applied to an lseq.
</p><dl>
<!--
==== lseq-apply
============================================================================-->
<dt class="proc-def">
<a name="lseq-apply"></a>
<code class="proc-def">iapply</code><var> procedure object ... lseq -> object</var>
</dt><dd class="proc-def">
The <code>lseq-apply</code> procedure is an analogue of <code>apply</code> whose last
argument is an lseq rather than a list. It is equivalent to
<code>(apply </code><var>procedure object</var> ... (<code>lseq->list</code> <var>lseq</var><code>))</code>,
but may be implemented more efficiently.
</dd></dl>
<!--========================================================================-->
<h2><a name="Comparators">Comparators</a></h2>
<dl>
<dt class="proc-def">
<a name="lseq-comparator"></a>
<code class="proc-def">ipair-comparator</code>
</dt><dd class="proc-def">
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 pairs using <code>default-comparator</code> on their first elements. If they are not equal, that value is returned. If they are equal, <code>default-comparator</code> is used on the rest of the lseqs and that value is returned.
</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">
The <code>make-lseq-comparator</code> procedure returns a comparator suitable for comparing lseqs
using <var>element-comparator</var> to compare the elements.
</dd>
</dl>
<!--========================================================================-->
<h1><a name="SampleImplementation">Sample Implementation</a></h1>
<p>An lseq is a <a href="http://srfi.schemers.org/srfi-117/srfi-117.html">SRFI 117</a> 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 <code>lseq-realize-once!</code>, which realizes one value and adds it to the back of the queue.</p>
<p>The sample implementation of this SRFI depends on SRFI 9 (or R7RS) records. 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.
}}}
time
2015-01-08 10:30:49
version
2