From df5ddc0ed2fe48411645228c6e2d596be239a0c6 Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Mon, 4 Jul 2022 22:25:39 -0400 Subject: A few edits more --- docs/doc/fill.html | 26 +++++++++++++++++++------- docs/doc/find.html | 8 ++++---- docs/doc/fold.html | 43 ++++++++++++++++++++++++++----------------- 3 files changed, 49 insertions(+), 28 deletions(-) (limited to 'docs/doc') diff --git a/docs/doc/fill.html b/docs/doc/fill.html index 3c1a0c27..dc6134b3 100644 --- a/docs/doc/fill.html +++ b/docs/doc/fill.html @@ -6,17 +6,17 @@
(github) / BQN / doc

Fill elements

A few array operations need an array element to use when no existing element applies. BQN tries to maintain a "default" element for every array, known as a fill element, for this purpose. If it's known, the fill element is a nested array structure where each atom is either 0 or ' '. If no fill is known, a function that requests it results in an error.

-

Fills are used by Take (↑) when a value in 𝕨 is larger than the corresponding length in 𝕩, by the two Nudge functions (»«) when 𝕩 is non-empty, by Merge (>) when 𝕩 is empty, and by Reshape (⥊) when 𝕨 contains ↑. Except for these specific cases, the fill value an array has can't affect the program. The result of Match (≡) doesn't depend on fills, and any attempt to compute a fill can't cause side effects.

+

Fills are used by Take (↑) when a value in 𝕨 is larger than the corresponding length in 𝕩 and Reshape (⥊) when 𝕨 contains ↑, by the two Nudge functions (»«) when 𝕩 is non-empty, by Merge (>) and Join when 𝕩 is empty, and by Cells and Rank when the result has an empty frame. These are the only ways that an array's fill value can affect the program. The result of Match (≡) doesn't depend on fills, and any attempt to compute a fill can't cause side effects.

Using fills

-

For the examples in this section we'll use the fact that an all-number array usually has 0 as a fill while a string has ' ' (BQN maintains fills alongside array values rather than deriving them from arrays, so it's possible to construct arrays where this isn't true, but this probably wouldn't happen in ordinary code).

-

Take (↑) and Nudge (»«) in either direction use the fill for padding, to extend the array past its boundary. For example, 𝕨↑𝕩 will add elements to one side when a number in |𝕨 is larger than the corresponding length in ≢𝕩.

+

For the examples in this section we'll use the fact that an all-number array usually has 0 as a fill while a string has ' ' (it's not too rare to end up with such an array that has no fill, and possible but very unusual for an array to have a fill that conflicts with those rules).

+

Take (↑) and Nudge (»«) in either direction use the fill for padding, to extend the array past its boundary. For example, 𝕨↑𝕩 adds elements to one side if a number in |𝕨 is larger than the corresponding length in ≢𝕩.

↗️
    ¯7 ↑ 4⥊3     # Fill with 0
 ⟨ 0 0 0 3 3 3 3 ⟩
 
     ¯7 ↑ "qrst"  # Fill with space
 "   qrst"
-

Nudge Left or Right shifts the array over and places a fill in the vacated space, effectively extending it backwards by one. If 𝕩 is empty then it shouldn't give an error, but it's safer not to rely on this.

+

Nudge Left or Right shifts the array over and places a fill in the vacated space. If 𝕩 is empty then it doesn't need the fill and can't error.

↗️
    »¨ ⟨4⥊3,"qrst"⟩
 ⟨ ⟨ 0 3 3 3 ⟩ " qrs" ⟩
 
@@ -26,7 +26,6 @@
     »⟨⟩   # Fill not needed
 ⟨⟩
-

If the argument to Merge is empty then its result will be as well, since the shape ≢𝕩 is a prefix of ≢>𝕩. However, the remainder of the result shape is determined by the elements of 𝕩, so if there are none then Merge uses the fill element to decide what the result shape should be.

Reshape (⥊) uses the fill when 𝕨 contains ↑ and the product of the rest of 𝕨 doesn't evenly divide the number of elements in 𝕩.

↗️
    ↑‿8 ⥊ "completepart"
 ┌─          
@@ -38,15 +37,28 @@
 ↗️
    ⊑»1↑⥊"string"
 ' '
 

+
Edge cases

+
The above functions use the fill as part of their core definition. A few other functions use fills only when they encounter empty arrays. The goal of this behavior is to make programs working on empty arrays more similar to the non-empty case, so if all goes well you don't need to be thinking about these cases.

+
If the argument to Merge is empty then its result will be as well, since the shape ≢𝕩 is a prefix of ≢>𝕩. However, the remainder of the result shape is determined by the elements of 𝕩, so if there are none then Merge uses the fill element to decide what the result shape should be. Join is similar, although it multiplies the shape of 𝕩 by the leading shape of the fill instead of concatenating them.

+↗️
    ≢ > 2‿0⥊<3‿4‿1⥊0
+⟨ 2 0 3 4 1 ⟩
+
+    ≢ ∾ 2‿0⥊<3‿4‿1⥊0
+⟨ 6 0 1 ⟩
+

+
Cells and Rank rely on fills in a slightly more complicated way. If one of the argument frames is empty, that means the result will be empty, but the shape of a result cell still needs to be known to determine its shape (and similarly for the fill, but that's optional). BQN implementations may try to find it by running 𝔽 using a cell of fills for the argument. As in Each (¨) described below, this evaluation is not allowed to produce side effects. If it doesn't work, the result cell shape is assumed to be ⟨⟩.

+↗️
    ≢ ⌽˘ ↕0‿4‿3  # Shape is determined by fills
+⟨ 0 4 3 ⟩
+

 
How fills are computed

 
For the exact requirements placed on fill, see the specification (particularly "required functions"). This section loosely describes behavior in existing BQN implementations, and includes some parts that aren't required in the specification.

 
A fill element should encompass something that's necessarily true for all elements of an array. If the way an array is computed implies it's all numbers, the fill should be 0. If every element is a list of two numbers, then the fill should be ⟨0,0⟩. If every element is a list but the lengths might vary, ⟨⟩ is probably a reasonable fill element.

-
For arithmetic primitives, the fill is found by the rules of pervasion, applying the function to both argument fills. Generally this means it consists of 0, but character arithmetic also allows space fills.

+
For arithmetic primitives, the fill is found by the rules of pervasion, applying the function to both argument fills. Generally this means it consists of 0, but character arithmetic can produce space for a fill value.

 ↗️
    » "abc" + 4‿3‿2
 " ee"
 

 
Mapping modifiers Each and Table (¨⌜) might try to follow a similar strategy, applying 𝔽 to argument fills to obtain the result fill. The absolute rule here is that this computation can't cause side effects or an error, so for a complicated 𝔽 such as a block function this procedure is likely to be aborted to avoid disrupting the rest of the program.

-
Most other primitives fit in one of three broad categories as shown in the table below. Structural primitives, indicated by ⊢, don't change the fill of 𝕩. Combining structural primitives, indicated by ∩, only depend on the fill of all combined arrays—elements of 𝕩 in the one-argument case, or 𝕨 and 𝕩 in the two-argument case. Finally, many functions such as search functions return only numbers and have a fill of 0.

+
Most other primitives fit in one of three broad categories as shown in the table below. Structural primitives, indicated by ⊢, don't change the fill of 𝕩. Combining structural primitives, indicated by ∩, only depend on the fill of all combined arrays—elements of 𝕩 in the one-argument case, or 𝕨 and 𝕩 in the two-argument case. If these fills are the same value, then that's the fill; otherwise, the result has no fill. Finally, many functions such as search functions return only arrays of numbers and have a fill of 0.

 
diff --git a/docs/doc/find.html b/docs/doc/find.html
index 09632469..01efff6d 100644
--- a/docs/doc/find.html
+++ b/docs/doc/find.html
@@ -9,7 +9,7 @@
 ↗️
    "xx" ⍷ "xxbdxxxcx"
 ⟨ 1 0 0 0 1 1 0 0 ⟩
 

-
More precisely 𝕨 needs to match a contiguous selection from 𝕩, which for strings means a substring. These subarrays of 𝕩 are also exactly the cells in the result of Windows. In fact we can use Windows to see all the arrays 𝕨 will be compared against.

+
More precisely, 𝕨 needs to match a contiguous selection from 𝕩, which for strings means a substring. These subarrays of 𝕩 are also exactly the cells in the result of Windows. So we can use Windows to see all the arrays 𝕨 will be compared against.
↗️
    2 ↕ "xxbdxxxcx"
 ┌─    
 ╵"xx  
@@ -32,7 +32,7 @@
     "string" (≢∘⊢↑⍷) "substring"  # APL style
 ⟨ 0 0 0 1 0 0 0 0 0 ⟩
 

-
If 𝕨 is larger than 𝕩, the result is empty, and there's no error even in cases where Windows would fail. One place this tends to come up is when applying First (⊑) the result: ⊑⍷ tests whether 𝕨 appears in 𝕩 at the first position, that is, whether it's a prefix of 𝕩. If 𝕨 is longer than 𝕩 it shouldn't be a prefix. First will fail but using a fold 0⊣´⥊∘⍷ instead gives a 0 in this case.

+
If 𝕨 is larger than 𝕩, the result is empty, and there's no error even in cases where Windows would fail. One place this tends to come up is when applying First (⊑) to the result: ⊑⍷ tests whether 𝕨 appears in 𝕩 at the first position, that is, whether it's a prefix of 𝕩. If 𝕨 is longer than 𝕩 it shouldn't be a prefix. First will fail but using a fold 0⊣´⍷ instead gives a 0 in this case.
↗️
    "loooooong" ⍷ "short"
 ⟨⟩
 
@@ -42,7 +42,7 @@
     0 ⊣´ "loooooong" ⍷ "short"
 0
 

-
This pattern also works in the high-rank case discussed below, testing whether 𝕨 is a multi-dimensional prefix starting at the lowest-index corner of 𝕩.

+
Adding a Deshape gives 0⊣´⥊∘⍷, which works with the high-rank case discussed below. It tests whether 𝕨 is a multi-dimensional prefix starting at the lowest-index corner of 𝕩.
Higher ranks
If 𝕨 and 𝕩 are two-dimensional then Find does a two-dimensional search. The cells used are also found in 𝕨≢⊸↕𝕩. For example, the bottom-right corner of 𝕩 below matches 𝕨, so there's a 1 in the bottom-right corner of the result.
↗️
    ⊢ a ← 7 (4|⋆˜)⌜○↕ 9   # Array with patterns
@@ -66,7 +66,7 @@
   0 0 1 0 0 0 1  
                 ┘
 

-
It's also allowed for 𝕨 to have a smaller rank than 𝕩; in this case leading axes of 𝕩 are mapped over so that axes of 𝕨 correspond to trailing axes of 𝕩. This is a minor violation of the leading axis principle, which would match axes of 𝕨 to leading axes of 𝕩 in order to make a function that's useful with the Rank operator, but such a function would be quite strange and hardly ever useful.

+
It's also allowed for 𝕨 to have a smaller rank than 𝕩; the axes of 𝕨 then correspond to trailing axes of 𝕩, so that leading axes of 𝕩 are mapped over. This is a minor violation of the leading axis principle, which would match axes of 𝕨 to leading axes of 𝕩 in order to make a function that's useful with the Rank operator, but such a function would be quite strange and hardly ever useful.
↗️
    0‿1‿0‿1 ⍷ a
 ┌─             
 ╵ 0 0 0 0 0 0  
diff --git a/docs/doc/fold.html b/docs/doc/fold.html
index f1dc9a59..5b024ff4 100644
--- a/docs/doc/fold.html
+++ b/docs/doc/fold.html
@@ -42,7 +42,7 @@
 
 
 
The closely related 1-modifiers Fold (´) and Insert (˝) apply a dyadic operand function 𝔽 repeatedly between elements or major cells of 𝕩. Neither is quite like the APL2-style Reduce operator (/ or ⌿ in APL), although I sometimes use the term "reduction" to mean either Fold or Insert. There are a bunch of other names like "accumulate" and "aggregate" for this class of calculations—I don't know which is best but I know "catamorphism" is worst.

-
A distinguishing feature of APL-family reductions is that they don't use an initial value, and try to derive an "identity element" from the operand if the argument array is empty. BQN retains this capability but also allows the programmer to supply an initial value as 𝕨.

+
A distinguishing feature of APL-family reductions is that they don't use an initial value, and try to derive an "identity element" for 𝔽 if the argument array is empty. BQN retains this capability but also allows the programmer to supply an initial value as 𝕨.

 
Fold

 
As its glyph suggests, Fold is slightly simpler than Insert. The argument 𝕩 must always be a list, and Fold applies 𝔽 between elements—always two at a time—of the list to yield a single result value. In this sense, 𝔽´ removes a layer of depth from 𝕩, although it's not necessarily true that the depth of 𝔽´𝕩 is less than that of 𝕩 because the function 𝔽 might increase depth.

 ↗️
    +´ 2‿4‿3‿1
@@ -50,7 +50,7 @@
     +´ ⟨2‿4, 3‿1⟩
 ⟨ 5 5 ⟩
 

-
Any function can be used as an operand. With Maximum (⌈) you can find the largest number out of an entire list, and likewise for Minimum (⌊).

+
Any function can be used as an operand. You can find the largest number out of an entire list with Maximum (⌈), or the smallest with Minimum (⌊).

 ↗️
    ⌈´ 2‿4‿3‿1
 4
     ⌊´ 2‿4‿3‿1
@@ -77,7 +77,7 @@
     ∧´ ⟨⟩  # All the elements in the list are true…
 1
 

-
The full list of identity values Fold has to use is shown below.

+
Here's the full list of identity values Fold has to support.

 

 
 

 
 
 
 
 
 

@@ -140,7 +140,7 @@
     'a'⋈'b'⋈'c'⋈'d'# Expanded form
 ⟨ 'a' ⟨ 'b' "cd" ⟩ ⟩
 
-
Using Pair (⋈) as an operand shows the structure nicely. This fold first pairs the final two characters 'c' and 'd', then pairs 'b' with that and so on. This matches BQN's right-to-left order of evaluation. More declaratively we might say that each character is paired with the result of folding over everything to its right.

+
Pair (⋈) as an operand shows the structure nicely. This fold first pairs the final two characters 'c' and 'd', then pairs 'b' with that and so on. This matches BQN's right-to-left order of evaluation. More declaratively we might say that each character is paired with the result of folding over everything to its right.
BQN doesn't provide a left Fold (` is Scan). However, you can fold from the left by reversing (⌽) the argument list and also reversing (˜) the operand function's argument order.
↗️
    ⋈˜´ ⌽ "abcd"
 ⟨ ⟨ "ab" 'c' ⟩ 'd' ⟩
@@ -149,12 +149,12 @@
 ↗️
    -´ 30‿1‿20‿2‿10
 57
 

-
The operand +⟜÷ is a quick way to compute a continued fraction's value from a list of numbers. Here are a few terms from the continued fraction for e.

+
And the operand +⟜÷ is a quick way to compute a continued fraction's value from a list of numbers. Here are a few terms from the continued fraction for e.

 ↗️
    +⟜÷´ 2‿1‿2‿1‿1‿4‿1‿1
 2.71830985915493
 

 
Initial element

-
When the operand isn't just an arithmetic primitive, folding with no initial element can be dangerous. Even if you know 𝕩 isn't empty, saving you from an "Identity not found" error, the case with only one element can easily violate expectations. Here's a somewhat silly example of a function meant to merge elements of the argument into a single list (∾⥊¨ is a much better way to do this):

+
When 𝔽 isn't just an arithmetic primitive, folding with no initial element can be dangerous. Even if you know 𝕩 isn't empty, saving you from an "Identity not found" error, the case with only one element can easily violate expectations. Here's a somewhat silly example of a function meant to merge elements of the argument into a single list (∾⥊¨ is a much better way to do this):

 ↗️
    ∾○⥊´ ⟨2‿4≍6‿8,"abcd",0⟩
 ⟨ 2 4 6 8 'a' 'b' 'c' 'd' 0 ⟩
 
@@ -168,11 +168,11 @@
       ┘
 

 
The result always has rank 1, until the one-element case, when ∾○⥊ is never applied and can't deshape anything. Using Fold with lots of complex operands and no initial element can make a program fragile.

-
However, it's easy to specify an initial element for Fold: simply pass it as 𝕨. Because 𝕨 behaves like an element of 𝕩, it doesn't need to be enclosed and will usually have one smaller depth. For ∾○⥊ the natural starting element for a fold that returns a list is the empty list.

+
The left argument, if given, is the initial right argument to 𝔽. This puts 𝕨 on the same level as an element of 𝕩, so it doesn't need to be enclosed and will usually have one smaller depth. For ∾○⥊´ the natural starting element is the empty list.

 ↗️
    ⟨⟩ ∾○⥊´ ⟨2‿4≍6‿8⟩
 ⟨ 2 4 6 8 ⟩
 

-
The initial element is used in the first function application, so it behaves as though it's added to the end of the list (∾⟜<˜ would accomplish this as well).

+
With a non-empty 𝕨 we can see it's placed at the end of the result list, because it's passed to 𝔽 before any elements of 𝕩.

 ↗️
    "end" ∾○⥊´ ⟨"start","middle"⟩
 "startmiddleend"
 

@@ -194,24 +194,24 @@
     +˝ tab
 ⟨ 9 7 12 ⟩
 

-
The Insert (˝) modifier will do this for you. Because it works on the leading axis of the argument, Insert can be applied to axes other than the first with Rank. Sum each row (second axis) with ˘, for example.

+
The Insert (˝) modifier will do this for you. And because it works on the leading axis of the argument, Insert can be applied to axes other than the first with Rank. Sum each row (second axis) with Cells (˘), for example.
↗️
    +˝˘ tab
 ⟨ 2 3 6 5 12 ⟩
 

-
This case is tricky, because +´˘ tab yields the same result but is actually unsound—if tab contains arrays then they will be merged together at the end. Remember that if you want to reduce along one axis of an array but get an array of results out, you should use Insert (possibly adding Each to work on elements instead of cells; see APL2 reduction below).

+
This case is tricky, because +´˘ tab yields the same result but is actually unsound—if tab contains arrays then they will be merged together at the end. Remember: if you want to reduce along one axis of an array and get an array of results out, you should use Insert (possibly adding Each to work on elements instead of cells; see APL2 reduction below).
A function with Insert 𝔽˝ is nearly equivalent to 𝔽´<˘ (and both fail on unit arguments, because there's no axis to apply along). Besides being more convenient, 𝔽˝ is a little safer because it takes the argument shape into account when returning an identity value:
↗️
    +´<˘ 0‿4⥊0
 0
     +˝   0‿4⥊0
 ⟨ 0 0 0 0 ⟩
 

-
Just like Fold, Insert allows an initial element for the left argument, so that you don't need to rely on the interpreter knowing the identity. A more complete translation into Fold is therefore {𝕨𝔽´<˘𝕩}. The expression below shows that the operand function is called on the last major cell when the identity, then the next-to-last major cell and so on. In total there are ≠𝕩 calls, while there would be 1-˜≠𝕩 without the left argument.

-↗️
    "id" ⋈˝ "row0 "∾"row1 "≍"row2 "
+
Just like Fold, Insert allows an initial element for the left argument, so that you don't need to rely on the interpreter knowing the identity (in Fold terms it's {𝕨𝔽´<˘𝕩}). Below, we see that 𝔽 is called on the last major cell and 𝕨, then the next-to-last major cell and so on. This makes ≠𝕩 calls, while there would be 1-˜≠𝕩 without the initial value.

+↗️
    "id" ⋈˝ ["row0 ","row1 ","row2 "]
 ┌─                                      
 · "row0 " ⟨ "row1 " ⟨ "row2 " "id" ⟩ ⟩  
                                        ┘
 

-
One trick involving Insert is ∾˝, which merges the first two axes of 𝕩 into one long axis. It even works on empty arrays, because BQN knows that there's only one result shape that makes sense (in contrast to ∾´⟨⟩, where many results sometimes work but none of them always work).

+
One trick involving Insert is ∾˝, which uses Join to to merge the first two axes of 𝕩 into one long axis. It even works on empty arrays, because BQN knows that there's only one result shape that makes sense (unlike ∾´⟨⟩, where many results sometimes fit but none of them always fit).

 ↗️
    ⊢ let ← ("AHW"-'A') +⌜ "aA" +⌜ ↕4
 ┌─      
 ╎"abcd  
@@ -242,12 +242,21 @@
 

 
As a historical note, Insert is named after J's adverb /, which comes from SHARP APL's ⌿, reduce-down. In the original APL, only arithmetic reductions were defined, and nested arrays didn't exist—arrays were either all characters or all numbers. SHARP extended them by splitting the array into cells as we've shown. However, there's another interpretation, which is what you'll find in mainstream APLs today…

 
APL2 reduction?

-
If you try an expression like ⍪⌿ in Dyalog APL, you'll get results very different from BQN's ∾˝. Instead of combining the cells like we see above, APL applies the function on pairs of elements much like Fold. The difference is that, because reduction happens only along one axis but an array might have other axes, there can be multiple values in the result, so that it will always be an array like the argument. BQN can perform this operation as well: ⍪⌿ is written ∾¨˝ in BQN.

-↗️
    ∾¨˝ tab
+
The function ⍪⌿ in Dyalog APL gives very different results from BQN's ∾˝. Instead of combining the cells like we see above, APL applies the function on pairs of elements much like Fold. The difference is that, because reduction happens only along one axis but an array might have other axes, there can be multiple values in the result, so that it will always be an array like the argument. BQN can perform this operation as well: ⍪⌿ is written ∾¨˝ in BQN (but please use <˘⍉ instead).

+↗️
    tab
+┌─       
+╵ 1 0 1  
+  0 1 2  
+  1 2 3  
+  4 0 1  
+  3 4 5  
+        ┘
+
+    ∾¨˝ tab
 ⟨ ⟨ 1 0 1 4 3 ⟩ ⟨ 0 1 2 0 4 ⟩ ⟨ 1 2 3 1 5 ⟩ ⟩
 

-
This kind of reduction has an interesting property that the other two lack: it always removes exacly one axis, so that the result's shape is the argument's major cell shape. When applied to a later axis using the Rank or Cells modifier, it removes that axis instead.

-↗️
    ≢ ∾¨˝ ↕4‿2‿3   # Reduce out the first axis
+
This kind of reduction has an interesting property not found in ´ or ˝: it always removes exactly one axis, so that the result's shape is 𝕩's major cell shape. When applied to a later axis using Rank or Cells, it removes that axis instead.

+↗️
    ≢ ∾¨˝  ↕4‿2‿3  # Reduce out the first axis
 ⟨ 2 3 ⟩
     ≢ ∾¨˝˘ ↕4‿2‿3  # Reduce out the second
 ⟨ 4 3 ⟩
-- 
cgit v1.2.3