allow recursive generic type aliases

interface A<a> {
    brand: 'a';
    nested: a;
}

interface B<a> {
    brand: 'b';
    nested: a;
}

type C<a> = A<a> | B<a>;

type D = C<D> | string; // <-- i wish

While we had a long discussion about this on #3496, we closed that because the original issue was unblocked. We can certainly continue discussion a bit more. Is there a specific scenario you're interested in modeling here?

As I recall, this happens because type aliases do not actually create a type. Furthermore, the type argument position causes a circularity because the only way to look up the type reference in the instantiation cache is to know the id of each type argument. It is pretty much a consequence of the caching mechanism for generics.

Say you have a cyclic object graph of nodes defined like this:

interface Node { id: number; children: Node[]; }

When such graph gets serialized all cyclic references have to be encoded
with something different than Node:

interface Reference { nodeId: number; }

So ultimately the serializable object graph should be defined like this:

interface NodePlain { id: number; childern: (Node | Reference)[]; }

But practically during deserializing we want to replace all Reference
object with resolved Node objects, going back to the original definition:

interface Node { id: number; children: Node[]; }

So instead of maintaining 2 interfaces (one for serializing, one for
deserializing) I wish I could parametrize the Node interface with a type of
node:

interface Draft { id: number; children: Child [] }

Then we have:

type Node = Draft ;
type NodePlain = Draft <NodePlain | Reference>

function serialize (value: Node): NodePlain {}

function deserialize (value: NodePlain): Node {}
On Dec 23, 2015 7:25 PM, "Jason Freeman" notifications@github.com wrote:

As I recall, this happens because type aliases do not actually create a
type. Furthermore, the type argument position causes a circularity because
the only way to look up the type reference in the instantiation cache is to
know the id of each type argument. It is pretty much a consequence of the
caching mechanism for generics.

—
Reply to this email directly or view it on GitHub
#6230 (comment)
.

More basic example

type Json = null | string | number | boolean | Json [] | { [name: string]: Json }

In your serialization example, I think you could get by with:

interface Node extends Draft<Node> { }
interface NodePlain extends Draft<NodePlain | Reference> { }

As long as there is only one sort of Draft, yes I can do it. In a non trivial case I cannot: type Node = OneDraft<Node> | AnotherDraft <Node>

Why can't you do

interface Node extends OneDraft<Node>, AnotherDraft <Node> { }

Because I am looking for a sum type (either or) not a product type (this
and that).
On Dec 24, 2015 5:57 PM, "Jason Freeman" notifications@github.com wrote:

Why can't you do

interface Node extends OneDraft, AnotherDraft { }

—
Reply to this email directly or view it on GitHub
#6230 (comment)
.

Oh sorry, you're right. I misread it.

Well, the reason it happens is what I said before. Hopefully that can provide a clue about how to fix it.

As discussed in #7489, this issue is related to the special case of partial application in #5453, albeit indirectly.

I have a slightly different case where the current work-around is not satisfying. Consider two types following the work-around pattern:

type StringOrStringTree = (string | StringTree);
interface StringTree extends Array<StringOrStringTree> {}

type NumberOrNumberTree = (number | NumberTree);
interface NumberTree extends Array<NumberOrNumberTree>{}

Now what I want to write is a flatten function that flattens a tree into non-nested array such as (without types) would be:

function flatten(items) {
  let result = [];
  function flattenNode(node) {
    if (Array.isArray(node)) {
      node.forEach(flattenNode);
    }
    else {
      result.push(node);
    }
  }
  flattenNode(items);
  return result;
}

It is clear this would work correctly for both types but is there is no good typing for this function that allows both types and infers T without someway to express a recursive union type. Maybe something like:

function flatten<T>(tree: T | this[]: T[] {
  ....
}

would work where T | this[] would match a recursive union such as:

type StringOrStringTree = string | StringOrStringTree[];

where the this refers to the union type. Maybe self would be better here to avoid collision with other uses of this in a type position.

This example requires a way to express the type (which the work-around gives me) and a way of expressing the type relation implied by the type for type inferencing (which the work-around doesn't give me).

Here is some brain-storming around potential syntaxes:

  function flatten<T>(tree: T | this[]): T[];
  function flatten<T>(tree: T | self[]): T[];
  function flatten<T>(tree: T | union[]): T[];
  function flatten<T, S = T | S[]>(tree: S): T[];

The last one above is the most general solution, allows expressing the type relation directly, but might make the implementation too difficult as it would allow any type relation expressible in using a type alias. The advantage of using a special symbol is it allows the type to be written as a stand-alone expression without need for a meta-symbol in situation where a meta-symbol would be awkward (e.g. foo(a: string | this[])) .

Chuck Jazdzewski (@chuckjaz)

Chuck Jazdzewski (@chuckjaz)

T | this[]

👎 for anonymous recursive references. I don't see much of a use case for that, and it feels like a solution in search of a problem.

It also reminds me too much of arguments.callee conceptually.

i've been pointed at a surprisingly simple answer, i am confused how i didn't see it before

type Exp<T> = BinExp<T> | UnExp<T> | T;
type UnExp<T> = { sole: Exp<T>; };
type BinExp<T> = { left: Exp<T>; right: Exp<T> };

I have a similar example:

type Num = {
    type: "number",
    value: number,
};

type Add<T> = {
    type: "add",
    args: T[],
};

type Mul<T> = {
    type: "mul",
    args: T[],
};

type ExprF<T> = Num | Add<T> | Mul<T>;

The reason why I don't do something like:

type Add<T> = {
    type: "add",
    args: ExprF<T>[],
};

Is that I want to be able to use these types for recursion schemes. In particular I'd like to define cata a function which folds Expr into a ExprF<number> and returns the number (evaluate) or Expr into a ExprF<string> and returns the string (print). Expr is defined by type Expr = ExprF<Expr>.

If we expand the definition of Expr once we get:

type Expr = Num | Add<Expr> | Mul<Expr>;

which doesn't work, but if we expand the definition again we get:

type Expr = {
    type: "number",
    value: number,
} | {
    type: "add",
    args: Expr[],
} | {
    type: "mul",
    args: Expr[],
};

which does work. I wonder if the type checker could be modified to auto expand aliases when it encounters recursive generic type aliases.

Ken Howard (@kenhowardpdx)

Ken Howard (@kenhowardpdx) have you looked at this: #6230 (comment)

ZpdDG4gta (@zpdDG4gta8XKpMCd)

ZpdDG4gta (@zpdDG4gta8XKpMCd) the problem is that that formulation won't work with recursion schemes. Given a function:

const exprCata = <A>(transform: ExprF<A> => A, expr: ExprF<Expr>): A => {
    return transform(fmap(x => exprCata(transform, x), expr));
}

where fmap is defined as:

const fmap = <A, B>(fn: A => B, expr: ExprF<A>): ExprF<B> => {
    switch (expr.type) {
        case "number":
            return expr;
        case "add":
            return {
                type: "add",
                args: expr.args.map(fn),
            };
        case "mul":
            return {
                type: "mul",
                args: expr.args.map(fn),
            };
        default:
            return (expr: empty);
    }
}

by defining ExprF as type ExprF<T> = Num | Add<T> | Mul<T>; we're able to control what type of data Add and Mul nodes contain. Initially they contain Expr which is recursive but as exprCata runs, each Add/Mul node in the recursive structure is mapped to a non-recursive and then that non-recursive node is folded into into a single value.

Here's the rest of the code:

const evalTransform = (expr: ExprF<number>): number => {
    switch (expr.type) {
        case "number":
            return parseFloat(expr.value);
        case "add":
            return sum(expr.args);
        case "mul":
            return prod(expr.args);
        default:
            return (expr: empty);
    }
};

const ast = {
   type: "mul",
   args: [
       { type: "add": args: [{ type: "number", value: "2" }, { type: "number", value: "3" }]},
       { type: "number", value: "4" },
   ],
};

const result: number = exprCata(evalTransform, ast); // 20
// intermediary steps: (* (+ "2" "3") "4") => (* (+ 2 3) "4") => (* 5 4) => 20

Notice how evalTransform is not recursive. The recursive mapping of the ast has been extracted into fmap. exprCata allows us to reuse fmap and can be used to define other folds on the ast, e.g. pretty printing it.

The problem with:

type Exp<T> = BinExp<T> | UnExp<T> | T;
type UnExp<T> = { sole: Exp<T>; };
type BinExp<T> = { left: Exp<T>; right: Exp<T> };

is that it's always recursive which breaks recursion schemes.

The code I posted above works in Flow which got me thinking, why is it possible to declare recursive data types in Flow without running into a stack overflow? I think the proposal I made to auto-expand type aliases could provide a way to do this in TypeScript. I started prototyping the idea this weekend, but I'm not familiar with TypeScript internals so It's slow going. I did make some progress though. I was able to expand a the type aliases. I still need to figure out how to create a copy of the expanded type and then substitute T for Expr in the copy.

I came up with a different solution to make recursion schemes work in TypeScript. Instead of making the recursive type generic I define a helper type that replaces instances of a type (and arrays of the type) with a different type. This is used to define a generic type ExprF<T> from a non-generic type Expr.

type ReplaceType<T, Search, Replace> = {
    [P in keyof T]: T[P] extends Search 
        ? Replace 
        : T[P] extends Search[]
            ? Replace[]
            : T[P];
};

type Expr = {
    kind: "add",
    args: Expr[],
} | {
    kind: "mul",
    args: Expr[],
} | {
    kind: "number",
    value: string,
};

type ExprF<T> = ReplaceType<Expr, Expr, T>;

Using these new types, here's the "evaluate" example from my previous post:

const fmap = <A, B>(
    fn: (a: A) => B,
    expr: ExprF<A>,
): ExprF<B> => {
    switch (expr.kind) {
        case "number":
            return expr;
        case "add":
            return {
                kind: "add",
                args: expr.args.map(fn),
            };
        case "mul":
            return {
                kind: "mul",
                args: expr.args.map(fn),
            };
        default:
            throw new UnreachableCaseError(expr);
    }
}

const exprCata = <A>(
    fmap: (fn: (a: Expr) => A, expr: Expr) => ExprF<A>,
    transform: (exprA: ExprF<A>) => A, 
    expr: Expr,
): A => {
    return transform(fmap(x => exprCata(fmap, transform, x), expr));
}

const add = (a: number, b: number) => a + b;
const mul = (a: number, b: number) => a * b;
const zero = 0;
const one = 1;
const sum = (nums: number[]) => nums.reduce(add, zero);
const prod = (nums: number[]) => nums.reduce(mul, one);

const evaluateTransform = (expr: ExprF<number>): number => {
    switch (expr.kind) {
        case "number":
            return parseFloat(expr.value);
        case "add":
            return sum(expr.args);
        case "mul":
            return prod(expr.args);
        default:
            throw new UnreachableCaseError(expr);
    }
};

const evaluate = (ast: Expr) => exprCata(fmap, evaluateTransform, ast);

I think with a little more work a general version of exprCata is possible, but I'll leave that for another day.

Having to write type NestedMap<T> = Map<string, NestedMap<T> | T> as

type Node<T> = Map<string, T>;
interface NestedMap<T> extends Map<string, Node<T> | T> {}

(found solution in this thread)

Would be nice to have fixed :)

Eskild Diderichsen (@snebjorn)

Eskild Diderichsen (@snebjorn) I wouldn't say that these represent the same type:

type NestedMap<T> = Map<string, NestedMap<T> | T>

actually means

type NestedMap<T> = Map<string, T>
                  | Map<string, Map<string, T>>
                  | Map<string, Map<string, Map<string, T>>>
                  | ...

with T at any depth, while

type Node<T> = Map<string, T>;
interface NestedMap<T> extends Map<string, Node<T> | T> {}

is just the same as

type NestedMap<T> = Map<string, T>
                  | Map<string, Map<string, T>>

Patrik (@zepatrik)

Patrik (@zepatrik) oh crap, you're right.

Well then I guess this is the right place to ask for support for

type NestedMap<T> = Map<string, NestedMap<T> | T>

Eskild Diderichsen (@snebjorn)

Eskild Diderichsen (@snebjorn) I presume you meant this as your solution?

interface Node<T> extends Map<string, Node<T> | T> {}

(This is a rare case where it's not quite so hacky to use the interface workaround.)

I'm facing an issue which seem related to this:
Given the following code for (that's not the real code it's just to illustrate with a simplified version of the problem).

type BoundActions<
TState,
TActions extends Record<string,  (...args : any[]) => (getState: () => TState, setState: (newState: Partial<TState>) => void, actions: BoundActions<TState,TActions>) => any>
> = {
[K in keyof TActions]: (
  ...args: Parameters<TActions[K]>
) => ReturnType<ReturnType<TActions[K]>>;
};

function createStoreSimplified<TState, TActions extends Record<string, (...args : any[]) => (getState: () => TState, setState: (newState: Partial<TState>) => void, actions: BoundActions<TState, TActions>) => any>>(initialState: TState, actions: TActions) : BoundActions<TState, TActions>{
  
  let state = initialState;

  const setState = (newPartialSate: Partial<TState>) => state = {...state, ...newPartialSate};
  const getState = () => state;

  const boundProps: BoundActions<TState, TActions> = {} as BoundActions<TState, TActions>;

  for (const key in actions) {
    if (actions.hasOwnProperty(key)) {
      const element = actions[key];
      boundProps[key] = (...args) => element(args)(getState, setState, boundProps);
    }
  }
  return boundProps
}

The following works

type State = {value: number}
const initialState: State = { value: 0};

type ActionsType = typeof actions;

const actions = {
  increment: (by : number = 1) => (getState: () => State, setState: (newState: Partial<State>) => void, actions: BoundActions<State, ActionsType>) => {
    setState({value : getState().value + by});
  },
  doSomethingAndIncrement: () => (getState: () => State, setState: (newState: Partial<State>) => void, actions: BoundActions<State, ActionsType>) => {
    actions.increment();
  },
}

const store1 = createStoreSimplified(initialState, actions);

store1.increment();

But when relying on type inference it does not work anymore:

const store2 = createStoreSimplified(initialState,{
  increment: () => (get, set, actions) => {
    set({value : get().value + 1});
  },
  doSomethingAndIncrement: () => (get, set, actions) => {
    actions.increment();
  },
});

store2.increment();

I fails with Property 'increment' does not exist on type 'BoundActions<State, unknown>'.ts(2339). Basically it considers actions as unknwown.
i tried a couple of things but couldn't find a way to fix this. Maybe someone has an idea?

The full project is https://github.com/atlassian/react-sweet-state

With #33050 the original example can now be written as:

interface A<a> {
    brand: 'a';
    nested: a;
}

interface B<a> {
    brand: 'b';
    nested: a;
}

type D = A<D> | B<D> | string;

I'm running into this limitation.

The suggested approach:

interface A<a> {
    brand: 'a';
    nested: a;
}

interface B<a> {
    brand: 'b';
    nested: a;
}

type D = A<D> | B<D> | string;

...pretty much works, though it leads to some verbosity in my code, because if you have a type like:

type Wrapper<T> = FooWrapper<T> | BarWrapper<T> | BazWrapper<T>

which you need for other purposes, you can't actually use it in a type like:

type Node = Wrapper<Node> | string

You have to write:

type Wrapper<T> = FooWrapper<T> | BarWrapper<T> | BazWrapper<T>;
type Node = FooWrapper<Node> | BarWrapper<Node> | BazWrapper<Node> | string;

The other issue I ran into with the interface workaround is that an interface can extend a tuple like [A, B, C], but not a tuple with a ... in it. So I ended up playing musical chairs for a little while trying to understand the different type design constraints.

Navigation Menu

Repository navigation

allow recursive generic type aliases #6230

55 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

allow recursive generic type aliases #6230

Description

Activity

DanielRosenwasser commented on Dec 24, 2015

JsonFreeman commented on Dec 24, 2015

zpdDG4gta8XKpMCd commented on Dec 24, 2015

zpdDG4gta8XKpMCd commented on Dec 24, 2015

JsonFreeman commented on Dec 24, 2015

zpdDG4gta8XKpMCd commented on Dec 24, 2015

JsonFreeman commented on Dec 24, 2015

zpdDG4gta8XKpMCd commented on Dec 24, 2015

JsonFreeman commented on Dec 25, 2015

JsonFreeman commented on Dec 25, 2015

dead-claudia commented on Mar 30, 2016

chuckjaz commented on Apr 21, 2016

dead-claudia commented on Apr 21, 2016

55 remaining items

zpdDG4gta8XKpMCd commented on Apr 8, 2019

k4b7 commented on May 12, 2019

zpdDG4gta8XKpMCd commented on May 13, 2019

k4b7 commented on May 14, 2019

k4b7 commented on May 26, 2019

snebjorn commented on Jun 6, 2019

zepatrik commented on Jun 7, 2019

snebjorn commented on Jun 7, 2019

dead-claudia commented on Jun 7, 2019

sandorfr commented on Jul 1, 2019

ahejlsberg commented on Aug 30, 2019

dgreensp commented on Dec 31, 2023

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions