Indices: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
Miraheze>Marshall
mNo edit summary
m (Text replacement - "<source" to "<syntaxhighlight")
(25 intermediate revisions by 5 users not shown)
Line 1: Line 1:
:''This page describes a primitive whose result is a list of indices. See [[Index]] for the page on indices themselves. See [[Index of]] for the index generator.''
:''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 [[Boolean]] array. More generally, Indices accepts an array of non-negative integers and copies each index the corresponding number of times.
{{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.


Indices was introduced in [[J]] as <source lang=j inline>I.</source> and is present in [[K]] as <source lang=k inline>&</source>.
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 Boolean [[vector]].
In all implementations, Indices gives the indices of ones in a Boolean [[vector]].
<source lang=apl>
<syntaxhighlight lang=apl>
       ⍸ 0 0 1 0 0 0 1 0
       ⍸ 0 0 1 0 0 0 1 0
3 7
3 7
</source>
</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.
<source lang=apl>
<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:
││
││
└┘
└┘
</source>
</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.
<source lang=apl>
<syntaxhighlight lang=apl>
       ⍸ 3 0 2
       ⍸ 3 0 2
1 1 1 3 3
1 1 1 3 3
</source>
</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:
<source lang=apl>
<syntaxhighlight lang=apl>
Where ← {(,⍵)⌿,⍳⍴⍵}
Where ← {(,⍵)⌿,⍳⍴⍵}
</source>
</syntaxhighlight>
{{Works in|[[Dyalog APL]], [[dzaima/APL]], [[NARS2000]], [[ngn/apl]]}}
{{Works in|[[Dyalog APL]], [[dzaima/APL]], [[NARS2000]], [[ngn/apl]]}}


Line 50: Line 50:
== Mathematical interpretation ==
== Mathematical interpretation ==


Indices may be viewed as a way to convert between two ways of writing [https://en.wikipedia.org/wiki/Multiset multisets] 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.
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.


== Documentation ==
== Relation with Replicate ==


[http://help.dyalog.com/latest/index.htm#Language/Primitive%20Functions/Where.htm Dyalog]
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]].


[http://wiki.nars2000.org/index.php/Indices NARS2000]
[[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]].


J [https://www.jsoftware.com/help/dictionary/dicapdot.htm Dictionary], [https://code.jsoftware.com/wiki/Vocabulary/icapdot NuVoc]
== Inverse ==


== Other resources ==
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]]

Revision as of 22:15, 10 September 2022

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.

Indices (), or Where, is a monadic primitive function which returns the 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 (&). In J, it is called Indices (I.).

Examples

In all implementations, Indices gives the indices of ones in a Boolean vector.

      ⍸ 0 0 1 0 0 0 1 0
3 7

In nested APLs it returns nested indices when passed a matrix or higher-dimensional array.

      ⍸ 3 3⍴0 0 1 0 0 0 1 0
┌───┬───┐
│1 3│3 1│
└───┴───┘
      ⍸ 1   ⍝ An index into a scalar is empty!
┌┐
││
└┘

If numbers higher than 1 are allowed, they indicate that the index of the number is repeated. Negative numbers are never allowed.

      ⍸ 3 0 2
1 1 1 3 3
Works in: dzaima/APL, NARS2000

Description and APL model

Indices replicates each index in the argument by the number of times it appears. It is identical to the APL function:

Where ← {(,⍵)⌿,⍳⍴⍵}

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.

The only flat array language which implements Indices is J. Because J's Iota does not return multidimensional indices, J defines Indices to have function rank 1 so that only vector indices are used.

Mathematical interpretation

Indices may be viewed as a way to convert between two ways of writing multisets of array 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 V and W, we have ⍸V V/⍳≢V and V⌿X X[⍸V]. While Replicate performs a transformation on another array, Indices gives a representation of that transformation using 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 & is paired with Minimum instead. In K, Replicate is performed by using Where and then indexing.

Inverse

The inverse of Indices, ⍸⍣¯1, 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 Y without duplicates, the expression R←(⍸⍣¯1)Y gives a Boolean vector R with ones at the indices in Y. This is equivalent to R←(1@Y)0⍴⍨⌈/Y which is useful in conversion between partition representations.

It should be noted that the inverse is not unique because (⍸Y) ≡ (⍸Z) if Y and Z differ only by the number of trailing zeros. ⍸⍣¯1 does not add any trailing zeros, and it may be necessary to add those separately, for example using overtake.

History

Idioms 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 X/⍳⍴X as "594. Indices of ones in logical vector X".

Where (&) with a Boolean argument was present in K by K2 in 1996,[1] 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 (I.) in release 5.02 (2003), introducing the pairing of Indices and Interval Index now used in APL.[2]

Indices () was first introduced to APL, and the nested array model, by NARS2000. Originally defined only for vectors, the generalised definition (,R)/,⍳⍴1/R was introduced in about 2013 after some experimentation with alternatives.[3] Where () was added to Dyalog APL 16.0 (June 2017), with the nearly-identical definition {(,⍵)⌿,⍳⍴⍵}, but also with the restriction that the argument be Boolean. This restriction that was lifted to allow non-negative integers in 18.0 (2020). For a scalar I, Dyalog's definition gives I⍴⊂⍬ for ⍸I, while NARS2000 returned I⍴1. By January 2018, NARS2000 switched to Dyalog's definition, removing the discrepancy for scalar arguments.

The inverse of Indices became supported with Dyalog APL 18.0.

External links

Lessons

Documentation

References

  1. Kx Systems. "K User Manual". 1998.
  2. Jsoftware. "I. Implements Indices. 2003.
  3. NARS2000 Wiki. Indices. Old revision: 2013-05-26.
APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic ConjugateNegateSignumReciprocalMagnitudeExponentialNatural LogarithmFloorCeilingFactorialNotPi TimesRollTypeImaginarySquare Root
Dyadic AddSubtractTimesDivideResiduePowerLogarithmMinimumMaximumBinomialComparison functionsBoolean functions (And, Or, Nand, Nor) ∙ GCDLCMCircularComplexRoot
Non-Scalar
Structural ShapeReshapeTallyDepthRavelEnlistTableCatenateReverseRotateTransposeRazeMixSplitEncloseNestCut (K)PairLinkPartitioned EnclosePartition
Selection FirstPickTakeDropUniqueIdentityStopSelectReplicateExpandSet functions (IntersectionUnionWithout) ∙ Bracket indexingIndexCartesian ProductSort
Selector Index generatorGradeIndex OfInterval IndexIndicesDealPrefix and suffix vectors
Computational MatchNot MatchMembershipFindNub SieveEncodeDecodeMatrix InverseMatrix DivideFormatExecuteMaterialiseRange
Operators Monadic EachCommuteConstantReplicateExpandReduceWindowed ReduceScanOuter ProductKeyI-BeamSpawnFunction axis
Dyadic BindCompositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner ProductDeterminantPowerAtUnderRankDepthVariantStencilCutDirect definition (operator)
Quad names Index originComparison toleranceMigration levelAtomic vector