Variation on Iota

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

  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...