Library support for multidimensional arrays

[cgranade]

Library support for multidimensional arrays

Abstract and conceptual overview

Q# currently provides the array type 'T[] for any type 'T. By using arrays of arrays (i.e.: 'T[][]), Q# allows for representing multidimensional data. As discussed at microsoft/qsharp-language#49, however, using nested arrays in this way presents a number of limitations.

This proposal builds on the work in microsoft/qsharp-language#49 by providing a number of different library functions and operations to support the new multidimensional arrays in the corresponding Q# language proposal. For details on the motivation, justification, and context for both proposals, please see microsoft/qsharp-language#49.

Proposal

New and modified functions and operations

This proposal introduces new functions and operations for creating, manipulating, and transforming multidimensional arrays (i.e.: values of type [|'T|], [||'T||], and so forth), extending the Microsoft.Quantum.Array namespace to support the new types introduced by microsoft/qsharp-language#49. To distinguish functions acting on multidimensional arrays of distinct ranks, suffixes are used to denote the rank each function or operation acts on (e.g.: EmptyArray2 returns a value of type [|'T|] while EmptyArray3 returns a value of type [||'T||]). For brevity, we list only the rank-1, rank-2, and rank-3 variants of each proposed addition here, but the pattern should be continued to include multidimensional arrays of rank up to and including 8. For details on how to remove these suffixes using bounded polymorphism, please see "Relationship to Q# language feature proposals," below.

As an implementation detail, all of the functions and operations proposed here can be written in pure Q#, using the functions described in microsoft/qsharp-language#49 to create and deconstruct multidimensional arrays from their underlying strides, offsets, and sizes.

• namespace Microsoft.Quantum.Arrays
  • Concatenation
    • function Concatenated<'T>(left : 'T[], right : 'T[]) : ['T]
    • function Concatenated2<'T>(axis : Int, left : [|'T|], right : [|'T|]) : [|'T|]
    • function Concatenated3<'T>(axis : Int, left : [||'T||], right : [||'T||]) : [||'T||]
  • Array creation
    • Multidimensional from jagged:
      These functions convert jagged (aka nested) arrays to multidimensional arrays, failing when the input is not rectangular in shape (e.g.: [[1], [2, 3]]).
      • function JaggedAsRectangular2<'T>(jagged : [['T]]) : [|'T|]
      • function JaggedAsRectangular3<'T>(jagged : [[['T]]]) : [||'T||]
    • Diagonal arrays:
      These functions create new multidimensional arrays given a one-dimensional array of data to be applied along the diagonal (e.g.: DiagonalArray2(0, [1, 2])) returns [|1, 0|, |0, 2|]).
      • function DiagonalArray2<'T>(zero : 'T, diag : 'T[]) : [|'T|]
      • function DiagonalArray3<'T>(zero : 'T, diag : 'T[]) : [||'T||]
    • Constant arrays:
      These functions extend the existing ConstantArray function to apply to multidimensional arrays.
      • function ConstantArray2<'T>(size : (Int, Int), value : 'T) : [|'T|]
      • function ConstantArray3<'T>(size : (Int, Int, Int), value : 'T) : [||'T||]
    • Empty arrays:
      These functions return empty arrays of given types and rank.
      • function EmptyArray2<'T>() : [|'T|]
      • function EmptyArray3<'T>() : [||'T||]
  • Array metadata, accessors and deconstructors
    • Size: returns the extent along each axis of a multidimensional array
      • function Size2<'T>(array : [|'T|]) : (Int, Int)
      • function Size3<'T>(array : [||'T||]) : (Int, Int, Int)
    • Element at:
      returns an element at a given index, mainly useful in combinators and partial application.
      • function ElementAt2<'T>(index : (Int, Int), array : [|'T|]) : 'T
      • function ElementAt3<'T>(index : (Int, Int, Int), array : [||'T||]) : 'T
    • Diagonal:
      returns all elements along the diagonal of a multidimensional array as a one-dimensional array (e.g.: [arr[(0, 0, 0)], arr[(1, 1, 1)], arr[(2, 2, 2)], ...]).
      • function Diagonal2<'T>(array : [|'T|]) : ['T]
      • function Diagonal3<'T>(array : [||'T||]) : ['T]
    • Subarray:
      extracts the given elements of a multidimensional array into a one-dimensional array.
      • function Subarray2<'T>(indices : (Int, Int)[], array : [|'T|]) : ['T]
      • function Subarray3<'T>(indices : (Int, Int, Int)[], array : [||'T||]) : ['T]
  • Reduction
    • Folded along axes:
      These functions generalize the existing Fold by computing folds along each axis of a multidimensional array.
      • function FoldedAlongAxis2<'TInput, 'TOutput>(reduction : (['TInput] -> 'TOutput), axis : Int, array : [|'TInput|]) : ['TOutput]
      • function FoldedAlongAxis3<'TInput, 'TOutput>(reduction : (['TInput] -> 'TOutput), axis : Int, array : [||'TInput||]) : [|'TOutput|]
  • Linear algebra
    • Tensor contractions:
      These functions calculate generalized tensor contractions, with functions being provided for addition and multiplication.
      • function TensorDot2With2<'T>(plus : (('T, 'T) -> 'T), times : (('T, 'T) -> 'T), (idxLeft : Int, idxRight : Int), left : [|'T|], right : [|'T|]) : [|'T|]
      • function TensorDot3With2<'T>(plus : (('T, 'T) -> 'T), times : (('T, 'T) -> 'T), (idxLeft : Int, idxRight : Int), left : [||'T||], right : [|'T|]) : [||'T||]
      • function TensorDot2With3<'T>(plus : (('T, 'T) -> 'T), times : (('T, 'T) -> 'T), (idxLeft : Int, idxRight : Int), left : [|'T|], right : [||'T||]) : [||'T||]
      • function TensorDot3With3<'T>(plus : (('T, 'T) -> 'T), times : (('T, 'T) -> 'T), (idxLeft : Int, idxRight : Int), left : [||'T||], right : [||'T||]) : [|||'T|||]
    • Matrix dot products:
      These functions specialize tensor contractions to common applications (e.g.: vectors and matrices of Double or Complex elements)
      • function Dot11D(left : [Double], right : [Double]) : Double
      • function Dot11C(left : [Complex], right : [Complex]) : Complex
      • function Dot12D(left : [Double], right : [|Double|]) : [Double]
      • function Dot21D(left : [|Double|], right : [Double]) : [Double]
      • function Dot22D(left : [|Double|], right : [|Double|]) : [|Double|]
    • Hermitian conjugation
      • function Dagger(array : [|Complex|]) : [|Complex|]
  • Element-wise operations:
    These functions take scalar functions and apply them elementwise between two multidimensional arrays, broadcasting as necessary.
    • function Elementwise2<'TLeft, 'TRight, 'TOutput>(fn : (('TLeft, 'TRight) -> 'TOutput)) : (([|'TLeft|], [|'TRight|]) -> [|'TOutput|])
      For example: Elementwise2(TimesD)(left, right) returns the elementwise product of each element in left and right.
    • function Elementwise3<'TLeft, 'TRight, 'TOutput>(fn : (('TLeft, 'TRight) -> 'TOutput)) : (([||'TLeft||], [||'TRight||]) -> [||'TOutput||])
  • Reshaping and broadcasting
    • Reshape: These functions convert one-dimensional and multidimensional arrays to multidimensional arrays of a given shape.
      • function Reshaped1To2<'T>(array : ['T], newShape : (Int, Int)) : [|'T|]
      • function Reshaped1To3<'T>(array : ['T], newShape : (Int, Int, Int)) : [||'T||]
      • function Reshaped2To3<'T>(array : [|'T|], newShape : (Int, Int, Int)) :[|| 'T||,]
      • function Reshaped3To3<'T>(array : [||'T||], newShape : (Int, Int, Int)) :[|| 'T||,]
      • function Reshaped3To2<'T>(array : [||'T||], newShape : (Int, Int)) : [|'T|]
    • Broadcast:
      These functions repeat elements of multidimensional arrays as needed to produce arrays of the same shape.
      • function Broadcasted2<'T0, 'T1>(in0 : 'T0[,], in1 : 'T1[,]) : ('T0[,], 'T1[,])
      • function Broadcasted3<'T0, 'T1>(in0 : 'T0[,,], in1 : 'T1[,,]) : ('T0[,,], 'T1[,,])
    • Transposition
      • function Transposed2<'T>(data : [|'T|]) : [|'T|]
      • function Transposed3<'T>(axes : (Int, Int, Int), data : [||'T||]) : [||'T||]
      • function Transposed4<'T>(axes : (Int, Int, Int, Int), data : [|||'T|||]) : [|||'T|||]

Note that the list above does not include a few functions common in other frameworks, deferring to language Q# support in such cases (e.g.: np.ones((3, 3)) can be replaced by [| 1.0, size=(3, 3) |]).

Examples

TODO

Relationship to Q# language feature proposals

Bounded polymorphism (microsoft/qsharp-language#149)

The use of rank suffixes could be largely eliminated by using bounded polymorphism to represent common patterns, such as indexing and size.

For example:

concept 'TArray is IndexedBy<'TIndex, 'TElement> when {
    unction ElementAt(index : 'TIndex, array : 'TArray) : 'TElement;f
}
example <'T> ['T] is IndexedBy<Int, 'T> { ... }
example <'T> ['T] is IndexedBy<Range, 'T[]> { ... }
example <'T> [|'T|] is IndexedBy<(Int, Int), 'T> { ... }
example <'T> [|'T|] is IndexedBy<(Range, Int), ['T]> { ... }
example <'T> [|'T|] is IndexedBy<(Int, Range), ['T]> { ... }
example <'T> [|'T|] is IndexedBy<(Range, Range), [|'T|]> { ... }

function Subarray<'TArray, 'TIndex, 'TElement where 'TArray is IndexedBy<'TIndex, 'TElement>>(
    indices : ['TIndex], array : 'TArray
)
: 'TElement {
    return Mapped(ElementAt(_, array), indices);
}

Open design questions and considerations

• Suffixes like 2 and 3 are also used to indicate the number of inputs, as in Zipped2; how can we disambiguate these two uses?

[cgranade]

Edited to reflect recent changes in microsoft/qsharp-language#49.

[msoeken]

Thanks for the proposal, @cgranade. Here are some comments:

• The return type seems broken in Reshaped2To3 and Reshaped3To3
• Will there be a function called Size for consistency with Size2 and Size3. Would this function be identical to Length?

[cgranade]

Thanks for the proposal, @cgranade. Here are some comments:

• The return type seems broken in Reshaped2To3 and Reshaped3To3

Thanks for catching that typo!

• Will there be a function called Size for consistency with Size2 and Size3. Would this function be identical to Length?

I'm somewhat reticent to introduce another function that is identical to Length but that has a different name; perhaps it would be worth renaming Length instead?