What does "homomorphic mapped type" mean?

Question

I've seen the term "homomorphic mapped type" in a few TypeScript PRs. Here's an example: https://github.com/microsoft/TypeScript/pull/21919

In --strictNullChecks mode, when a homomorphic mapped type removes a ? modifier from a property in the underlying type it also removes undefined from the type of that property

What is a homomorphic mapped type? What exactly is the homomorphism? Is there a good example of a non-homomorphic mapped type

The reason for my confusion is that a homomorphism is map between two structures that preserves a particular operation. What is the operation in question here? That is, where f is the mapping, what is op in the following equation:

f(x op y) = f(x) op f(y)

What I tried

I tried going on the assumption that op is &, the operation that intersects two types.

A homomorphic mapping would then be one such that:

F<T & U> = F<T> & F<U>

An example of a homomorphic mapping (from the TS handbook) is:

type Partial<T> = { [P in keyof T]?: T[P] }

because Partial<T & U> is always the same as Partial<T> & Partial<U>.

The problem is that I can't come up with any way to make a mapped type non-homomorphic!

Even silly ones like this seem homomorphic:

type Silly<T> = { [P in "foo"]: number}

What's confusing for me is that Silly seems to be a homomorphism (Silly <T & U> = Silly<T> & Silly<U>).

This seems to contradict what the handbook says a homomorphic mapped type:

...homomorphic, which means that the mapping applies only to properties of T and no others. The compiler knows that it can copy all the existing property modifiers before adding any new ones

Silly preserves & but is not a homomorphic mapped type by the definition in the handbook.

Answer 1

In TypeScript, a homomorphic mapped type is specifically a type in which the compiler recognizes that you are mapping the properties of an existing object type. In such cases, the output object type will have the same readonly and/or optional (?) property modifiers on its properties as the ones on the input type do. There are a few ways I know of to make a mapped type homomorphic, and some other ways to make it... not.

In what follows, let's use this type as something to map over:

type Foo = {
    norm: string,
    opt?: string,
    readonly ro: string,
    readonly both?: string
};

---

Main homomorphic mapped type technique, in keyof:

type Hom1<T> = { [P in keyof T]: number };
type Hom2<T, U> = { [K in keyof (T & U)]: K extends keyof T ? "L" : "R" };
type Hom3 = { [Q in keyof { readonly a: string, b?: number }]: Q };

In the above, you are explicitly iterating over keyof something. Let's see what you get when we use them on our Foo type:

type Hom1Foo = Hom1<Foo>;
/* type Hom1Foo = {
    norm: number;
    opt?: number | undefined;
    readonly ro: number;
    readonly both?: number | undefined;
}*/

type Hom2FooDate = Hom2<Foo, { z: boolean }>
/*type Hom2FooDate = {
    norm: "L";
    opt?: "L" | undefined;
    readonly ro: "L";
    readonly both?: "L" | undefined;
    z: "R";
} */

type Hom3Itself = Hom3
/* type Hom3Itself = {
    readonly a: "a";
    b?: "b" | undefined;
} */

You can see that in all the outputs, the read-only and optionality markers were copied over from the inputs. This is the main technique for producing homomorphic mapped types and by far the most common.

---

Secondary homomorphic mapped type technique, in K where Kextendskeyof T is a generic type parameter and T is a generic type parameter:

// <K extends keyof T, T> ... {[P in K]: ...}
type Hom4<T, K extends keyof T> = { [P in K]: 1 };

This specifically gives us the ability to copy property modifiers from just some of the keys of an object, and was implemented here, primarily to make the Pick<T, K> utility type homomorphic. Let's see how Hom4 behaves with Foo:

type Hom4AllKeys = Hom4<Foo, keyof Foo>;
/* type Hom4AllKeys = {
    norm: 1;
    opt?: 1 | undefined;
    readonly ro: 1;
    readonly both?: 1 | undefined;
}*/

type Hom4SomeKeys = Hom4<Foo, "opt" | "ro">;
/* type Hom4SomeKeys = {
    opt?: 1 | undefined;
    readonly ro: 1;
}*/

---

Now just about any other use of mapped types gives a non-homomorphic type. This is not really an issue if you don't see yourself as mapping over the keys of a different object type. For example:

type NonHom0 = { [P in "a" | "b" | "c"]: 0 };
/* type NonHom0 = {
    a: 0;
    b: 0;
    c: 0;
}*/

The properties of NonHom0 are neither optional nor read-only; why would they be? There's no other type with keys a, b, and c to copy them from. Things get a little trickier if you start imagining that you're copying a property from some other object type, but the compiler doesn't see it that way:

type NonHom1 = { [P in "norm" | "opt" | "ro" | "both"]: Foo[P] };
/* type NonHom = {
    norm: string;
    opt: string | undefined;
    ro: string;
    both: string | undefined;
}*/

type KeysOfFoo = keyof Foo
type NonHom2 = { [K in KeysOfFoo]: 1 }
/* type NonHom2 = {
    norm: 1;
    opt: 1;
    ro: 1;
    both: 1;
} */

type NonHom3 = { [Q in Extract<keyof Foo, string>]: Foo[Q] };
/* type NonHom3 = {
    norm: string;
    opt: string | undefined;
    ro: string;
    both: string | undefined;
}*/

In those cases the mapping is non-homomorphic; the output types have neither read-only nor optional properties. (the | undefined is still present on properties that used to be optional, but the properties themselves are not optional). It's true that you're still iterating over the keys of Foo, but the compiler no longer sees a relationship with Foo. In NonHom1, the keys just happen to be the same, but there's no keyof, so the compiler doesn't recognize the mapping as homomorphic. In NonHom2, you're using keyof, but the compiler eagerly evaluates KeysOfFoo so that by the time you get to NonHom2, it's the same mapping as in NonHom1. In NonHom3, you're iterating over just the string keys of Foo (which is all of them), but again, the compiler loses the thread and no longer recognizes in Extract<keyof Foo, string> as a trigger for homomorphic mapping. There are workarounds, see microsoft/TypeScript#24679, but the point here is that if you stray from in keyof or in K-where-K extends keyof T-and-both-K-and-T-are-generic, you will get the non-homomorphic map.

---

Whew, I'm done. I don't want to write the word "homomorphic" for a few days after this. Anyway, hope that helps; good luck!

Playground link to code