Interval Index: Difference between revisions

{{Built-in|Interval Index|⍸}}, or '''Bins''' (<syntaxhighlight lang=apl inline>⍋</source>) in [[A+]] and [[BQN]], is a [[primitive function|primitive]] [[search function]] which locates [[cell]]s of its right [[argument]] relative to cells of a [[sorted]] left argument. Like searching for the right page for a word in a dictionary, knowing the first word on each page, Interval Index finds for each cell (word to search for) an [[index]] (page number) in the left argument (dictionary) so that the target cell is between the [[major cell]] at that index (first word on the page) and the major cell at the following index (first word on the next page). In general computer science, this problem is known as a '''predecessor search''' (see [[wikipedia:predecessor problem|predecessor problem]]), since it searches for the predecessor—entry immediately preceding—of an array, but may be referred to by the name of a common technique used to solve it, the [[wikipedia:binary search|binary search]]. Interval Index may also be considered a way to perform [[wikipedia:data binning|data binning]].

</source>

In [[J]] the ''last'' letter of each group should be used instead, and the left argument must be converted to a list of [[box]]ed strings: <syntaxhighlight lang=j inline>(<@,"0'DIQZ') I. 'Ken';'Adin';'Larry';'Phil';'Roger'</source>. The results are one smaller, because J uses [[index origin]] 0.

</source>

</source>

</source>

Either definition may be adjusted to use either strict or non-strict precedence, and the result may be offset by some amount. Note that the result in the first case is an [[index]], and should be subject to [[index origin]], while the result in the second is merely a count, and should not. Therefore the definitions are incompatible in any language with variable index origin, and at least one must be adjusted by <syntaxhighlight lang=apl inline>⎕IO</source>.

[[A+]] was the first APL to feature Interval Index as a primitive. Called Bins (<syntaxhighlight lang=apl inline>⍋</source>), it assumed the left argument to be sorted ascending with no duplicates and returned the number of cells strictly less than the target cell, giving right-closed indices. A+ used the same [[High-rank set functions|cell rank convention]] as Find ([[Index Of]]) for Interval Index, a choice that was also adopted in later implementations of the primitive.

Interval Index (<syntaxhighlight lang=j inline>I.</source>) in [[J]] was implemented in release 6.01, available in 2006.<ref>Jsoftware. [https://www.jsoftware.com/docs/archive/release/binsearch.htm I. ''Interval Index'' Implemented]. 2005.</ref> The choice of <syntaxhighlight lang=j inline>I.</source> for a symbol introduced the pairing of Interval Index with the monadic function [[Indices]]. In release 6.02 (2008), [[Index Of]] was extended to allow non-matching cell shapes, but Interval Index was not similarly extended.

Interval Index was also introduced in [[Dyalog APL 16.0]], initially with the requirement that the left argument be sorted ascending with no duplicates. Dyalog extended it by adding [[total array ordering]] in [[Dyalog APL 17.0]], and by removing the no-duplicate requirement in [[Dyalog APL 17.1]]. Dyalog's introduction was the first time the primitive was added to a language with [[index origin]]. The primitive was chosen to depend on <syntaxhighlight lang=apl inline>⎕IO</source>, with its result decreased by 1 relative to A+ and J with index origin 0 in order to accommodate the index origin 1 case (thus, the index origin 1 case matches A+ and J in terms of the possible result indices).

| [[A+]]        || Bins          || <syntaxhighlight lang=apl inline>⍋</source>  || <syntaxhighlight lang=apl inline>0</source>    || (]            || Ascending; no duplicates (unchecked)

| [[J]]          || Interval Index || <syntaxhighlight lang=j inline>I.</source>  || <syntaxhighlight lang=j inline>0</source>      || (]            || Ascending or descending (unchecked)

| [[Dyalog APL]] || Interval Index || <syntaxhighlight lang=apl inline>⍸</source>  || <syntaxhighlight lang=apl inline>⎕IO-1</source> || [)            || Ascending; no duplicates prior to [[Dyalog APL 17.1|17.1]]

| [[BQN]]        || Bins          || <syntaxhighlight lang=apl inline>⍋⍒</source> || <syntaxhighlight lang=apl inline>0</source>    || [)            || Ascending (<syntaxhighlight lang=apl inline>⍋</source>) or descending (<syntaxhighlight lang=apl inline>⍒</source>)