commit 558bb06e305bea002fcd0e008f0bbc53f564f419
parent b8d93afc711a06ab364afcd59c4a69626cd3a39c
Author: mpizzzle <m@michaelpercival.xyz>
Date: Thu, 23 Feb 2023 15:35:44 +0000
wrote a few random thoughts about bqn partitioning/ apl scan
Diffstat:
1 file changed, 167 insertions(+), 0 deletions(-)
diff --git a/content/thoughts/dyalog-scan.md b/content/thoughts/dyalog-scan.md
@@ -0,0 +1,167 @@
+---
+title: "Is dyalog APL's Scan "broken"?"
+date: 2023-02-22T19:57:02Z
+draft: false
+---
+
+I saw [this](https://twitter.com/code_report/status/1628131083760898052/photo/1) recent tweet by Conor Hoekstra, which has some neat (riveting, even) code comparisons.
+
+The idea is to write a function that can tell whether there are at least 3 consecutive odd numbers in a given array.
+
+He broadly compares three algorithms across a few different languages:
+
+{{< img src="/assets/three-odd-ints.png" width="900" height="480">}}
+The image highlights a few curiosities that I'd like to touch upon, namely:
+
+- what's up with BQN partitioning?
+- is APL's scan really broken?
+- (sorry q, perhaps I'll learn about you another time.)
+
+Lets find out.
+
+---
+
+So why is writing a "ChunkBy" algorithm harder in BQN than APL?
+
+I see the main difference in the following glyphs: APL has a dedicated '[partition](http://help.dyalog.com/latest/index.htm#Language/Primitive%20Functions/Partition.htm)' function (dyadic
+{{< highlight APL "hl_inline=true, style=catppuccin-mocha" >}}
+⊆
+{{< /highlight >}}), whereas BQN has the more generalised '[group](https://mlochbaum.github.io/BQN/help/groupindices_group.html)'
+{{< highlight BQN "hl_inline=true, style=catppuccin-mocha" >}}
+(⊔)
+{{< /highlight >}}.
+
+Group has a bit of a learning curve, but is the more [flexible](https://mlochbaum.github.io/BQN/commentary/problems.html#how-to-choose-a-partitioning-function) of the two primitives; the trade-off however is that partitions in BQN are done [idiomatically](https://mlochbaum.github.io/BQN/doc/group.html#partitioning) rather than as a single glyph.
+
+Here is a potential BQN [partition](https://mlochbaum.github.io/bqncrate/?q=Cut%20slice#) solution to Conor's problem:
+
+{{< highlight BQN "linenos=true, style=catppuccin-mocha" >}}
+F ← { 3 ≤ ⌈´≠¨(¬-˜⊢×·+`»⊸>)⊸⊔ 2 | 𝕩 }
+
+F ⟨1,2,3,4,5,6⟩
+# 0
+F ⟨1,2,3,7,5,6⟩
+# 1
+{{< /highlight >}}
+
+Or, [alternatively](https://mlochbaum.github.io/bqncrate/?q=Split%20the%20removing#):
+
+{{< highlight BQN "linenos=true, style=catppuccin-mocha" >}}
+G ← { 3 ≤ ⌈´≠¨ 0 ((⊢-˜+`׬)∘=⊔⊢) 2 | 𝕩 }
+
+G ⟨1,2,3,4,5,6⟩
+# 0
+G ⟨1,2,3,7,5,6⟩
+# 1
+{{< /highlight >}}
+
+These both look overly cumbersome, and well, they are.
+
+However, I think there is a hidden clue: within each partition function is a plus scan
+{{< highlight APL "hl_inline=true, style=catppuccin-mocha" >}}
+(+`)
+{{< /highlight >}}, and isn't that already the basis for the first algorithm? I would take that as a hint from the cosmos that partitioning is not a highly baconic approach here, and to instead go with either a scan or windowed reduction.
+
+---
+
+The second curiosity is the missing APL solution in the above image. Is APL's '[scan](http://help.dyalog.com/latest/index.htm#Language/Primitive%20Operators/Scan.htm)' really broken? That sounds like a rather damning indictment.
+
+Here is what a plus scan looks like:
+
+{{< highlight APL "linenos=true, style=catppuccin-mocha" >}}
++ 3 6 1 8 5
+⍝ 3 9 10 18 23
+{{< /highlight >}}
+
+Which seems fine at first, but once you start plugging in _non-commutative_ functions e.g. subtraction it starts to get weirder.
+
+This example from [Mastering Dyalog APL](https://www.dyalog.com/uploads/documents/MasteringDyalogAPL.pdf#page=406) highlights the problem:
+
+{{< highlight APL "linenos=true, style=catppuccin-mocha" >}}
+- 3 6 1 8 5
+⍝ 3 ¯3 ¯2 ¯10 ¯5
+{{< /highlight >}}
+
+Scan in APL is applied left-to-right, so why do we not instead get
+{{< highlight APL "hl_inline=true, style=catppuccin-mocha" >}}
+(3 ¯3 ¯4 ¯12 ¯17)
+{{< /highlight >}}?
+
+The missing ingredient is that each intermediate is equivalent to a minus reduction
+{{< highlight APL "hl_inline=true, style=catppuccin-mocha" >}}
+(-/)
+{{< /highlight >}} of the elements up to n, and reductions in APL are evaluated _right-to-left_. Therein lies the problem!
+
+For example, applying a minus reduction to the first four elements yields the fourth element of the minus scan:
+{{< highlight APL "linenos=true, style=catppuccin-mocha" >}}
+-/ 3 6 1 8 # i.e. (3-(6-(1-8)))
+⍝ ¯10
+{{< /highlight >}}
+
+So it works as intended, albeit with a slightly odd design.
+
+I think that the perceived "brokenness" with APL scan is more that it doesn't behave in line with other languages.
+
+Take BQN for example:
+
+{{< highlight BQN "linenos=true, style=catppuccin-mocha" >}}
+-` ⟨3,6,1,8,5⟩
+#⟨ 3 ¯3 ¯4 ¯12 ¯17 ⟩
+{{< /highlight >}}
+
+BQN also scans left-to-right, but each intermediate is instead equivalent to a _left_ fold:
+
+{{< highlight BQN "linenos=true, style=catppuccin-mocha" >}}
+-˜´⌽ ⟨3,6,1,8,5⟩ # equivalent to ((((3-6)-1)-8)-5)
+# ¯17
+{{< /highlight >}}
+
+Whilst this is slightly at odds with
+{{< highlight BQN "hl_inline=true, style=catppuccin-mocha" >}}
+´
+{{< /highlight >}}
+being a right fold in BQN (left fold is
+{{< highlight BQN "hl_inline=true, style=catppuccin-mocha" >}}
+𝕗˜´⌽
+{{< /highlight >}}),
+I think that this is still the more intuitive scan primitive, so I do sympathise with Conor's assertion.
+
+To add another example, Haskell also agrees with this left scan definition:
+
+{{< highlight haskell "linenos=true, style=catppuccin-mocha" >}}
+ghci> scanl1 (-) [3,6,1,8,5]
+-- [3,-3,-4,-12,-17]
+{{< /highlight >}}
+
+I had a go at unrolling the APL behaviour to create a left scan in line with Haskell and BQN, which resulted in the following mess:
+
+{{< highlight APL "linenos=true, style=catppuccin-mocha" >}}
+-⍨/∘⌽¨, 3 6 1 8 5
+⍝ 3 ¯3 ¯4 ¯12 ¯17
+{{< /highlight >}}
+
+This is taking the [prefixes](https://aplcart.info/?q=Prefixes%20of%20a%20vector) by doing a join scan
+{{< highlight APL "hl_inline=true, style=catppuccin-mocha" >}}
+(,)
+{{< /highlight >}}
+and then composing a minus 'left' reduction
+{{< highlight APL "hl_inline=true, style=catppuccin-mocha" >}}
+(-⍨/∘⌽)
+{{< /highlight >}}
+for each
+{{< highlight APL "hl_inline=true, style=catppuccin-mocha" >}}
+(¨)
+{{< /highlight >}}
+prefix (yes, I am trying to sound smart).
+
+An APL 'scan' solution to Conor's problem could look something like the following:
+{{< highlight APL "linenos=true, style=catppuccin-mocha" >}}
+{3≤⌈/(⊢×+)⍨/∘⌽¨,2|⍵} 1 2 3 4 5 6
+⍝ 0
+{3≤⌈/(⊢×+)⍨/∘⌽¨,2|⍵} 1 2 3 7 5 6
+⍝ 1
+{{< /highlight >}}
+
+It works, but perhaps the cosmos are whispering something about APL's scan here too.
+
+_(...iiitttsss bbbrrroookkkeeennn...)_
