aboutsummaryrefslogtreecommitdiff
path: root/docs/doc/array.html
diff options
context:
space:
mode:
authorMarshall Lochbaum <mwlochbaum@gmail.com>2022-06-26 21:00:25 -0400
committerMarshall Lochbaum <mwlochbaum@gmail.com>2022-06-26 21:00:25 -0400
commitb6185d5029e2adcc721c0cc2097f591d9a09f135 (patch)
treebf777353ed2a9b28d8b1577c5f36b68605240375 /docs/doc/array.html
parentc618ade174cc2b4e428457751ad8dd01130c2239 (diff)
I am in editing stepped in so far that, should I wade no more, returning were as tedious as go o'er.
Diffstat (limited to 'docs/doc/array.html')
-rw-r--r--docs/doc/array.html18
1 files changed, 9 insertions, 9 deletions
diff --git a/docs/doc/array.html b/docs/doc/array.html
index 827f05c0..f675b171 100644
--- a/docs/doc/array.html
+++ b/docs/doc/array.html
@@ -7,8 +7,8 @@
<h1 id="the-array"><a class="header" href="#the-array">The array</a></h1>
<p>As BQN is an array language, it's often helpful to understand what an array is when writing BQN programs. Fully describing the concept is sometimes <a href="https://www.jsoftware.com/papers/array.htm">held to be tricky</a>; here we'll see definitions, examples, and metaphors.</p>
<p>In BQN, as in APL, arrays are multidimensional, instead of strictly linear. Languages like Python, Javascript, or Haskell offer only one-dimensional arrays with <code><span class='Bracket'>[]</span></code> syntax, and typically represent multidimensional data with nested arrays. Multidimensional arrays have fundamental differences relative to this model.</p>
-<p>BQN's arrays are immutable, meaning that an array is entirely defined by its attributes, and there is no way to modify an existing array, only to produce another array that has changes relative to it. As a result, an array can never contain itself, and arrays form an inductive type. BQN's <a href="lexical.html#mutation">mutable</a> types are operations and namespaces.</p>
-<p>An array might also have a <a href="fill.html">fill element</a> that captures some structural information about its elements and is used by a few operations. The fill, as an inferred property, isn't considered to truly be part of the array but is instead some information about the array that the interpreter keeps track of. So it's out of scope here.</p>
+<p>BQN's arrays are immutable, meaning that an array is entirely defined by its attributes, and there's no way to modify an existing array, only to produce another array that has changes relative to it. As a result, an array can never contain itself. BQN's <a href="lexical.html#mutation">mutable</a> types are operations and namespaces.</p>
+<p>An array might also have a <a href="fill.html">fill element</a> that captures some structural information about its elements and is used by a few operations. As an inferred property, the fill isn't considered to truly be part of the array, but is instead some information about it that the interpreter keeps track of. So it's out of scope here.</p>
<svg viewBox='-36 -15 544 426'>
<g fill='currentColor' stroke-linecap='round' text-anchor='middle' font-size='14' font-family='BQN,monospace'>
<rect class='code' stroke-width='1.5' rx='12' x='-4' y='0' width='480' height='396'/>
@@ -106,7 +106,7 @@
<p>The axes of an array must be independent, that is, the positions present in one axis are fixed for the entire array and don't depend on other axes. This is a difference relative to a nested list model. When storing data in nested lists, the outer axis comes first and later axes are subordinate to it. The length of the second axis depends completely on the position in the first. A programmer might choose the lengths so it doesn't in a particular case, but in a BQN array differing lengths simply aren't representable.</p>
<p>The array also needs to be complete. Every element—every combination of positions—must have a value. This value could be a placeholder like <code><span class='String'>@</span></code>, but it has to be <em>something</em> (in the spending example, everyone spends some amount at each store, even if it's zero). And of course, there are no extra elements that don't fit into the positioning system—the <a href="fill.html">fill</a> isn't really part of the array, but extra information about it.</p>
<h2 id="ordering-and-indices"><a class="header" href="#ordering-and-indices">Ordering and indices</a></h2>
-<p>To finish this definition of an array we also need to nail down the idea of a position. The positions along one dimension can't be labelled in any way, but they have a linear ordering (mathematically speaking, a <a href="https://en.wikipedia.org/wiki/Total_order">total order</a>: out of any two different positions one comes earlier and the other later). BQN keeps track of this order: for example, when we <a href="join.html">join</a> two arrays it places positions in <code><span class='Value'>𝕨</span></code> before those of <code><span class='Value'>𝕩</span></code> and otherwise maintains the original ordering.</p>
+<p>To finish this definition of an array we also need to nail down the idea of a position. The positions along one dimension can't have labels attached to them, but they have a linear ordering (mathematically speaking, a <a href="https://en.wikipedia.org/wiki/Total_order">total order</a>: out of any two different positions one comes earlier and the other later). BQN keeps track of this order: for example, when we <a href="join.html">join</a> two arrays it places positions in <code><span class='Value'>𝕨</span></code> before those of <code><span class='Value'>𝕩</span></code> and otherwise maintains the original orderings.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=ImJlZm9yZSIg4oi+ICJhZnRlciI=">↗️</a><pre> <span class='String'>&quot;before&quot;</span> <span class='Function'>∾</span> <span class='String'>&quot;after&quot;</span>
"beforeafter"
</pre>
@@ -116,10 +116,10 @@
<p>The number of axes in an array is called its <strong>rank</strong>. The number of positions along an axis is called its <strong>length</strong>, and the length of an array means its length along the first axis, or <code><span class='Number'>1</span></code> if there are no axes. The list of the lengths along each axis is the array's <strong>shape</strong>, and describes the possible element locations completely. In BQN they're exposed as the <a href="shape.html">functions</a> Rank (<code><span class='Function'>=</span></code>), Length (<code><span class='Function'>≠</span></code>), and Shape (<code><span class='Function'>≢</span></code>).</p>
<p>The total number of elements in an array is its <strong>bound</strong>, and can be found using <a href="reshape.html">Deshape</a> with <code><span class='Function'>≠</span><span class='Modifier2'>∘</span><span class='Function'>⥊</span></code>, or by multiplying all the lengths in the shape. An array of rank 0, which always contains exactly one element, is called a <a href="enclose.html#whats-a-unit"><strong>unit</strong></a>, while an array of rank 1 is called a <strong>list</strong> and an array of rank 2 is called a <strong>table</strong>.</p>
<h2 id="elements"><a class="header" href="#elements">Elements</a></h2>
-<p>Any BQN value can be used as an array element, including another array (BQN, as a dynamically-typed language, doesn't restrict the types that can be used in one context without a good reason). However, BQN arrays are restricted relative to other array models. Frameworks like NumPy or Julia have mutable arrays, so that the value of an element can be changed after the array is created. This allows an array to be its own element, by creating an array and then inserting it into itself. This would be unnatural in BQN, where an array can only be formed from elements that already exist. In BQN only operations and namespaces are <a href="lexical.html#mutation">mutable</a>.</p>
-<p>An array with no elements (a bound of 0) is called <strong>empty</strong>. These arrays can cause problems when a property should be computed from the elements of an array, like the sum <code><span class='Function'>+</span><span class='Modifier'>´</span><span class='Value'>𝕩</span></code> or shape of the <a href="couple.html#merge-and-array-theory">merged</a> array <code><span class='Function'>&gt;</span><span class='Value'>𝕩</span></code>. BQN has two mechanisms to make these cases work better. First, reductions like <code><span class='Function'>+</span><span class='Modifier'>´</span></code> have <a href="fold.html#identity-values">identity values</a> for certain functions, so that <code><span class='Function'>+</span><span class='Modifier'>´</span><span class='Bracket'>⟨⟩</span></code> is <code><span class='Number'>0</span></code> for example. Second, every array might have a <a href="fill.html">fill element</a>, a special &quot;typical element&quot; for the array. Functions like Merge use this element's structure to determine the result shape when there are no actual elements to be used.</p>
+<p>Any BQN value can be used as an array element, including another array (BQN, as a dynamically-typed language, doesn't restrict the types that can be used in one context without a good reason). However, BQN arrays are in some sense restricted relative to other array models. Frameworks like NumPy or Julia have mutable arrays, so that the value of an element can be changed after the array is created. This allows an array to be its own element, by creating an array and then inserting it into itself. This would be unnatural in BQN, where an array can only be formed from elements that already exist. In BQN only operations and namespaces are <a href="lexical.html#mutation">mutable</a>.</p>
+<p>An array with no elements (a bound of 0) is called <strong>empty</strong>. These arrays can cause problems when a property should be computed from the elements of an array, like the sum <code><span class='Function'>+</span><span class='Modifier'>´</span><span class='Value'>𝕩</span></code> or shape of the <a href="couple.html#merge-and-array-theory">merged</a> array <code><span class='Function'>&gt;</span><span class='Value'>𝕩</span></code>. BQN has two mechanisms to make these cases work better. First, Fold (<code><span class='Modifier'>´</span></code>) and Insert (<code><span class='Modifier'>˝</span></code>) have <a href="fold.html#identity-values">identity values</a> for certain functions, so that <code><span class='Function'>+</span><span class='Modifier'>´</span><span class='Bracket'>⟨⟩</span></code> is <code><span class='Number'>0</span></code> for example. Second, every array might have a <a href="fill.html">fill element</a>, a special &quot;typical element&quot; for the array. Functions like Merge use this element's structure to determine the result shape when there are no actual elements to be used.</p>
<h2 id="cells"><a class="header" href="#cells">Cells</a></h2>
-<p>The contents of an array are its elements, but it also makes sense to split up an array into subarrays of elements called cells. The most important kind of cell, a <strong>major cell</strong> consists of all the elements that have indices beginning with some particular index <code><span class='Value'>i</span></code>. For this to make sense, <code><span class='Value'>i</span></code> must be between <code><span class='Number'>0</span></code> and the length <code><span class='Value'>l</span></code> of the array's first axis, so that there are <code><span class='Value'>l</span></code> major cells each identified by an index.</p>
+<p>The contents of an array are its elements, but it also makes sense to split up an array into subarrays of elements called cells. The most important kind of cell, a <strong>major cell</strong>, consists of all the elements whose indices begin with some particular index <code><span class='Value'>i</span></code>. For this to make sense, <code><span class='Value'>i</span></code> must be between <code><span class='Number'>0</span></code> and the length <code><span class='Value'>n</span></code> of the array's first axis, so that there are <code><span class='Value'>n</span></code> major cells each identified by an index.</p>
<a class="replLink" title="Open in the REPL" target="_blank" href="https://mlochbaum.github.io/BQN/try.html#code=MuKAvzPigL80IMOX4oycIDHigL814oC/OOKAvzExCgoxIOKKjyAy4oC/M+KAvzQgw5fijJwgMeKAvzXigL844oC/MTEgICMgTWFqb3IgY2VsbCAx">↗️</a><pre> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</span> <span class='Function'>×</span><span class='Modifier'>⌜</span> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>8</span><span class='Ligature'>‿</span><span class='Number'>11</span>
┌─
╵ 2 10 16 22
@@ -130,12 +130,12 @@
<span class='Number'>1</span> <span class='Function'>⊏</span> <span class='Number'>2</span><span class='Ligature'>‿</span><span class='Number'>3</span><span class='Ligature'>‿</span><span class='Number'>4</span> <span class='Function'>×</span><span class='Modifier'>⌜</span> <span class='Number'>1</span><span class='Ligature'>‿</span><span class='Number'>5</span><span class='Ligature'>‿</span><span class='Number'>8</span><span class='Ligature'>‿</span><span class='Number'>11</span> <span class='Comment'># Major cell 1
</span>⟨ 3 15 24 33 ⟩
</pre>
-<p>A major cell still has an array structure: it retains all the axes of the original array other than the first. So it has its own major cells, identified by the index <code><span class='Value'>i</span></code> of the original major cell and <code><span class='Value'>j</span></code> within it. These are also cells of the original array. Generalizing, a <strong>cell</strong> with index list <code><span class='Value'>l</span></code> is defined to be the array of all elements whose indices begin with <code><span class='Value'>l</span></code>. In an array with rank <code><span class='Value'>n</span></code>, the cell rank is <code><span class='Value'>n</span><span class='Function'>-≠</span><span class='Value'>l</span></code>, and cells grouped using this rank. An <code><span class='Value'>n</span></code>-cell mst have an empty cell index, so that it includes all elements—it's the entire array! An <code><span class='Value'>n</span><span class='Function'>-</span><span class='Number'>1</span></code> cell, also called a ¯1-cell, is a major cell. A 0-cell has an index of length <code><span class='Value'>n</span></code>, and contains a single element.</p>
+<p>A major cell still has an array structure: it retains all the axes of the original array other than the first. So it has its own major cells, identified by the index <code><span class='Value'>i</span></code> of the original major cell and <code><span class='Value'>j</span></code> within it. These are also cells of the original array. Generalizing, a <strong>cell</strong> with index list <code><span class='Value'>l</span></code> is defined to be the array of all elements whose indices begin with <code><span class='Value'>l</span></code>. In an array with rank <code><span class='Value'>r</span></code>, the cell rank is <code><span class='Value'>r</span><span class='Function'>-≠</span><span class='Value'>l</span></code>, and cells grouped using this rank. An <code><span class='Value'>r</span></code>-cell must have an empty cell index, so that it includes all elements—it's the entire array! An <code><span class='Value'>r</span><span class='Function'>-</span><span class='Number'>1</span></code> cell, also called a ¯1-cell, is a major cell. A 0-cell has an index of length <code><span class='Value'>r</span></code>, and contains a single element.</p>
<p>Cells are the center of the <a href="leading.html">leading axis model</a> used to structure many array primitives.</p>
<h2 id="properties"><a class="header" href="#properties">Properties</a></h2>
<p>Summarizing, the values needed to define an array are its rank (the number of axes), its shape (the number of positions along each axis), and the value of each element (that is, at each combination of positions). Two arrays <a href="match.html">match</a> when all these values match.</p>
-<p>If the rank is considered to be part of the shape, as it is when the shape is a BQN list, then the array is defined by its shape and element list—from <a href="reshape.html">deshape</a>.</p>
-<p>Here's a somewhat informal mathematical take. Given a set of possible element values <code><span class='Function'>T</span></code>, a <em>list</em> of <code><span class='Function'>T</span></code> of length <code><span class='Value'>l</span></code> is a map from natural numbers less than <code><span class='Value'>l</span></code> to <code><span class='Function'>T</span></code>. An array is a rank <code><span class='Value'>r</span></code>, along with a list <code><span class='Value'>s</span></code> of natural numbers of length <code><span class='Value'>r</span></code>, and a map from lists of natural numbers <code><span class='Value'>i</span></code> that satisfy <code><span class='Value'>i</span><span class='Paren'>(</span><span class='Value'>j</span><span class='Paren'>)</span> <span class='Function'>&lt;</span> <span class='Value'>s</span><span class='Paren'>(</span><span class='Value'>j</span><span class='Paren'>)</span></code> for all natural numbers <code><span class='Value'>j</span><span class='Function'>&lt;</span><span class='Value'>r</span></code> to BQN values. Arrays are an inductive type, so that an array can only be defined using elements that already exist. As a result an array's elements are always values of lesser complexity and selecting one element of an array, then an element of that element, and so on, must eventually reach a non-array.</p>
+<p>If the rank is considered to be part of the shape, as it is when the shape is a BQN list, then the array is defined by its shape, and element list as returned by <a href="reshape.html">deshape</a>.</p>
+<p>Here's a somewhat informal mathematical take. Given a set of possible element values <code><span class='Function'>T</span></code>, a <em>list</em> of <code><span class='Function'>T</span></code> of length <code><span class='Value'>l</span></code> is a map from natural numbers less than <code><span class='Value'>l</span></code> to <code><span class='Function'>T</span></code>. An array is a rank <code><span class='Value'>r</span></code>, along with a list <code><span class='Value'>s</span></code> of natural numbers of length <code><span class='Value'>r</span></code>, and a map from lists of natural numbers <code><span class='Value'>i</span></code> that satisfy <code><span class='Value'>i</span><span class='Paren'>(</span><span class='Value'>j</span><span class='Paren'>)</span> <span class='Function'>&lt;</span> <span class='Value'>s</span><span class='Paren'>(</span><span class='Value'>j</span><span class='Paren'>)</span></code> for all natural numbers <code><span class='Value'>j</span><span class='Function'>&lt;</span><span class='Value'>r</span></code> to BQN values. Arrays are an inductive type, so that an array can only be defined using elements that already exist. As a result, an array's elements are always values of lesser complexity than it: selecting one element of an array, then an element of that element, and so on, must eventually reach a non-array.</p>
<h2 id="why-arrays"><a class="header" href="#why-arrays">Why arrays?</a></h2>
<p>The multidimensional array is a fairly simple structure, but there are simpler ones like pairs, lists, sets, and dictionaries. Why does BQN choose the array for its central type? I don't think arrays are always the best data structure (or that BQN is always the best language), but I do think they're one of several good choices and have unique advantages.</p>
<p>Arrays offer a lot of flexibility since they generalize lists. This also means that they can be used to represent pairs or sets. Two lists, or an array with a length-2 axis, can represent a map, although it could be hard to use with good performance.</p>