Ooh, I've run into this one before! I'm a big fan of interval index[0], which performs a binary search, so Josh's suggestion is the one I prefer as well (the implementation might sometimes optimize by transforming it into a table lookup like the other solutions). Searching for +`≠¨ in my BQN files turns up a few uses, including one used to group primitives into types in a utility involved in compiling BQN[1] and an annotated function used a few times in the markdown processor that builds BQN's website[2].
Been working on the design of an optimizer for my APL VM and asked Claude how this would fit in (as we don't have Dyalog extensions):
The pattern is:
f⌿ X ∘.g Y
Where f is an associative reduction and g is a comparison. iBurg could recognize this tree shape and apply rewrites based on operator properties:
┌─────────┬───────────────────────────────────┐
│ Pattern │ Optimization │
├─────────┼───────────────────────────────────┤
│ +⌿X∘.≤Y │ Binary search count (if X sorted) │
├─────────┼───────────────────────────────────┤
│ +⌿X∘.=Y │ Histogram / count matches │
├─────────┼───────────────────────────────────┤
│ ∨⌿X∘.=Y │ Membership (hash lookup) │
├─────────┼───────────────────────────────────┤
│ ∧⌿X∘.<Y │ All-less-than (single comparison) │
└─────────┴───────────────────────────────────┘
The generic rules would be:
1. Shape rule: f⌿X∘.gY avoids materializing n×m matrix if f and g have algebraic properties that allow streaming/early-exit
2. Sortedness rule: If X is sorted and g is monotonic (≤, <, ≥, >), use binary search
3. Associativity rule: If f is associative (+, ∨, ∧, ⌈, ⌊), can process in chunks or parallel
The cost model decides when O(n log m) binary search beats O(n×m) outer product -typically when both n and m exceed some threshold.
iBurg is the Bottom-Up Rewrite System (BURS) based optimizer to operate over the continuation graphs the parser spits out, not sure where the 'i' part came from though...
Ooh, I've run into this one before! I'm a big fan of interval index[0], which performs a binary search, so Josh's suggestion is the one I prefer as well (the implementation might sometimes optimize by transforming it into a table lookup like the other solutions). Searching for +`≠¨ in my BQN files turns up a few uses, including one used to group primitives into types in a utility involved in compiling BQN[1] and an annotated function used a few times in the markdown processor that builds BQN's website[2].
[0] https://aplwiki.com/wiki/Interval_Index
[1] https://github.com/mlochbaum/BQN/blob/717555b0db/src/pr.bqn#...
[2] https://github.com/mlochbaum/BQN/blob/717555b0db/md.bqn#L45-...
This is about the APL language.
std::iota is influenced by APL, see Notes in https://en.cppreference.com/w/cpp/algorithm/iota.html
Been working on the design of an optimizer for my APL VM and asked Claude how this would fit in (as we don't have Dyalog extensions):
iBurg is the Bottom-Up Rewrite System (BURS) based optimizer to operate over the continuation graphs the parser spits out, not sure where the 'i' part came from though...