Improvements to Microsoft.Quantum.Arrays

[cgranade]

Abstract

There is a close connection between the iteration over classical values, and generalizing "circuit"-like patterns into high-level code. In Q#, we use exploit this connection with the Microsoft.Quantum.Arrays namespace to make it easier express high-level patterns. We have noted from user feedback, however, that some common patterns are difficult to express using existing array functions, or that users may not be able to discover needed functionality.

The improvements proposed here empower users to make better use of high-level quantum development in Q# by making it easier to iterate over collections of values, such as Qubit[], and to use them to write out complex algorithmic patterns efficiently.

Proposed deprecations and renamings

• namespace Microsoft.Quantum.Arrays
  • function Exclude<'T>(remove : Int[], array : 'T[]) : 'T[]; function Excluding<'T>(remove : Int[], array : 'T[]) : 'T[];
  • function Zip<'T, 'U>(left : 'T[], right : 'U[]) : ('T, 'U)[]; function Zipped<'T, 'U>(left : 'T[], right : 'U[]) : ('T, 'U)[];

Proposed additions

• namespace Microsoft.Quantum.Arrays
  • Accessor functions
  • function ElementAt<'T>(index : Int, array : 'T[]) : 'T;
  • function ElementsAt<'T>(range : Range, array : 'T[]) : 'T[];
  • Reductions and combinators
  • function CumulativeFolded<'State, 'TInput>(fn : ('State, 'TInput -> 'State), initialState : 'State, arr : 'TInput[]) : 'State[];
  • function FlatMapped<'TInput, 'TOutput>(mapper : 'TInput -> 'TOutput[], arr : 'TInput[]) : 'TOutput[]; Returns (mapper(arr[0]) + mapper(arr[1]) + ... + mapper(arr[n - 1])).
  • function MappedOverRange<'T>(fn : Int -> 'T, range : Range) : 'T[]; Returns the value of fn at each element of range.
  • function Flattened<'T>(arr : 'T[][]) : 'T[]; Returns the sum over array concatenation of arr; i.e.: arr[0] + arr[1] + ... + arr[Length(arr) - 1]. See comment by @msoeken below.
  • Multidimensional array functions
  • function ColumnAt<'T>(index : Int, array : 'T[][]) : 'T[];
  • function Diagonal<'T>(array : 'T[][]) : 'T[];
  • function Transposed<'T>(array : 'T[][]) : 'T[][];
  • Facts
  • function RectangularArrayFact<'T>(array : 'T[][], msg : String) : Unit
  • function SquareArrayFact<'T>(array : 'T[][], msg : String)
  • Conversion
  • function HeadAndRest<'T>(arr : 'T[]) : ('T, 'T[]);
  • function MostAndTail<'T>(arr : 'T[]) : ('T[], T);
  • Other functions
  • function Count<'T>(predicate : ('T -> Bool), array : 'T[]) : Int
  • function EmptyArray<'T>() : 'T[]; (see https://github.com/microsoft/qsharp-compiler/issues/589)
  • function Interleaved<'T>(first : 'T[], second : 'T[]) : 'T[]; Given two arrays, returns a new array [first[0], second[0], first[1], second[1], ...]
  • function Prefixes<'T>(arr : 'T[]) : 'T[][]; Given an array, returns a new array of all prefixes; i.e.: [[arr[0]], [arr[0], arr[1]], ... arr].
  • function Windows<'T>(size : Int, arr : 'T[]) : 'T[][]; Returns [[arr[0], arr[1], ..., arr[size - 1]], [arr[1], arr[2], ..., arr[size]], ..., [arr[n - size + 1], arr[n - size + 2], ..., arr[n - 1]]].
  • function Unique<'T>(arr : 'T[]) : 'T[];
  • function Unzipped<'T, 'U>(arr : ('T, 'U)[]) : ('T[], 'U[]);
  • Unzipped3, Unzipped4, etc.
• namespace Microsoft.Quantum.Canon
  • operation ApplyTo{Head, Tail, Most, Rest}{,A,C,CA}

Future considerations and language feature dependencies

• Functions like Transposed or ColumnAt may need to be redesigned to work well with 𝑛-d arrays.

Other comments

• @guenp​​ has suggested that Fold is a reasonable name if there's a way to find it in docs from searching for "reduce." The input name "folder" is dubious, though, regardless; duplicate meaning that can be confused.

[msoeken]

I suggest to add a function Flattened with the following specification:

function Flattened<'T>(arrays : 'T[][]) : 'T[] {
    return Fold(PlusA<'T>, new 'T[0], arrays);
}

This could also be implemented using a special case of FlatMapped:

function Flattened<'T>(arrays : 'T[][]): 'T[] {
  return FlatMapped(PlusA<'T>, arrays);
}

[msoeken]

I suggest to add a function Count with the following specification:

function Count<'T>(value : 'T, array : 'T[]) : Int {
  mutable count = 0;
  for (elem in array) {
    if (elem == value) {
      set count += 1;
    }
  }
  return count;
}

Currently I am implementing such a function using Filtered and type specific functions such as EqualI:

let integerCounts = Length(Filtered(EqualI(value, _), array));

[cgranade]

I suggest to add a function Count with the following specification:

Added to the draft API above, reflecting that not all 'T support equality by taking an explicit predicate.

[msoeken]

Added to the draft API above, reflecting that not all 'T support equality by taking an explicit predicate.

Thanks! That also explains the signature of Filtered, Where, and IndexOf, where I often expect a value instead of a predicate.

[guenp]

Perhaps this is out of scope for this discussion but I disagree with deprecating Zip. It can be a huge blocker to people who are new to Q# (and let's be honest, a large majority of our users are going to be new to Q# in the future :)) and have worked with other languages such as Python and are going to expect to be able to (keep) using Zip.

[msoeken]

I prefer Zipped for the sake of consistency, but agree that we should provide a solution for function names of commonly used functions that differ from the style guide, such as Zip, Fold, or Reduce. I suggest to have a discussion on how to best achieve this (solutions may include aliases, documentation, code hints, replacements in error messages for unknown identifiers, ...).

[cgranade]

Perhaps this is out of scope for this discussion but I disagree with deprecating Zip. It can be a huge blocker to people who are new to Q# (and let's be honest, a large majority of our users are going to be new to Q# in the future :)) and have worked with other languages such as Python and are going to expect to be able to (keep) using Zip.

While I totally agree with reducing confusion, I think it's important to keep in mind that Q# is its own language with its own design, geared towards making it easier to write quantum programs. For example, in order to support automatic adjointability and controllability, Q# has a strong separation between subroutines which are purely deterministic and cannot have side-effects (functions), and those that can have arbitrary side effects (operations). Operations cannot be used in all the same places that functions can, such that using names that reflect that feature helps make it easier understand the implications of functions-vs-operations.

From that perspective, I think it makes sense to identify some of the features that we can develop or expand upon to help users out as they learn Q#. As per your comments, @guenp and @msoeken, collecting some of the initial ideas:

• IntelliSense is already helpful for Q# standalone, Q# + Python, and Q# + .NET workflows in VS Code and VS (esp with %project now in IQ#). We can expand that to include Q# standalone and Q# + Python in Jupyter Notebook by supporting the autocomplete message in IQ#.
• Error messages for missing identifiers could offer hints when similarly named callables exist. E.g.: Unknown identifier Foo; did you mean FooBar?
• Code actions in VS and VS Code to fix common mistakes (can possibly add more to telemetry to help design here).
• Making deprecation stubs (possibly using a different attribute than @Deprecated) permanent to downgrade common mistakes from errors to warnings and to give actionable guidance.

The above notwithstanding, I'm wary of providing two distinct and equally valid functions for doing the same thing, though. That opens up a few more problems:

• Increases maintenance cost, as both equivalent functions need to be maintained and documented at the same level of quality.
• Users trying to read Q# need to learn both equivalent functions in order to read code written by other Q# users.
• Makes it harder to learn conventions, impacting discoverability for other parts of Q# libraries unless both function naming styles are adopted throughout entire libraries.

(On a not entirely serious side note, I think that's a large part of why Python's import this contains the following timeless wisdom: "There should be one-- and preferably only one --obvious way to do it. Although that way may not be obvious at first unless you're Dutch.")

In any case, given the above, my suggested action items are thus as follows:

• Keep the Zip → Zipped renaming as part of general API design consistency improvements.
• Improve telemetry to get a better understanding of the impact of unknown identifier errors, including how unknown identifier errors rates differ across editing environments (+@vxfield for discussion here).
• Make feature requests to qsharp-compiler and iqsharp for improved error messages, code actions, and IQ# autocomplete, so as to help users make the best use of Q# libraries.
• Consider making deprecation stubs for Zip, etc. permeant, making feature request to qsharp-compiler for a new attribute (e.g.: @Alias) supported by warnings and code actions.

[msoeken]

In any case, given the above, my suggested action items are thus as follows: ...

I second this suggestion.