diff options
author | Arthur A. Gleckler <srfi@speechcode.com> | 2021-03-18 15:30:34 -0700 |
---|---|---|
committer | Arthur A. Gleckler <srfi@speechcode.com> | 2021-03-18 15:34:41 -0700 |
commit | 86c0d1caee3678e3442e0e8545b05f93f5c285cf (patch) | |
tree | 0b682920eb0f11125a8742cc972598ba3ad56cf6 /srfi-214.html | |
parent | 6b36b8299df8fadb5713ac1249f0418e118913bf (diff) | |
download | srfi-214-86c0d1caee3678e3442e0e8545b05f93f5c285cf.tar.gz srfi-214-86c0d1caee3678e3442e0e8545b05f93f5c285cf.tar.xz srfi-214-86c0d1caee3678e3442e0e8545b05f93f5c285cf.zip |
copy edits
Diffstat (limited to 'srfi-214.html')
-rw-r--r-- | srfi-214.html | 12 |
1 files changed, 6 insertions, 6 deletions
diff --git a/srfi-214.html b/srfi-214.html index 61c938d..fd6c56d 100644 --- a/srfi-214.html +++ b/srfi-214.html @@ -22,8 +22,8 @@ <h2 id="abstract">Abstract</h2> <p>A <em>flexvector</em>, also known as a dynamic array or an arraylist, is a mutable vector-like data structure with an adjustable size. Flexvectors allow fast random access and fast insertion/removal at the end. This SRFI defines a suite of operations on flexvectors, modeled after <a href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a>'s vector operations.</p> <h2 id="rationale">Rationale</h2> -<p>Unlike the default vector datatype of many other languages, Scheme vectors have a fixed length. This makes vectors unusable as mutable stacks or queues, and is the reason that <a href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a> lacks common collection operations like <code>filter</code>.</p> -<p>In fact, no Scheme standard defines a mutable datatype that is suitable for this very common purpose, analogous to a Java <code>ArrayList</code> or to the default list data structure in JavaScript or Python. <a href="https://srfi.schemers.org/srfi-117/srfi-117.html">SRFI 117</a> defines the commonly-used "tconc" mutable queue, but it is a linked list. And <a href="https://srfi.schemers.org/srfi-134/srfi-134.html">SRFI 134</a> defines a deque datatype, but that datatype is immutable. Neither data structure has the (often useful) properties of being a mutable, contiguous, random-access sequence.</p> +<p>Unlike the default vector data type of many other languages, Scheme vectors have a fixed length. This makes vectors unusable as mutable stacks or queues, and is the reason that <a href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a> lacks common collection operations like <code>filter</code>.</p> +<p>In fact, no Scheme standard defines a mutable data type that is suitable for this very common purpose, analogous to a Java <code>ArrayList</code> or to the default list data structure in JavaScript or Python. <a href="https://srfi.schemers.org/srfi-117/srfi-117.html">SRFI 117</a> defines the commonly-used "tconc" mutable queue, but it is a linked list. And <a href="https://srfi.schemers.org/srfi-134/srfi-134.html">SRFI 134</a> defines a deque data type, but that data type is immutable. Neither data structure has the (often useful) properties of being a mutable, contiguous, random-access sequence.</p> <p>This SRFI does not define a comparator or any sorting procedures, in order to ensure that it has no dependencies. These may be defined in future SRFIs.</p> <h3 id="terminology">Terminology</h3> <p>What this SRFI calls a <em>flexvector</em> is better known as a <a href="https://en.wikipedia.org/wiki/Dynamic_array"><em>dynamic array</em></a>. This data structure has a wide variety of names in different languages:</p> @@ -37,7 +37,7 @@ <p>This SRFI is primarily modeled on <a href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a>. It includes flexvector equivalents of all SRFI 133 procedures, most with the same names and argument order. There are three notable exceptions:</p> <ol> <li><code>flexvector-unfold</code> mimics the API of <a href="https://srfi.schemers.org/srfi-1/srfi-1.html">SRFI 1</a>'s <code>unfold</code>, not SRFI 133's <code>vector-unfold</code>. <code>vector-unfold</code> is limited by the necessity of a fixed vector length, while <code>flexvector-unfold</code> may generate a flexvector of any length, and so the <code>unfold</code> API is more useful.</li> -<li>There is no flexvector equivalent of <code>vector-unfold!</code>, because flexvectors use the list version of <code>unfold</code>, which has no <code>unfold!</code> equivalent with a similar API.</li> +<li>There is no flexvector equivalent of <code>vector-unfold!</code> because flexvectors use the list version of <code>unfold</code>, which has no <code>unfold!</code> equivalent with a similar API.</li> <li>The flexvector equivalent of <code>vector=</code> is <code>flexvector=?</code>. It is conventional for Scheme equality predicates to end in <code>=?</code> (e.g., <code>symbol=?</code>, <code>string=?</code>), and most data structure SRFIs follow this convention (see <a href="https://srfi.schemers.org/srfi-113/srfi-113.html">SRFI 113</a>, <a href="https://srfi.schemers.org/srfi-125/srfi-125.html">125</a>, <a href="https://srfi.schemers.org/srfi-146/srfi-146.html">146</a>). This SRFI follows established convention, even when it does not match SRFI 133's procedure names.</li> </ol> <p>Additionally, this SRFI includes deque-like operations that reference, add to, and remove from both ends of a flexvector. The naming convention for these operations is taken from <a href="https://srfi.schemers.org/srfi-134/srfi-134.html">SRFI 134</a>, which uses the terms <em>front</em> and <em>back</em>. <em>Front</em> refers to the start of the flexvector (index 0), while <em>back</em> refers to the end (index <code>(- (flexvector-length x) 1)</code>).</p> @@ -61,7 +61,7 @@ <p><code>λ</code> is a shorthand alias for <code>lambda</code>.</p> </li> </ul> -<p>Additionally, examples include literal flexvector values written in pseudo-lexical syntax: <code>#<flexvector a b c></code> is a flexvector of length 3 containg the symbol values <code>a</code>, <code>b</code>, and <code>c</code>. <strong>This syntax is only used for example purposes.</strong> This SRFI does not define the <code>#<flexvector ...></code> syntax for actual use.</p> +<p>Additionally, examples include literal flexvector values written in pseudo-lexical syntax: <code>#<flexvector a b c></code> is a flexvector of length 3 containing the symbol values <code>a</code>, <code>b</code>, and <code>c</code>. <strong>This syntax is only used for example purposes.</strong> This SRFI does not define the <code>#<flexvector ...></code> syntax for actual use.</p> <h3 id="api">API</h3> <ul> <li>Constructors @@ -170,7 +170,7 @@ <div class="copy-wrapper"><pre><code class="language-scheme"><span><span class="mtk1">(flexvector </span><span class="mtk21">0</span><span class="mtk1"> </span><span class="mtk21">1</span><span class="mtk1"> </span><span class="mtk21">2</span><span class="mtk1"> </span><span class="mtk21">3</span><span class="mtk1"> </span><span class="mtk21">4</span><span class="mtk1">) </span><span class="mtk4">;=> #<flexvector 0 1 2 3 4></span></span><br></code></pre></div> <h4 id="flexvector-unfold-flexvector-unfold-right"><code>flexvector-unfold</code>, <code>flexvector-unfold-right</code></h4> <p><code>(flexvector-unfold p f g initial-seed ...)</code></p> -<p>The fundamental flexvector constructor. <code>flexvector-unfold</code> is modeled on SRFI 1 <code>unfold</code> instead of SRFI 133 <code>vector-unfold</code>, because flexvectors are not limited to a predetermined length.</p> +<p>The fundamental flexvector constructor. <code>flexvector-unfold</code> is modeled on SRFI 1 <code>unfold</code> instead of SRFI 133 <code>vector-unfold</code> because flexvectors are not limited to a predetermined length.</p> <div class="copy-wrapper"><pre><code class="language-scheme"><span><span class="mtk4">;; List of squares: 1^2 ... 10^2</span></span><br><span><span class="mtk1">(flexvector-unfold (λ (x) (> x </span><span class="mtk21">10</span><span class="mtk1">)) (λ (x) (* x x)) (λ (x) (+ x </span><span class="mtk21">1</span><span class="mtk1">)) </span><span class="mtk21">1</span><span class="mtk1">)</span></span><br><span><span class="mtk4">;=> #<flexvector 1 4 9 16 25 36 49 64 81 100></span></span><br></code></pre></div> <p>For each step, <code>flexvector-unfold</code> evaluates <code>p</code> on the seed value(s) to determine whether it should stop unfolding. If <code>p</code> returns <code>#f</code>, it then evaluates <code>f</code> on the seed value(s) to produce the next element, then evaluates <code>g</code> on the seed value(s) to produce the seed value(s) for the next step. The recursion can be described with this algorithm:</p> <div class="copy-wrapper"><pre><code class="language-scheme"><span><span class="mtk1">(</span><span class="mtk12">let</span><span class="mtk1"> recur ((seeds initial-seed) (fv (flexvector)))</span></span><br><span><span class="mtk1"> (</span><span class="mtk12">if</span><span class="mtk1"> (apply p seeds) fv</span></span><br><span><span class="mtk1"> (let-values ((next-seeds (apply g seeds)))</span></span><br><span><span class="mtk1"> (recur next-seeds (flexvector-add-back! fv</span><span class="mtk1"> (apply f seeds))))))</span></span><br></code></pre></div> @@ -321,7 +321,7 @@ <div class="copy-wrapper"><pre><code class="language-scheme"><span><span class="mtk1">(</span><span class="mtk12">let</span><span class="mtk1"> ((fv (flexvector </span><span class="mtk21">1</span><span class="mtk1"> </span><span class="mtk21">2</span><span class="mtk1"> </span><span class="mtk21">3</span><span class="mtk1"> </span><span class="mtk21">4</span><span class="mtk1"> </span><span class="mtk21">5</span><span class="mtk1"> </span><span class="mtk21">6</span><span class="mtk1"> </span><span class="mtk21">7</span><span class="mtk1"> </span><span class="mtk21">8</span><span class="mtk1">)))</span></span><br><span><span class="mtk1"> (flexvector-filter! odd? fv)</span></span><br><span><span class="mtk1"> fv)</span></span><br><span><span class="mtk4">;=> #<flexvector 1 3 5 7></span></span><br></code></pre></div> <h4 id="flexvector-for-each-flexvector-for-eachindex"><code>flexvector-for-each</code>, <code>flexvector-for-each/index</code></h4> <p><code>(flexvector-for-each f fv1 fv2 ...)</code></p> -<p>Simple flexvector iterator: applies <code>f</code> to the corresponding list of parallel elements from <code>fv1 fv2 ...</code> in the range [0, <code>length</code>), where <code>length</code> is the length of the smallest flexvector argument passed, In contrast with <code>flexvector-map</code>, <code>f</code> is reliably applied in left-to-right order, starting at index 0, in the flexvectors.</p> +<p>Simple flexvector iterator: applies <code>f</code> to the corresponding list of parallel elements from <code>fv1 fv2 ...</code> in the range [0, <code>length</code>), where <code>length</code> is the length of the smallest flexvector argument passed. In contrast with <code>flexvector-map</code>, <code>f</code> is reliably applied in left-to-right order, starting at index 0, in the flexvectors.</p> <p><code>flexvector-for-each/index</code> is a variant that passes the index as the first argument to <code>f</code> for each element.</p> <p>Example:</p> <div class="copy-wrapper"><pre><code class="language-scheme"><span><span class="mtk1">(flexvector-for-each (λ (x) (display x) (newline))</span></span><br><span><span class="mtk1"> (flexvector </span><span class="mtk1">"foo"</span><span class="mtk1"> </span><span class="mtk1">"bar"</span><span class="mtk1"> </span><span class="mtk1">"baz"</span><span class="mtk1"> </span><span class="mtk1">"quux"</span><span class="mtk1"> </span><span class="mtk1">"zot"</span><span class="mtk1">))</span></span><br></code></pre></div> |