From 2afb23928e1984d475cc460e1672e8f6fa0e4dbe Mon Sep 17 00:00:00 2001 From: Marshall Lochbaum Date: Wed, 11 Aug 2021 17:21:31 -0400 Subject: Allow clicking on header to get fragment link --- docs/doc/fold.html | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'docs/doc/fold.html') diff --git a/docs/doc/fold.html b/docs/doc/fold.html index 2890eb4d..b9dddf8b 100644 --- a/docs/doc/fold.html +++ b/docs/doc/fold.html @@ -4,7 +4,7 @@ BQN: Fold and Insert
(github) / BQN / doc
-

Fold and Insert

+

Fold and Insert

@@ -43,7 +43,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 𝕨.

-

Fold

+

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
 10
@@ -64,7 +64,7 @@
     ∨´ 1‿1‿0
 1
-

Identity values

+

Identity values

Folding over a list of length 1 never calls the operand function: it returns the lone element unchanged.

↗️
    !´ ⟨⎊⟩
 ⎊
@@ -132,7 +132,7 @@
 
 
 
-
Right-to-left

+
Right-to-left

 
The functions we've shown so far are associative (ignoring floating point imprecision), meaning it's equally valid to combine elements of the argument list in any order. But it can be useful to fold using a non-associative function. In this case you must know that Fold performs a right fold, starting from the end of the array and working towards the beginning.

 ↗️
    ≍○<´ "abcd"
 ⟨ 'a' ⟨ 'b' "cd" ⟩ ⟩
@@ -153,7 +153,7 @@
 ↗️
    +⟜÷´ 2‿1‿2‿1‿1‿4‿1‿1
 2.7183098591549295
 

-
Initial element

+
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):

 ↗️
    ∾○⥊´ ⟨2‿4≍6‿8,"abcd",0⟩
 ⟨ 2 4 6 8 'a' 'b' 'c' 'd' 0 ⟩
@@ -180,7 +180,7 @@
 ↗️
    "STOP" ⌽⊸∾´ "ABCDE"‿"012"‿"abcd"
 "EDCBA210dcbaSTOP"
 

-
Insert

+
Insert

 
Fold only works on lists. What if you want to, say, sum the columns of a table?

 ↗️
    ⊢ tab ← (2+↕5) |⌜ 9+↕3
 ┌─       
@@ -241,7 +241,7 @@
 ⟨ 0 4 ⟩
 

 
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?

+
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
 ⟨ ⟨ 1 0 1 4 3 ⟩ ⟨ 0 1 2 0 4 ⟩ ⟨ 1 2 3 1 5 ⟩ ⟩
-- 
cgit v1.2.3