Difference between revisions of "Empty array"

From APL Wiki
Jump to navigation Jump to search
Miraheze>Adám Brudzewsky
m (8 revisions imported: Migrate from miraheze)
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
In the APL [[array model]], an '''empty''' array is one with a [[bound]] of zero, that is, an array with no [[elements]]. While a nested list model has only one empty list, APL has many different empty arrays. These arrays are distinguished by their [[shape]] and [[prototype]].
+
In the APL [[array model]], an '''empty''' array is one with a [[bound]] of zero, that is, an array with no [[element]]s. While a nested list model has only one empty list, APL has many different empty arrays. These arrays are distinguished by their [[shape]] and [[prototype]].
  
 
Examples of empty arrays are the empty [[numeric]] array [[Zilde]] (<source lang=apl inline>⍬</source>) and the empty [[character]] array <source lang=apl inline>''</source>. These arrays have different prototypes, and do not [[match]] in most APLs.
 
Examples of empty arrays are the empty [[numeric]] array [[Zilde]] (<source lang=apl inline>⍬</source>) and the empty [[character]] array <source lang=apl inline>''</source>. These arrays have different prototypes, and do not [[match]] in most APLs.
Line 5: Line 5:
 
== Empty array shape ==
 
== Empty array shape ==
  
The shape of an empty array is usually determined by shape arithmetic in the function which produces it. Because in most [[primitive functions]] the result shape is determined by the argument shapes and sometimes the numeric values of elements from the arguments (for instance, in the left argument of [[Reshape]]), the shape of an empty array is rarely in doubt.
+
The shape of an empty array is usually determined by shape arithmetic in the function which produces it. Because in most [[primitive function]]s the result shape is determined by the argument shapes and sometimes the numeric values of elements from the arguments (for instance, in the left argument of [[Reshape]]), the shape of an empty array is rarely in doubt.
  
The primary exception is when using the [[Rank operator]] on an array with no [[cells]] of the specified rank. Because the shape of each result cell might be determined by values in an argument cell, the appropriate shape may be impossible to determine.
+
The primary exception is when using the [[Rank operator]] on an array with no [[cell]]s of the specified rank. Because the shape of each result cell might be determined by values in an argument cell, the appropriate shape may be impossible to determine.
 
<source lang=apl>
 
<source lang=apl>
 
       ⍴ ⍳⍤0 ⊢2⍴3
 
       ⍴ ⍳⍤0 ⊢2⍴3
Line 19: Line 19:
 
The example above shows how an arithmetic rule can fail when using Rank with an empty array. For any positive integer <source lang=apl inline>n</source>, it's clear that <source lang=apl inline>(n,3) ≡ ⍴ ⍳⍤0 ⊢n⍴3</source> because each result cell is the array <source lang=apl inline>⍳3</source>. However, the empty array <source lang=apl inline>0⍴3</source> is indistinguishable from any other empty numeric array because it has shape <source lang=apl inline>,0</source> and prototype <source lang=apl inline>0</source>. This means Rank cannot determine the appropriate result shape. The Rank operator still attempts to find a sensible result shape: it executes the operand on a prototype cell obtained by reshaping the argument to the argument cell shape (here, the prototype cell is a scalar <source lang=apl inline>0</source>), and uses the resulting shape to determine the shape of its final result. In this case, this succeeds in finding the appropriate result rank but not the desired shape.
 
The example above shows how an arithmetic rule can fail when using Rank with an empty array. For any positive integer <source lang=apl inline>n</source>, it's clear that <source lang=apl inline>(n,3) ≡ ⍴ ⍳⍤0 ⊢n⍴3</source> because each result cell is the array <source lang=apl inline>⍳3</source>. However, the empty array <source lang=apl inline>0⍴3</source> is indistinguishable from any other empty numeric array because it has shape <source lang=apl inline>,0</source> and prototype <source lang=apl inline>0</source>. This means Rank cannot determine the appropriate result shape. The Rank operator still attempts to find a sensible result shape: it executes the operand on a prototype cell obtained by reshaping the argument to the argument cell shape (here, the prototype cell is a scalar <source lang=apl inline>0</source>), and uses the resulting shape to determine the shape of its final result. In this case, this succeeds in finding the appropriate result rank but not the desired shape.
  
If Rank is implemented by [[Split|splitting]] the argument(s) into cells, applying the operand with [[Each]], and [[Mix|mixing]], then the above problem actually becomes an issue of empty array prototypes: the result of split is empty, and calling Each on an empty array uses prototypes to determine prototypes, an unreliable operation.
+
If Rank is implemented by [[split]]ting the argument(s) into cells, applying the operand with [[Each]], and [[mix]]ing, then the above problem actually becomes an issue of empty array prototypes: the result of Split is empty, and calling Each on an empty array uses prototypes to determine prototypes, an unreliable operation.
  
 
== Empty array prototype ==
 
== Empty array prototype ==
  
Because an empty array has no [[elements]] from which a [[prototype]] could be derived, prototype or type information must be stored with the array.
+
Because an empty array has no [[element]]s from which a [[prototype]] could be derived, prototype or type information must be stored with the array.
  
 
Determining the prototype of an empty array when it is produced is often difficult, and may break identities even for simple functions. An empty array's prototype is far less reliable than its shape.
 
Determining the prototype of an empty array when it is produced is often difficult, and may break identities even for simple functions. An empty array's prototype is far less reliable than its shape.
  
Consider the following identities for [[Catenate]] on [[vectors]], one of which is empty.
+
Consider the following identities for [[Catenate]] on [[vector]]s, one of which is empty.
 
<source lang=apl>
 
<source lang=apl>
 
a ≡ ⍬,a
 
a ≡ ⍬,a
Line 45: Line 45:
 
== Reduction over a length-0 axis ==
 
== Reduction over a length-0 axis ==
  
If a [[reduce|reduction]] (using one of <source lang=apl inline>/</source>, <source lang=apl inline>⌿</source>, <source lang=apl inline>\</source>, or <source lang=apl inline>⍀</source>)is performed over an axis of length 0, the resulting array is filled with [[identity element]]s. For example, the sum of an empty list is 0 because the identity element for [[addition]] is 0:
+
If a [[Reduce|reduction]] (using one of <source lang=apl inline>/</source>, <source lang=apl inline>⌿</source>, <source lang=apl inline>\</source>, or <source lang=apl inline>⍀</source>) is performed over an axis of length 0, the resulting array is filled with [[identity element]]s. For example, the sum of an empty list is <source lang=apl inline>0</source> because the identity element for [[addition]] is <source lang=apl inline>0</source>:
 
<source lang=apl>
 
<source lang=apl>
 
       +/0⍴0
 
       +/0⍴0
 
0
 
0
 
</source>
 
</source>
The identity element for a specific reduction always depends on the operand, and may depend on the argument array prototype. Dialects differ in their support for such reductions. All define identity elements for most [[scalar functions#Standard scalar functions|scalar primitives]], and some stop there (e.g. [[SAX]]), while others (e.g. [[Dyalog APL]] and [[APL2]]) define identity elements for various [[mixed functions]].
+
The identity element for a specific reduction always depends on the operand, and may depend on the argument array prototype. Dialects differ in their support for such reductions. All define identity elements for most [[scalar functions#Standard scalar functions|scalar primitives]], and some stop there (e.g. [[SAX]]), while others (e.g. [[Dyalog APL]] and [[APL2]]) define identity elements for various [[mixed function]]s.
{{APL programming language}}
+
{{APL features}}

Revision as of 15:24, 20 November 2019

In the APL array model, an empty array is one with a bound of zero, that is, an array with no elements. While a nested list model has only one empty list, APL has many different empty arrays. These arrays are distinguished by their shape and prototype.

Examples of empty arrays are the empty numeric array Zilde () and the empty character array ''. These arrays have different prototypes, and do not match in most APLs.

Empty array shape

The shape of an empty array is usually determined by shape arithmetic in the function which produces it. Because in most primitive functions the result shape is determined by the argument shapes and sometimes the numeric values of elements from the arguments (for instance, in the left argument of Reshape), the shape of an empty array is rarely in doubt.

The primary exception is when using the Rank operator on an array with no cells of the specified rank. Because the shape of each result cell might be determined by values in an argument cell, the appropriate shape may be impossible to determine.

       0 23
2 3
       0 13
1 3
       0 03
0 0
Works in: Dyalog APL, NARS2000

The example above shows how an arithmetic rule can fail when using Rank with an empty array. For any positive integer n, it's clear that (n,3) 0 n3 because each result cell is the array 3. However, the empty array 03 is indistinguishable from any other empty numeric array because it has shape ,0 and prototype 0. This means Rank cannot determine the appropriate result shape. The Rank operator still attempts to find a sensible result shape: it executes the operand on a prototype cell obtained by reshaping the argument to the argument cell shape (here, the prototype cell is a scalar 0), and uses the resulting shape to determine the shape of its final result. In this case, this succeeds in finding the appropriate result rank but not the desired shape.

If Rank is implemented by splitting the argument(s) into cells, applying the operand with Each, and mixing, then the above problem actually becomes an issue of empty array prototypes: the result of Split is empty, and calling Each on an empty array uses prototypes to determine prototypes, an unreliable operation.

Empty array prototype

Because an empty array has no elements from which a prototype could be derived, prototype or type information must be stored with the array.

Determining the prototype of an empty array when it is produced is often difficult, and may break identities even for simple functions. An empty array's prototype is far less reliable than its shape.

Consider the following identities for Catenate on vectors, one of which is empty.

a  ,a
b  b,''

These identities always hold when a and b are non-empty, because the result is non-empty and its elements are entirely determined by the non-empty argument. However, if we consider the catenation

,''

then the first identity tells us that the result should be '' while the second gives a result of . These two arrays do not match, so one of the identities must be wrong! In fact, the choice of which prototype to use for the result is a source of incompatibility among APLs. In Dyalog APL it has even been changed in the past. At one point the right argument's prototype was used; now we can inspect the first element of ,'' to see that the left argument's prototype is used.

      ,''
0
Works in: Dyalog APL

Reduction over a length-0 axis

If a reduction (using one of /, , \, or ) is performed over an axis of length 0, the resulting array is filled with identity elements. For example, the sum of an empty list is 0 because the identity element for addition is 0:

      +/00
0

The identity element for a specific reduction always depends on the operand, and may depend on the argument array prototype. Dialects differ in their support for such reductions. All define identity elements for most scalar primitives, and some stop there (e.g. SAX), while others (e.g. Dyalog APL and APL2) define identity elements for various mixed functions.

APL features [edit]
Built-ins Primitive functionPrimitive operatorQuad name
Array model ShapeRankDepthBoundIndex (Indexing) ∙ AxisRavelRavel orderElementScalarVectorMatrixSimple scalarSimple arrayNested arrayCellMajor cellSubarrayEmpty arrayPrototype
Data types Number (Boolean, Complex number) ∙ Character (String) ∙ BoxNamespace
Concepts and paradigms Leading axis theoryScalar extensionConformabilityScalar functionPervasionGlyphIdentity elementComplex floorTotal array ordering
Errors LIMIT ERRORRANK ERRORSYNTAX ERRORDOMAIN ERRORLENGTH ERRORINDEX ERRORVALUE ERROR