GeezerVison is showing github.com — allow recursive generic type aliases · Issue #6230 · microsoft/TypeScript
allow recursive generic type aliases #6230Descriptioninterface 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 wishReacted by Jaden Geller, Dave Falke, Jonah Scheinerman, Asad Saeeduddin, Shu Uesugi, n9, Ilia Sidorenko, Nurbol Alpysbayev, int0h, Michał Gołębiowski-Owczarek and 32 more ActivityDanielRosenwasser commented on Dec 24, 2015 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? JsonFreeman commented on Dec 24, 2015 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. zpdDG4gta8XKpMCd commented on Dec 24, 2015 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" [email protected] 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)
.
zpdDG4gta8XKpMCd commented on Dec 24, 2015 More basic example
type Json = null | string | number | boolean | Json [] | { [name: string]: Json } Reacted by Caleb Meredith, Josh Kuhn, Sean Vieira, Francis Crick, Alexander “weej” Jones, Brandon Bloom, Tom Crockett, Jan Olaf Martin, marsiancba, Wessel Kronemeijer and 55 more JsonFreeman commented on Dec 24, 2015 In your serialization example, I think you could get by with:
interface Node extends Draft<Node> { }
interface NodePlain extends Draft<NodePlain | Reference> { }zpdDG4gta8XKpMCd commented on Dec 24, 2015 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> JsonFreeman commented on Dec 24, 2015 Why can't you do
interface Node extends OneDraft<Node>, AnotherDraft <Node> { }zpdDG4gta8XKpMCd commented on Dec 24, 2015 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" [email protected] wrote:
Why can't you do
interface Node extends OneDraft, AnotherDraft { }
—
Reply to this email directly or view it on GitHub
#6230 (comment)
.
JsonFreeman commented on Dec 25, 2015 Oh sorry, you're right. I misread it. JsonFreeman commented on Dec 25, 2015 Well, the reason it happens is what I said before. Hopefully that can provide a clue about how to fix it. dead-claudia commented on Mar 30, 2016 As discussed in #7489, this issue is related to the special case of partial application in #5453, albeit indirectly. chuckjaz commented on Apr 21, 2016 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[])) . dead-claudia commented on Apr 21, 2016 Chuck Jazdzewski (@chuckjaz)
👎 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. zpdDG4gta8XKpMCd commented on Apr 8, 2019 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> };
k4b7 commented on May 12, 2019 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. zpdDG4gta8XKpMCd commented on May 13, 2019 k4b7 commented on May 14, 2019 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. Reacted by Radosław Miernik k4b7 commented on May 26, 2019 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. snebjorn commented on Jun 6, 2019 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 :) zepatrik commented on Jun 7, 2019 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>>snebjorn commented on Jun 7, 2019 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> dead-claudia commented on Jun 7, 2019 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.) Reacted by Eskild Diderichsen sandorfr commented on Jul 1, 2019 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 ahejlsberg commented on Aug 30, 2019 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;Reacted by Titian Cernicova-Dragomir, Claudia Meadows, James Conkling, rvion, Victor Magalhães, Eskild Diderichsen, Sergey, SlurpTheo, franckXu, Michael Stramel and 3 more Reacted by reverofevil Reacted by Obed, Victor Magalhães, Eskild Diderichsen, Claudia Meadows, Patrik, Mateusz Bednarski and codestar73 Reacted by rvion, Mike Marcacci, Victor Magalhães, Eskild Diderichsen, Wes Roberts, Mateusz Bednarski and Artur Mostowski dgreensp commented on Dec 31, 2023 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.
MetadataMetadataDevelopmentNo branches or pull requestsIssue actions
|