4,493
edits
Indices: Difference between revisions
Jump to navigation
Jump to search
m
Text replacement - "<source" to "<syntaxhighlight"
Miraheze>Adám Brudzewsky No edit summary |
m (Text replacement - "<source" to "<syntaxhighlight") |
||
| (30 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
:''This | :''This page about finding indices of non-zero values. See [[Index]] for the page on indices themselves. See [[Indexing]], [[Index Generator]], [[Index of]], and [[Interval Index]] for other operations named after indices.'' | ||
{{Built-in|Indices|⍸}} or '''Where''', is a [[monadic]] [[primitive function]] which returns the [[Index|indices]] of all ones in a [[ | {{Built-in|Indices|⍸}}, or '''Where''', is a [[monadic]] [[primitive function]] which returns the [[Index|indices]] of all ones in a [[Boolean]] array. More generally, Indices accepts an array of non-negative integers and copies each index the corresponding number of times. It is closely related to [[Replicate]], and may be seen as an index-based equivalent to Replicate in the same way that [[Grade]] is an index-based equivalent of sorting. | ||
In [[K]], the first language to include the primitive, it is called Where (<code>&</code>). In [[J]], it is called Indices (<syntaxhighlight lang=j inline>I.</syntaxhighlight>). | |||
== Examples == | == Examples == | ||
In all implementations, Indices gives the indices of ones in a | In all implementations, Indices gives the indices of ones in a Boolean [[vector]]. | ||
< | <syntaxhighlight lang=apl> | ||
⍸ 0 0 1 0 0 0 1 0 | ⍸ 0 0 1 0 0 0 1 0 | ||
3 7 | 3 7 | ||
</ | </syntaxhighlight> | ||
{{Works in|[[Dyalog APL]], [[dzaima/APL]], [[NARS2000]]}} | {{Works in|[[Dyalog APL]], [[dzaima/APL]], [[NARS2000]]}} | ||
In [[Nested array model|nested]] APLs it returns nested indices when passed a [[matrix]] or higher-dimensional array. | In [[Nested array model|nested]] APLs it returns nested indices when passed a [[matrix]] or higher-dimensional array. | ||
< | <syntaxhighlight lang=apl> | ||
⍸ 3 3⍴0 0 1 0 0 0 1 0 | ⍸ 3 3⍴0 0 1 0 0 0 1 0 | ||
┌───┬───┐ | ┌───┬───┐ | ||
| Line 24: | Line 24: | ||
││ | ││ | ||
└┘ | └┘ | ||
</ | </syntaxhighlight> | ||
{{Works in|[[Dyalog APL]], [[dzaima/APL]], [[NARS2000]]}} | {{Works in|[[Dyalog APL]], [[dzaima/APL]], [[NARS2000]]}} | ||
If numbers higher than 1 are allowed, they indicate that the index of the number is repeated. Negative numbers are never allowed. | If numbers higher than 1 are allowed, they indicate that the index of the number is repeated. Negative numbers are never allowed. | ||
< | <syntaxhighlight lang=apl> | ||
⍸ 3 0 2 | ⍸ 3 0 2 | ||
1 1 1 3 3 | 1 1 1 3 3 | ||
</ | </syntaxhighlight> | ||
{{Works in|[[dzaima/APL]], [[NARS2000]]}} | {{Works in|[[dzaima/APL]], [[NARS2000]]}} | ||
| Line 37: | Line 37: | ||
Indices [[Replicate|replicates]] each index in the argument by the number of times it appears. It is identical to the APL function: | Indices [[Replicate|replicates]] each index in the argument by the number of times it appears. It is identical to the APL function: | ||
< | <syntaxhighlight lang=apl> | ||
Where ← {(,⍵)⌿,⍳⍴⍵} | Where ← {(,⍵)⌿,⍳⍴⍵} | ||
</ | </syntaxhighlight> | ||
{{Works in|[[Dyalog APL]], [[dzaima/APL]], [[NARS2000]], [[ngn/apl]]}} | {{Works in|[[Dyalog APL]], [[dzaima/APL]], [[NARS2000]], [[ngn/apl]]}} | ||
The argument is restricted to be an array of non-negative integers, or, in [[Dyalog APL]], | The argument is restricted to be an array of non-negative integers, or, in [[Dyalog APL]], Booleans. | ||
Because Indices returns indices (like [[Iota]]), it is subject to [[index origin]]. | Because Indices returns indices (like [[Iota]]), it is subject to [[index origin]]. | ||
| Line 50: | Line 50: | ||
== Mathematical interpretation == | == Mathematical interpretation == | ||
Indices may be viewed as a way to convert between two ways of writing [ | Indices may be viewed as a way to convert between two ways of writing [[wikipedia:multiset|multiset]]s of array [[Index|indices]]. The argument uses a dense representation indicating for each index the number of times it appears, and the result uses a sparse representation which lists all the indices contained in the set. | ||
== | == Relation with Replicate == | ||
[ | Indices on a [[vector]] is closely related to [[Replicate]]: for vectors <syntaxhighlight lang=apl inline>V</syntaxhighlight> and <syntaxhighlight lang=apl inline>W</syntaxhighlight>, we have <syntaxhighlight lang=apl inline>⍸V</syntaxhighlight> {{←→}} <syntaxhighlight lang=apl inline>V/⍳≢V</syntaxhighlight> and <syntaxhighlight lang=apl inline>V⌿X</syntaxhighlight> {{←→}} <syntaxhighlight lang=apl inline>X[⍸V]</syntaxhighlight>. While Replicate performs a transformation on another array, Indices gives a representation of that transformation using [[Index|indices]]. The relationship between Indices and Replicate parallels that between [[Grade]] and [[Sort By]]. | ||
[ | [[K]] takes advantage of this relationship by removing the primitive Replicate entirely: the glyph <code>&</code> is paired with [[Minimum]] instead. In K, Replicate is performed by using Where and then [[Bracket indexing|indexing]]. | ||
== Inverse == | |||
== | The [[inverse]] of Indices, <syntaxhighlight lang=apl inline>⍸⍣¯1</syntaxhighlight>, is the mapping from an ordered (multi-)set of indices to an array where each element is the count for its position. For a simple non-empty vector <syntaxhighlight lang=apl inline>Y</syntaxhighlight> without duplicates, the expression <syntaxhighlight lang=apl inline>R←(⍸⍣¯1)Y</syntaxhighlight> gives a Boolean vector <syntaxhighlight lang=apl inline>R</syntaxhighlight> with ones at the indices in <syntaxhighlight lang=apl inline>Y</syntaxhighlight>. This is equivalent to <syntaxhighlight lang=apl inline>R←(1@Y)0⍴⍨⌈/Y</syntaxhighlight> which is useful in conversion between [[partition representations]]. | ||
[https://chat.stackexchange.com/transcript/52405?m=41724812#41724812 APL Cultivation] | It should be noted that the inverse is not unique because <syntaxhighlight lang=apl inline>(⍸Y) ≡ (⍸Z)</syntaxhighlight> if <syntaxhighlight lang=apl inline>Y</syntaxhighlight> and <syntaxhighlight lang=apl inline>Z</syntaxhighlight> differ only by the number of trailing zeros. <syntaxhighlight lang=apl inline>⍸⍣¯1</syntaxhighlight> does not add any trailing zeros, and it may be necessary to add those separately, for example using [[overtake]]. | ||
{{APL built-ins}} | |||
== History == | |||
[[Idiom]]s with similar behavior to Indices were widely used in APL long before it was made into a primitive. For example, the [[FinnAPL idiom library]], first presented in 1984, lists <syntaxhighlight lang=apl inline>X/⍳⍴X</syntaxhighlight> as "594. Indices of ones in logical vector X". | |||
Where (<code>&</code>) with a Boolean argument was present in [[K]] by K2 in 1996,<ref>Kx Systems. [http://web.archive.org/web/20041022042401/http://www.kx.com/technical/documents/kusrlite.pdf "K User Manual"]. 1998.</ref> and extended to non-negative integers by K4 in 2000. It was added to [[J]] for the domain of non-negative integer vectors as Indices (<syntaxhighlight lang=j inline>I.</syntaxhighlight>) in release 5.02 (2003), introducing the pairing of Indices and [[Interval Index]] now used in APL.<ref>Jsoftware. [https://www.jsoftware.com/docs/archive/release/ifb.htm "I. Implements ''Indices'']. 2003.</ref> | |||
Indices (<syntaxhighlight lang=apl inline>⍸</syntaxhighlight>) was first introduced to APL, and the [[nested array model]], by [[NARS2000]]. Originally defined only for vectors, the generalised definition <syntaxhighlight lang=apl inline>(,R)/,⍳⍴1/R</syntaxhighlight> was introduced in about 2013 after some experimentation with alternatives.<ref>NARS2000 Wiki. [http://wiki.nars2000.org/index.php?title=Indices&direction=next&oldid=863 Indices]. Old revision: 2013-05-26.</ref> Where (<syntaxhighlight lang=apl inline>⍸</syntaxhighlight>) was added to [[Dyalog APL 16.0]] (June 2017), with the nearly-identical definition <syntaxhighlight lang=apl inline>{(,⍵)⌿,⍳⍴⍵}</syntaxhighlight>, but also with the restriction that the argument be Boolean. This restriction that was lifted to allow non-negative integers in [[Dyalog APL 18.0|18.0]] (2020). For a [[scalar]] <syntaxhighlight lang=apl inline>I</syntaxhighlight>, Dyalog's definition gives <syntaxhighlight lang=apl inline>I⍴⊂⍬</syntaxhighlight> for <syntaxhighlight lang=apl inline>⍸I</syntaxhighlight>, while NARS2000 returned <syntaxhighlight lang=apl inline>I⍴1</syntaxhighlight>. By January 2018, NARS2000 switched to Dyalog's definition, removing the discrepancy for scalar arguments. | |||
The [[#inverse|inverse]] of Indices became supported with [[Dyalog APL 18.0]]. | |||
== External links == | |||
=== Lessons === | |||
* [https://chat.stackexchange.com/transcript/52405?m=41724812#41724812 APL Cultivation] | |||
=== Documentation === | |||
* [https://help.dyalog.com/latest/index.htm#Language/Primitive%20Functions/Where.htm Dyalog] | |||
* [http://wiki.nars2000.org/index.php/Indices NARS2000] | |||
* J [https://www.jsoftware.com/help/dictionary/dicapdot.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/icapdot NuVoc] (as <syntaxhighlight lang=j inline>I.</syntaxhighlight>) | |||
* [https://mlochbaum.github.io/BQN/doc/replicate.html#indices BQN] (as <code>/</code>) | |||
* [https://github.com/kevinlawler/kona/wiki/Where Kona (K3)] (as <code>&</code>) | |||
== References == | |||
<references /> | |||
{{APL built-ins}}[[Category:Primitive functions]] | |||