Use case: pattern matching

[masaeedu]

This issue describes some code that is simple to implement in JS but difficult to type accurately in TypeScript. I'm going to try to relate it to open issues and proposals to illustrate how they could improve the situation.

---

Use case

I have a simple discriminator-based pattern matching function in JS:

// Takes a discriminator projection, a set of cases, and an object, and produces the value
// obtained by applying the case matching the discriminator value
const match =  (p, ...c) => {
  const cases = new Map(c)
  return x => cases.get(p(x))(x)
}

Some contrived usage:

const validate = match(
  x => x.foo.bar > 5,

  [false, x => "number must be more than five!"],
  [true,  x => "ok"                            ])

const x = { foo: { bar: 4 } }
console.log(validate(x))
// => "number must be more than five!"

const max = match(
  a => !a.length ? "0" : a.length === 1 ? "1" : "n",

  ["0", ()          => fail("No max of empty list")               ],
  ["1", ([x])       => x                                          ],
  ["n", ([x, ...y]) => { const m = max(y); return x > m ? x : m; }])

console.log(max([1, 2, 4, 500, 8]))
// => 500

Now I want to add some type annotations to help me use it. Importantly, I don't want new syntax or runtime features: I just want good type checking and inference on top of something that can already be done in 4 lines of JS.

I want to ensure the following:

• The case handlers supplied should be checked for exhaustiveness over the discriminant cases.

• Type inference should ensure each case handler sees a narrowed type appropriate to it.

  If I am using x => x.foo to match on { foo: "a", bar: 42 } | { foo: "b", baz: 42 }, only the "a" case should be able to see the bar property and only the "b" case should be able to see the baz property.

Unfortunately, I've been having a very difficult time expressing this in TypeScript.

Implementation

The best I've been able to do is the following:

type Match = <P extends string, X extends {[p in P]}, R>(
    x: X,
    p: P,
    f: {[_ in X[P]]: (data: X & {[p in P]: _}) => R })
    => R
declare const match: Match

declare const x: { foo: "a", bar: 42 } | { foo: "b", baz: 42 }
match(x, "foo", {
    a: x => x.bar,
    b: x => x.baz
})

This is frustratingly close to being something that works, but there's various problems.

Inference is sensitive to currying/argument ordering

Currying and the appropriate argument ordering needed to be discarded right off the bat, if we want the user to have good inference of the type parameters from the arguments. This rearrangement is not free: we are changing the performance and runtime characteristics of our code to appease a type checker.

See #16914.

Mapped types cannot be used with unions of non-string literals

We need to map a union of possible discriminant values (in this case "a" | "b") to a tuple of "case handlers". Mapped types in TypeScript, however, can only map to properties of an object, and consequently can only be used to map from a union of strings. This precludes pattern matching over false | true or "potato" | 42, and cases must now be supplied as a hash instead of spread arguments.

This is not fatal, since any union of non-string literals can be encoded as a union of string literals (e.g. by just adding "s around the literals in question), but it is annoying. It would be nice to be able to project a union type to an exhaustive tuple type containing some transformation from every member of the union.

No reduction of absurd types

The trick of doing X & {[p in P]: _} doesn't work. x in a: x => x.bar is inferred as ({ foo: "a"; bar: 42; } & { foo: "a"; }) | ({ foo: "b"; baz: 42; } & { foo: "a"; }). So far so good. Unfortunately we get a type error at x.bar, saying: Property 'bar' does not exist on type ....

However, the property bar does exist on all possible values of typeof x! The second member of the union, ({ foo: "b"; baz: 42; } & { foo: "a"; }) is impossible; there can be no value for x where the foo property is simultaneously "a" and "b". Hence this type, through straightforward reduction (see discussion in #18339), is equivalent to never, and T | never is simply T, for any T.

This means the actual type of x here is { foo: "a"; bar: 42; }, which does have a bar property, so the error is not warranted.

Can't use arbitrary function as discriminator anymore

I'm now stuck using a static string prop as my discriminator projection. That is, I can't use x => x.foo.bar, or ([x, ...y]) => ... to demarcate cases, as I did in the examples at the beginning.

At first glance it seems like this can't actually be improved in any way. When the projection is a static property string, it is easy to express constraints that narrow the arguments for the case handlers (X & {[p in P]: _}). How can we do this when the projection is an arbitrary function? In other words, given only the projection function's type P, how can you extract an appropriately narrowed version of X for each of the function's possible return types?

Beware: Much handwaving and pseudocode follows.

It requires a lot of work, and a large number of features we don't have today, but it might be possible to do this. All the information necessary for inferring the right types is available in the terms.

First, focusing on the projection expression:

const p =(a: {}[]) => !a.length ? "0" : a.length === 1 ? "1" : "n"

Today, the type of p is inferred as:

type P = (a: {}[]) => "0" | "1" | "n"

In fact, there is more information is available to the typechecker via the control flow graph it superimposes on every function. For more on inferring overloads from branched function expressions, see #17747. Using this information, it should be possible to instead infer, at least in a conceptual sense, a type of:

type Falsy = false | null | undefined | 0 | ... 
type Truthy = {} - Falsy
type P = 
  ((a: []) => "0") &
  ((a: [{}]) => "1") &
  ((a: {}[] & { length: (Truthy - 1) }) => "n")

(using subtraction type operator from #12215). I assume that:

• Control flow analysis intersects the type of each discriminated term with Falsy in negative branches
• The type system reduces { length: Falsy } & { length: number } to { length: 0 } (by removing absurd intersections from Falsy & number)
• { length: <numeric literal> } & T[] is equivalent to a T tuple of the appropriate length (see Compiler does not narrow tuples based on length property #19543)

Granted that p is now ascribed the overloaded function type P from above, how does that help us? Squinting at P, I can recognize that the argument types in P's overloads exactly match the desired argument types for the case handlers.

As mentioned in #17747, overloaded function signatures and function signatures that accept an argument of a union type are actually equivalent. Given the overloaded function signature P, we want to map over the type of its argument, which is the union [] | [{}] | ({}[] & ...), and produce a tuple type to represent the cases we expect to be passed. In pseudo-TypeScript:

type Cases<R> = [[return(P, A), (x: A) => R] for A in arg(P, 0)]

Where:

• arg denotes a type operator for retrieving a positional argument type
• return denotes a type operator for retrieving the return type of a function (for a particular set of type arguments)
• the [...X... for X in Y] syntax represents a tuple containing one projected type for every union member in Y

Finally, our match function's type can be expressed as:

type Cases<P, R> = [[return(P, A), (x: A) => R] for A in arg(P, 0)]
type Match = <X, P extends (x: X) => R, R>(
    x: X,
    p: P,
    f: Cases<P, R>) => R
declare const match: Match

This ultimately gets us:

const result = match(
  [1, 2 ,3],
  a => !a.length ? "0" : a.length === 1 ? "1" : "n",
  [
    ["0", ()          => fail("No max of empty list")               ],
    ["1", ([x])       => x                                          ],
    ["n", ([x, ...y]) => { const m = max(y); return x > m ? x : m; }]
  ])

// X === number[]
// P === ((a: []) => "0") & ((a: [number]) => "1") & ((a: number[] & { length: (Truthy - 1) }) => "n")
// R === never | number
// typeof result === R

This is pretty good, if not perfect. It would be nice if we were able to return to the curried signature and be a little more specific, so that we could have:

const max = ...
// typeof max === ((a: []) => never) & ((a: number[]) => number)

I'm out of time and energy though, and am going to quit here.

What's the takeaway?

• TypeScript has a lot of powerful features, but in certain cases features don't interact well, or there are holes that need to plugged before things can work together
• JS by itself is quite powerful, and is capable of imitating many useful idioms from other languages
• The type system would be better able to keep up in niche scenarios by ensuring features have some underlying semantics that composes sensibly
• We are at a threshold where it is almost possible to write certain kinds of highly expressive code safely

[mhegazy]

Previously proposed in #16067. Related to #12424

[typescript-bot]

Automatically closing this issue for housekeeping purposes. The issue labels indicate that it is unactionable at the moment or has already been addressed.