Recursive Generic Types

Recursive generic types

Try:

class StringToDictionary : Dictionary<string, StringToDictionary> { }

Then you can write:

var stuff = new StringToDictionary
        {
            { "Fruit", new StringToDictionary
                {
                    { "Apple", null },
                    { "Banana", null },
                    { "Lemon", new StringToDictionary { { "Sharp", null } } }
                }
            },
        };

General principle for recursion: find some way to give a name to the recursive pattern, so it can refer to itself by name.

What does Recursive type bound in Generics mean?

What is recursive type bound

This: <T extends Comparable<T>>

Note that the type parameter T is also part of the signature of the super interface Comparable<T>.

and how does the above piece of code help achieve mutual comparability?

It ensures that you can only compare objects of type T. Without the type bound, Comparable compares any two Objects. With the type bound, the compiler can ensure that only two objects of type T are compared.

Understanding java recursive generic type definitions with type erasion

So ClassName has a generic parameter T and this parameter needs to fit a certain requirement, in this case extends a certain type S, that means, T must inherit S. Now the interesting thing in this case is this S.

We have S to be ClassName<?>, so T must inherit from ClassName with a wildcard. For the wildcard aka the question mark please have a look at the link Michael Markidis gave in a comment to your question.

The real fun now is that this definition

public abstract class ClassName<T extends ClassName<?>>

allows recursive generic type defintion. So you could have something like

ClassName<ClassName<ClassName<ClassName<?>>>> test;

for whatever that's worth :)

EDIT: Given

ClassName2<T extends ClassName<?>> extends ClassName<T>

thats relatively easy in comparison. We want to inherit ClassName but not "destroy" the generic argument, so we take one ClassName would accept, in this case T extends ClassName<?>. In extends ClassName<T> the compiler checks if this (i.e. ClassName2's) T fits the T of ClassName, which was the requirement (remember ClassName's definition) T extends ClassName<?>, so this obviously works.

In addition, we have ClassName2<?> extending ClassName<?>, so now you can mix the two types however you want:

ClassName2<ClassName<ClassName<ClassName<?>>>> test2;
ClassName2<ClassName<ClassName2<ClassName<?>>>> test3;

However, if you would have, say

class ClassName3<T extends ClassName3<?>> extends ClassName<T>

(the public and abstrac modifiers don't really influence the generic behavior here), you can only have things like

ClassName3<ClassName3<ClassName3<ClassName3<?>>>> test4;
ClassName2<ClassName<ClassName3<ClassName3<?>>>> test5;

since ClassName and ClassName2don't inherit ClassName3.

Recursive generic type parameter in C#

It's known as a "Curiously recurring template pattern" . C# examples here and here. Often used for fluent syntax of interface types in order to keep the generic type "known" to the base implementation.

Is it possible to infer generic types recursively in TypeScript?

(Partial answer)

TypeScript doesn't like recursive types. You can mostly work around this, so long as you don't require inference... however, since that's required here, I don't think it is possible to get TS to take the last step.

You can have one of the following features:

1. Infer the return type to be a tuple with the correct return types.
2. Deeply typecheck the passed array

The first is easy. We just need T in createElements to extend a discriminated union. You had this already, but this is a slightly different way of looking at it.

type DiscriminatedElements = {
    // you can, of course, do better than unknown here.
    [K in keyof HTMLElementTagNameMap]: readonly [K, Partial<HTMLElementTagNameMap[K]> | null, unknown]
}[keyof HTMLElementTagNameMap]

type ToElementTypes<T extends readonly DiscriminatedElements[]> = {
    [K in keyof T]: T[K] extends [keyof HTMLElementTagNameMap, any, any] ? HTMLElementTagNameMap[T[K][0]] : never
}

declare const createElements: <T extends readonly DiscriminatedElements[] | []>(
    array: T
) => ToElementTypes<T>

createElements([
    ['span', {}, null]
]) // [HTMLSpanElement]

The second is a bit trickier. As I said before, TS doesn't like recursive types. See GH#26980. That said, we can work around it to create a type of an arbitrary depth for checking... but if we try to combine this type with any inference, TS will realize it is potentially infinite.

type DiscriminatedElements = {
    [K in keyof HTMLElementTagNameMap]: readonly [K, Partial<HTMLElementTagNameMap[K]> | null]
}[keyof HTMLElementTagNameMap]

type NumberLine = [never, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
type CreateElementArray<T extends readonly [any, any], N extends number> = T extends readonly [infer A, infer B] ? {
    done: readonly [A, B, null],
    recurse: readonly [A, B, null | readonly CreateElementArray<DiscriminatedElements, NumberLine[N]>[]]
}[N extends 0 ? 'done' : 'recurse'] : never

// Increase up N and NumberLine as required
type ElementItem = CreateElementArray<DiscriminatedElements, 4>

declare const createElements: (
    array: readonly ElementItem[]
) => HTMLElement[];

const [divEl, spanEl] = createElements([
    ['div', { id: 'test' }, [
        ['a', { href: 'test' }, [
            ['img', { src: 'test' }, null]
        ]],
        ['img', { href: 'test' }, null] // error, as expected
    ]],
    ['span', null, null]
]);

I don't think variadic tuples help you here. They will be an awesome addition to the language, but don't solve the problem that you are trying to model here.

A solution that would let you keep the best of both worlds would be to accept HTML elements as the third item in the tuple, and simply call createElements within that array.

Recursive Generics in TypeScript

The compiler gives up before it can realize that the type you are specifying is recursive in a supported way, because it does not probe the definition of the Record utility type before checking for circularity. This is a design limitation of TypeScript. See microsoft/TypeScript#41164 for an explanation.

The fix here is to replace Record<string, XYZ> with what it eventually becomes, a type with a string index signature like { [k: string]: XYZ }:

type MyObject = 
  { [k: string]: string | string[] | number | boolean | MyObject } // okay

which works without error.

Playground link to code

how generic type with a recursive type parameter along with the abstract self method allows method chaining to work properly?

Imagine a class:

class Foo<T extends Foo<T>> {
  T foo() { ... }
}

What this is saying is that the foo() method, in the Foo<T> class, will return an instance of something that's also a Foo<T>, because all possible types represented by T are subclasses of Foo<T>.

So it can return itself - which is why it's useful for method chaining with builders; but there's actually nothing that stops it returning some other class within the bound.

If you were to declare it as:

class Foo<T extends Foo> {
  T foo() { ... }
}

then this makes T a raw-typed Foo: foo() returns a Foo, not a Foo<T>. Because raw types erase all generics, this means that in a call chain like foo().foo(), you are losing type information after the first call.

In many situations, this may not feel super-important. But raw types should be avoided in pretty much all situations. The consequences of a raw type here would be:

1. If you weren't returning the self type (alluded to above with the "there's actually nothing that stops it returning some other class"), you would lose that "other class" after the first method call.
2. If you had other generic methods in Foo, e.g. List<String> myList() { ... }, the raw-typed Foo would return raw List, not List<String> (raw types erase all generics, not just the ones related to the omitted type variables).

These clearly don't apply in all situations; but since it is simply bad practice to introduce unnecessary raw types, make sure you don't introduce them.

---

Related Topics