Is dyalog APL's Scan "broken"?

I saw this 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:

• 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’ function (dyadic ⊆), whereas BQN has the more generalised ‘group’ (⊔).

Group has a bit of a learning curve to it, but is the more flexible of the two primitives; the trade-off is that partitions in BQN have to be done idiomatically rather than as a single glyph.

Here is a potential BQN partition solution to Conor’s problem:

1
2
3
4
5
6

F ← { 3 ≤ ⌈´≠¨(¬-˜⊢×·+`»⊸>)⊸⊔ 2 | 𝕩 }

F ⟨1,2,3,4,5,6⟩
# 0
F ⟨1,2,3,7,5,6⟩
# 1

Or, alternatively:

1
2
3
4
5
6

G ← { 3 ≤ ⌈´≠¨ 0 ((⊢-˜+`׬)∘=⊔⊢) 2 | 𝕩 }

G ⟨1,2,3,4,5,6⟩
# 0
G ⟨1,2,3,7,5,6⟩
# 1

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 (+`), 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’ really broken? That sounds like a rather damning indictment.

Here is what a plus scan looks like:

1
2

+\ 3 6 1 8 5
⍝ 3 9 10 18 23

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 highlights the problem:

1
2

-\ 3 6 1 8 5
⍝ 3 ¯3 ¯2 ¯10 ¯5

Scan in APL is applied left-to-right, so why do we not instead get (3 ¯3 ¯4 ¯12 ¯17)?

The missing ingredient is that each intermediate is really a minus reduction (-/) 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:

1
2

-/ 3 6 1 8 ⍝ i.e. (3-(6-(1-8)))
⍝ ¯10

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:

1
2

-` ⟨3,6,1,8,5⟩
#⟨ 3 ¯3 ¯4 ¯12 ¯17 ⟩

BQN also scans left-to-right, but each intermediate is instead equivalent to a left fold:

1
2

-˜´⌽ ⟨3,6,1,8,5⟩ # equivalent to ((((3-6)-1)-8)-5)
# ¯17

Whilst this is slightly at odds with ´ being a right fold in BQN (left fold is 𝕗˜´⌽), 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:

1
2

ghci> scanl1 (-) [3,6,1,8,5]
-- [3,-3,-4,-12,-17]

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:

1
2

-⍨/∘⌽¨,\ 3 6 1 8 5
⍝ 3 ¯3 ¯4 ¯12 ¯17

This is taking the prefixes by doing a join scan (,\) and then composing a minus ’left’ reduction (-⍨/∘⌽) for each (¨) prefix (yes, I am trying to sound smart).

An APL ‘scan’ solution to Conor’s problem could look something like the following:

1
2
3
4

{3≤⌈/(⊢×+)⍨/∘⌽¨,\2|⍵} 1 2 3 4 5 6
⍝ 0
{3≤⌈/(⊢×+)⍨/∘⌽¨,\2|⍵} 1 2 3 7 5 6
⍝ 1

It works, but perhaps the cosmos are whispering something about APL’s scan here too.

(…iiitttsss bbbrrroookkkeeennn…)