mpercivalxyz

dyalog-scan.md (6410B)

---

 ---
 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 artistic code comparisons.
 
 The problem he gives 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 algorithmic solutions across a few different languages:
 
 {{< img src="/assets/three-odd-ints.png" width="900" height="480">}}
 The image highlights a few questions 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.)
 
 ---
 
 So, why is writing a "ChunkBy" algorithm harder in BQN than APL?
 
 The main difference is 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 to it, 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 is that partitions in BQN have to be 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 as to why: 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 the 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 really 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.
 
 As 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...)_