Pattern matching and match expressions

[cgranade]

Suggestion

This suggestion proposes to add patterns to Q#, and to allow patterns to be used in deconstructing and matching values.

Considerations

The Q# language does not currently have a way of denoting that an action should be taken or a value should be computed from a list of closely related conditional expressions, similar to the switch of case statements common to many imperative languages. In absentia such a feature, operations that make use of techniques such as lookup tables can become unwieldy, such as seen in https://github.com/microsoft/QuantumLibraries/issues/409.

To resolve this in a way that also builds a path towards adopting more functional-inspired features in the future, this suggestion would introduce match expressions that allow breaking down the various cases of a given value by deconstructing that value into patterns. Where side effects are necessary and/or desirable, such that an expression form is not appropriate, this suggestion would also introduce a new if let statement (similar to existing constructs in Rust and C#) that allows conditioning the execution of a block of statements on whether or not a given value matches a pattern.

The design of this suggestion is intended to present patterns as a generalization of existing Q# concepts, such as deconstructing assignments, and to allow for the future growth of Q# in a consistent and coherent fashion.

Context

This suggestion generalizes the existing deconstruction feature, allowing for deconstructing more complicated patterns. In addition, this change would make it easier to develop additional Q# language features such as discriminated unions (see https://github.com/microsoft/qsharp-language/issues/51).

Related features in other languages:

• C# patterns
• F# patterns
• Python patterns
• Rust patterns

Related Q# proposals and suggestions:

• discriminated unions
• type-parameterized UDTs (in draft)

Kinds of patterns

We say that a pattern pattern is irrefutable for a type 'T if all possible values of type 'T match pattern. A pattern that is not irrefutable is refutable. A list of patterns pattern1, pattern2, ... is exhaustive for a value of type 'T if pattern1 | pattern2 | ... is irrefutable for 'T.

Kinds of patterns and pattern operators that may be worth considering:

• Wildcard pattern (_), matches any value.
• Named pattern (pattern as name), matches pattern, but captures the value as a new immutable binding. As a shorthand, name on its own acts as _ as name; this can always be disambiguated, since arbitrary expressions cannot be used as patterns.
• Tuple pattern ((pattern1, pattern2, ...)), matches values of a given arity, where each part of a value matches the corresponding pattern.
• Alternatives (pattern1 | pattern2 | ...), matches any value that matches pattern1, pattern2, or so forth.
• Literal pattern (e.g.: (), 100L, 42, 3.14, PauliX, Zero, or "foo"): matches only the exact value of the given literal.
• Named item pattern (e.g.: (Real -> pattern, Imag -> _)): matches named items of a UDT.
• UDT pattern (Complex(0.0, _)): similar to the tuple pattern, but matches on the unwrapped value of a UDT constructor. Possibly redundant with named item patterns, but is less explicit.
• Empty array pattern ([]): matches only the empty array of a given type.
• Array-by-subscript pattern (e.g.: [0 -> pattern1, 1... -> pattern2]): matches when an index or range is valid, and when subscripting the value by the given index or range matches the pattern on the right of ->.
• Array deconstructor pattern (e.g.: [pattern1, pattern2]): matches an array of the exact given length when each pattern is individually matched.
• Guarded pattern (e.g: _ as foo when foo > 40): matches only when a Boolean condition is met.

Note that this list explicitly excludes anything that would cause reification of type information at runtime. For example, a type pattern cannot be used to refine an unconstrained generic:

function Bad<'T>(input : 'T) : String {
    if let q : Qubit = input { // 💣, would refine 'T based on type information only available at runtime.
        return "Was a qubit!";
    } else {
        return "Was not a qubit!";
    }
}

This suggestion also excludes any consideration of F#-style active patterns,

Using patterns

This suggestion would extend Q# to allow using patterns in three distinct contexts:

• Deconstructing irrefutable patterns (let, for, use, or borrow statements).
• Conditionally deconstructing refutable patterns (if let, similar to Rust's if let statement and C#'s if (... is pattern) statement).
• Deconstructing values into one of an exhaustive list of patterns (match expression, similar to F#'s and Rust's match, and to C#'s switch expressions).

Examples

Example 1: Do something for each different Pauli operator.

operation ApplyP(pauli : Pauli, target : Qubit) : Unit is Adj + Ctl {
    let op = match pauli {
        PauliI -> I,
        PauliX -> X,
        PauliY -> Y,
        PauliZ -> Z
    };
    op(target);
}

Example 2: Define multiplication between Klein group elements (similar to group product and inverse definitions in https://github.com/microsoft/QuantumLibraries/issues/409).

newtype K4 = (Bool, Bool);
function TimesK4(left : K4, right : K4) : K4 {
    return match (left, right) {
        // Match identity elements.
        (K4(false, false), _) -> right,
        (_, K4(false, false)) -> left,
        // All elements square to themselves.
        _ when left == right -> K4(false, false),
        // Remaining 6 elements:
        (K4(false, true), K4(true, false)) -> K4(true, true),
        (K4(false, true), K4(true, true)) -> K4(true, false),
        (K4(true, false), K4(false, true)) -> K4(true, true),
        (K4(true, false), K4(true, true)) -> K4(false, true),
        (K4(true, true), K4(false, true)) -> K4(true, false),
        (K4(true, true), K4(true, false)) -> K4(false, true)
    };
}

Example 3: Apply different decompositions based on the number of controls.

// Adapted from:
// https://github.com/microsoft/qsharp-runtime/blob/974a385cc57c2b663e8134c1f3170f9cb8ae5fb1/src/Simulation/TargetDefinitions/Decompositions/XFromSinglyControlled.qs#L23
operation X(qubit : Qubit) : Unit is Adj + Ctl {
    body (...) {
        Controlled X([], qubit);
    }

    controlled (controls, ...) {
        match controls {
            [] -> ApplyUncontrolledX(qubit),
            [control] -> ApplyControlledX(control, qubit),
            [control0, control1] -> CCNOT(control0, control1, qubit),
            _ -> ApplyWithLessControlsA(Controlled X, (controls, qubit))
        }
    }
}

// Adapted from:
// https://github.com/microsoft/qsharp-runtime/blob/974a385cc57c2b663e8134c1f3170f9cb8ae5fb1/src/Simulation/TargetDefinitions/Decompositions/Measure.qs#L43-L69
operation Measure(bases : Pauli[], qubits : Qubit[]) : Result {
    if (Length(bases) != Length(qubits)) { fail "Arrays 'bases' and 'qubits' must be of the same length."; }
    if let ([basis], [qubit]) = (bases, qubits) {
        within {
            MapPauli(qubit, PauliZ, basis);
        } apply {
            let res = M(qubit);
            PreparePostM(res, qubit);
            return res;
        }
    } else {
        use q = Qubit();
        within {
            H(q);
        } apply {
            for (basis, qubit) in Zipped(bases, qubits) {
                Controlled (match basis {
                    PauliX -> X,
                    PauliY -> Y,
                    PauliZ -> Z,
                    _ -> I
                })(basis, qubit);
            }
        }
        let res =  M(q);
        Reset(q);
        return res;
    }
}

Examples using other proposed and suggested Q# enhancements

Example 4: Using patterns with type-parameterized UDT and discriminated union features.

// As described at https://github.com/microsoft/qsharp-language/issues/51,
// we can use type-parameterized UDTs and discriminated unions together to
// define a "maybe" DU that represents the possibility that a value may not
// exist.
newtype Maybe<'T> =
    | Some('T)
    | None();
// This DU is similar to the Option DU from Rust and F#, the Maybe DU from
// Haskell, the Optional DU from Swift, the Nullable struct from C#, the
// Optional type hint from Python, and so forth.

// Once defined, we can then use Maybe<'T> to represent in a type-safe manner
// the idea that a function may or may not return a value:

/// # Summary
/// Returns a big integer represented as a 64-bit integer if it is within
/// the range of valid values for 64-bit integers, and `None` otherwise.
function MaybeBigIntAsInt(value : BigInt) : Maybe<Int> { ... }

// This suggestion would extend the feature suggested in
// https://github.com/microsoft/qsharp-language/issues/51
// by allowing deconstructing discriminated unions into their case constructors.
// Since case deconstructors would then be refutable patterns, we could use
// the `if let` suggestion above to both check whether a pattern matches,
// and to capture the expression matched by the pattern.

if let Some(smallInt) = MaybeBigIntAsInt(value) {
    // In this block, we are guaranteed that MaybeBigIntAsInt returned
    // a concrete value, and have bound that value to the immutable variable
    // `smallInt`.
} else {
    // In this block, the output of `MaybeBigIntAsInt(value)` did not match
    // the refutable pattern `Some(smallInt)` such that the `if let` condition
    // fails. Thus, we know that the BigInt → Int conversion failed, and can
    // proceed to handle that failure accordingly without needing exceptional
    // control flow.
}

Example 5: Deconstructing anonymous DUs (copied from https://github.com/microsoft/qsharp-language/issues/51).

// As described at https://github.com/microsoft/qsharp-language/issues/51,
// we could consider anonymous DUs by using the case constructor delimiter `|`
// to combine various types together.
// This does not represent runtime reification of type information, however,
// as such anonymous DUs can always be converted to explicit and named DUs.
// That is, this suggestion from https://github.com/microsoft/qsharp-language/issues/51
// is effectively an example of syntactic sugar.

operation PrepareArbitraryState(coefficients : (Double[] | Complex[] | ComplexPolar[]), target : Qubit[]) : Unit is Adj + Ctl {
    let complexCoefficients = coefficients match {
        Double[](realCoefficients) ->
             // In this arm, realCoefficients is a resolution of the anonymous DU
             // to have the concrete type Double[] instead.
             Mapped(Complex(_, 0.0), realCoefficients),
         Complex[](alreadyComplexCoefficients) -> alreadyComplexCoefficients,
         ComplexPolar[](complexPolarCoefficients) ->
             Mapped(ComplexPolarAsComplex, complexPolarCoefficients)
          // The match expression is exhaustive here, such that no blank pattern
          // is needed in order to guarantee that complexCoefficients has
          // a value of type Complex[] in all cases.
    };

    // Use complexCoefficients in the rest of the implementation...
}

Note that this does not represent reifying arbitrary runtime type information as excluded above. Rather, the type (Double[] | Complex[] | ComplexPolar[]) represents an anonymous DU with case constructors Double[], Complex[], and ComplexPolar[], such that all possible cases are known exactly at compile time.

Affidavit (please fill out)

Please add ticks by placing a cross in the box:

• [x] I have searched both open and closed suggestions and proposals on this site and believe this is not a duplicate.
• [x] I believe that the spirit of this suggestion is aligned with the design principles and general vision for Q#.

Please tick all that apply:

• [x] This is not a breaking change to the Q# language design
• [x] I or my organization would be willing to help implement and/or test this

[kuzminrobin]

• I assume that with "matches the pattern on the right of <-" you meant "matches the pattern on the right of ->".
• In a fragment function Bad<'T>(in : 'T) : String I see that in { after ( } is highlighted the same way as the keywords. This makes me suspect that either you really meant a keyword in there, or the variable named in can conflict with a keyword. Any comments about that would help.
• FYI: https://github.com/microsoft/QuantumLibraries/416 not found (error 404). Two occurrences.
• FYI: I feel that listings in "Example 3" section are longer than enough to illustrate the concept.
• (Maybe I'm not familiar with evident Q# concepts, I apologize if that's the case) FYI: I feel that in "Example 4" the concepts of Maybe<Int>, Some(..), and None are not defined. I know those were mentioned in Discriminated Unions (that you refer to), but Discriminated Unions is just a related proposal, not a proposal yours is based on. So I'm not sure if you mean the same as that proposal or not. And even after having read that proposal I feel that Some(..) and None are still not defined (are black boxes for me).
• FYI: I suspect that in Example 5 with fragment Mapped(Complex(_, 0.0), positiveCoefficients) you meant Mapped(Complex(_, 0.0), realCoefficients). Otherwise I feel that positiveCoefficients is undefined.

[cgranade]

• I assume that with "matches the pattern on the right of <-" you meant "matches the pattern on the right of ->".

Thanks for catching, fixed that typo.

• In a fragment function Bad<'T>(in : 'T) : String I see that in { after ( } is highlighted the same way as the keywords. This makes me suspect that either you really meant a keyword in there, or the variable named in can conflict with a keyword. Any comments about that would help.

The in identifier is reserved in Q# when using C# code generation; clarified by changing to input.

• FYI: https://github.com/microsoft/QuantumLibraries/416 not found (error 404). Two occurrences.

Fixed.

• FYI: I feel that listings in "Example 3" section are longer than enough to illustrate the concept.

I feel that the value of choosing real-world examples from the actual decompositions used in our targeting packages is worth having a bit of a longer example. These translations are a bit messy at the moment due to the lack of some kind of switch or match, such that they make great usecases for a feature of this form.

• (Maybe I'm not familiar with evident Q# concepts, I apologize if that's the case) FYI: I feel that in "Example 4" the concepts of Maybe<Int>, Some(..), and None are not defined. I know those were mentioned in Discriminated Unions (that you refer to), but Discriminated Unions is just a related proposal, not a proposal yours is based on. So I'm not sure if you mean the same as that proposal or not. And even after having read that proposal I feel that Some(..) and None are still not defined (are black boxes for me).

As per the qsharp-language process, new language features start off as suggestions (represented by GitHub Issues), then proceed to be expanded into full proposals (represented by GitHub Pull Requests). Moreover, Example 4 is explicitly under a section that discusses how this suggestion would work with other suggestions and proposals — that section of the suggestion templated is intended to demonstrate how different suggestions work together, such that Examples 4 and 5 aren't truly standalone in that sense.

In any case, I've edited to clarify a little bit, and to point to the definition from https://github.com/microsoft/qsharp-language/issues/51 of Maybe<'T> as newtype Maybe<'T> = Some('T) | None(). As described at #51, Some<'T>(item0 : 'T) : Maybe<'T> and None<'T>() : Maybe<'T> are the two case constructors for the Maybe<'T> discriminated union, similar to the Option<T> DU in Rust, the Option<'a> DU in F#, the Option[T] type hint in Python, the Maybe T DU in Haskell, and the Nullable<T> struct in C#.

• FYI: I suspect that in Example 5 with fragment Mapped(Complex(_, 0.0), positiveCoefficients) you meant Mapped(Complex(_, 0.0), realCoefficients). Otherwise I feel that positiveCoefficients is undefined.

Thanks for catching; I had modified the name for clarity at one point and missed a spot when doing so.

[bettinaheim]

@kuzminrobin @cgranade Thank you both for already starting a more detailed discussion here. The general idea is that the bar for submitting a suggestion should be relatively low, and in that sense I do explicitly not want that these suggestions get too long or too detailed. It is good to point out what requires further clarification in a potential proposal, but these things should not be added to the suggestion itself. We will give feedback on whether or not we think this is something that is worth fleshing out further based on a more or less minimal description. This particular suggest is already a bit long for my taste. :)

[cgranade]

This particular suggest is already a bit long for my taste. :)

I'll take the responsibility for that one... I got a bit excited thinking about the different ways to use matching and may have gotten a bit carried away. Sorry about that...!