Typescript: allow recursive generic type aliases

[zpdDG4gta8XKpMCd]

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

[DanielRosenwasser]

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]

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]

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

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
https://github.com/Microsoft/TypeScript/issues/6230#issuecomment-167013105
.

[zpdDG4gta8XKpMCd]

More basic example

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

[JsonFreeman]

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

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

[zpdDG4gta8XKpMCd]

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 | AnotherDraft

[JsonFreeman]

Why can't you do

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

[zpdDG4gta8XKpMCd]

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
https://github.com/Microsoft/TypeScript/issues/6230#issuecomment-167164813
.

[JsonFreeman]

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

[JsonFreeman]

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

[isiahmeadows]

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

[chuckjaz]

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[])) .

[isiahmeadows]

@chuckjaz

T | this[]

:-1: 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.

[chuckjaz]

@isiahmeadows I don't have a problem with it being named only I couldn't come up with a good way to do it. The last example was the best I could come up with but it is, as you can see, fairly ugly and only works in the context of a type variables, not in a single expression.

Suggestions?

[isiahmeadows]

So far, the closest to feasible idea to come up is caching type aliases like how interfaces are already. Everything else so far that has been suggested along those lines have been declined AFAIK.

// Now
interface JSONObject {
  [key: string]: JSONValue;
}

interface JSONArray extends Array<JSONValue> {}

type JSONValue =
  string |
  number |
  boolean |
  JSONArray |
  JSONObject;

// If type aliases are cached like interface types
type JSONValue =
  string |
  number |
  boolean |
  JSONValue[] |
  {[key: string]: JSONValue};

I think the discrepancy of how type aliases and interfaces are cached is what's causing all these problems in the first place. Two code paths for similar concepts make it easy for this to happen.

[chuckjaz]

I agree but, my point was that this is incomplete as it doesn't provide a way to declare a function that is generic over recursive union types. For this I need to be able to express a recursive type relation as well as the type itself, hence my examples.

[isiahmeadows]

Does my proposal not cover type Nested<T> = T | Nested<T>[], the type you need?

[chuckjaz]

Sorry! I totally missed that. I should read more carefully.

[calebmer]

Bump, this could be a super helpful extension to the type system and allow for all sorts of cool things languages like Haskell already allow for, like the functional list definition:

type List<T> = [T, List<T>] | []

[calebmer]

Also, if this works (which it does):

type List<T> = { a: [T, List<T>] } | []

and this doesn't:

type List<T> = [T, List<T>] | []

Then this issue should probably be considered a bug and not a new feature.

[isiahmeadows]

@calebmer

Also, if this works (which it does): [code omitted] and this doesn't: [code omitted] Then this issue should probably be considered a bug and not a new feature.

I feel it's a bug your first one doesn't trigger the cycle detector. In no other kind of situation without an interface in the way have I found recursively referenced type aliases not fail to check.

[isiahmeadows]

But I do feel that caching type aliases similarly to how interfaces are already cached (or else, interface T<U extends T<U>> wouldn't work) would really help.

---

As for my idea, here's what should check, assuming Bar and Baz are interfaces:

• type Foo = Bar - that's okay now.
• type Foo = Bar | Baz<Foo> - Recursive case not in top level.
• type Foo = Bar | Foo[] - Recursive case not in top level (Foo[] and Array<Foo> are the same).
• type Foo = Bar<Foo> - Recursive case not in top level.
• type Foo = Bar<Baz | Array<Foo>> - Recursive case not in top level.
• type Foo = Array<Bar | Foo> - Recursive case not in top level.
• type Foo = {x: Foo} - Recursive case not in top level.

Here's what shouldn't check, following the same assumptions:

• type Foo = Foo - Self-explanatory
• type Foo = Bar | Foo - Recursive case on top level.
• type Foo = Bar & Foo - Recursive case on top level.

Generics don't affect this at all, and for purposes of detecting cycles, the generic parameters are generally irrelevant. The only exception is that generic bounds limits cannot recursively reference the type at the top level, like in type Foo<T extends string | Foo<T>>. The only base case for that situation I know of is with F-bounded interface type like interface Bar<T extends Bar<T>>, and that's an exceptionally rare case to need it. (Well, technically, a string type works here as well...)

As for when multiple type aliases get involved, it should work by simply reducing the type aliases until they no longer contain any other type aliases at the top level. If any cycles come up, they should be reported.

[JsonFreeman]

@isiahmeadows I agree with the characterization of top-level versus non-top-level. That's a great way to put it.

[isiahmeadows]

@JsonFreeman Thanks! :smile:

I will point out that, as an odd edge case, it will allow type Foo = Foo[], but you can already use interface Foo extends Array<Foo> {} to a similar effect, even though it's a bit of an odd edge case itself.

[JsonFreeman]

I think it is good to allow type Foo = Foo[]. It is not at the top level

[isiahmeadows]

I was implying it's okay. It's just odd at the conceptual level (for the average programmer).

On a tangentially related note, where would be the best way to seek more input on a proposal? There doesn't seem to be any clear place(s) from what I've found.

[zpdDG4gta8XKpMCd]

would like to bring this up again, the following is not possible to express without recursive type aliases

type Expression = Binary<Expression> | Unary<Expression> | Conditional<Expression>;

please re-consider

[isiahmeadows]

@aleksey-bykov

First, there's nothing to reconsider at all, because nothing's been rejected (i.e. the "needs proposal" part). Just none of us here have enough time and/or knowledge to actually implement it.

Second, in your particular example, generics are generally rarely necessary in practice. That kind of problem comes up easily in basic recursive AST interpreters, where the type union is more type-safe and easier than extending an abstract class. Here's an example derived from this SO answer.

// Types
export interface Const { type: "const"; value: number }
export interface Var { type: "var"; name: string }
export interface Add { type: "add"; left: Node; right: Node }
export interface Sub { type: "sub"; left: Node; right: Node }
export interface Mul { type: "mul"; left: Node; right: Node }
export interface Div { type: "div"; left: Node; right: Node }
export interface Assign { type: "assign"; name: Var; value: Node }
export interface Loop { type: "loop"; cond: Node; body: Node }
export interface Seq { type: "seq"; body: Node[] }

export type Node =
  Const | Var |
  Add | Sub | Mul | Div |
  Assign | Loop | Seq

export type State = {[key: string]: number}

// Constructors
export const c = (value: number) => ({type: "const", value}) as Const
export const v = (name: string) => ({type: "var", name}) as Var
export const add = (left: Expr, right: Expr) => ({type: "add", left, right}) as Add
export const sub = (left: Expr, right: Expr) => ({type: "sub", left, right}) as Sub
export const mul = (left: Expr, right: Expr) => ({type: "mul", left, right}) as Mul
export const div = (left: Expr, right: Expr) => ({type: "div", left, right}) as Div
export const set = (name: string, value: Expr) => ({type: "assign", name: v(name), value}) as Assign
export const loop = (cond: Expr, value: Stmt) => ({type: "loop", cond, stmt}) as Loop
export const seq = (stmts: Stmt[]) => ({type: "seq", name, value}) as Seq

export function run(node: Node, state: State): Val {
  switch (node.type) {
  case "const": return node.value
  case "var":
    if (!{}.hasOwnProperty.call(state, node.name)) {
      throw new ReferenceError(`'${node.name}' is not set!`)
    }
    return state[node.name]
  case "add": return run(node.left, state) + run(node.right, state)
  case "sub": return run(node.left, state) - run(node.right, state)
  case "mul": return run(node.left, state) * run(node.right, state)
  case "div": return run(node.left, state) / run(node.right, state)
  case "assign": return state[node.name] = run(node.value, state)
  case "loop": {
    let result = 0
    while (run(node.cond, state)) result = run(node.body, state)
    return result
  }
  case "seq": {
    let result = 0
    for (const stmt of node.body) result = run(stmt, state)
    return result
  }
  }
}

// Example usage
const fib = seq([
  set("x", c(0)),
  set("y", c(1)),
  loop(v("n"), seq([
    set("t", add(v("x"), v("y"))),
    set("x", v("y")),
    set("y", v("t")),
    set("n", sub(v("n"), c(1))),
  ])),
  v("x"),
])

run(fib, {n: 25}) // 75025

The above in OCaml would look something like this:

type State = (string, int) Hashtbl.t
type Node =
  | C of int
  | V of string
  | Add of Node * Node
  | Sub of Node * Node
  | Mul of Node * Node
  | Div of Node * Node
  | Set of string * Node
  | While of Node * Node
  | Seq of Node list
exception Unbound of string

(* Yes, these types are inferred *)
let rec eval node state =
  match node with
    | C value -> value
    | V value ->
      try Hashtbl.find state value
      with Not_found -> raise (Unbound value)
    | Add (left, right) -> eval left state + eval right state
    | Sub (left, right) -> eval left state - eval right state
    | Mul (left, right) -> eval left state * eval right state
    | Div (left, right) -> eval left state / eval right state
    | Set (string, value) ->
      let result = eval value state in
      begin
        Hashtbl.replace state string result
        result
      end
    | While (cond, body) ->
      let result = ref 0 in
      begin
        while run cond state <> 0 do prev := run body state
        !result
      end
    | Seq body -> List.fold_left (fun _ stmt -> run stmt state) 0 body

(* Example usage *)
let () =
  let fib = Seq [
    Set "x" (C 0);
    Set "y" (C 1);
    While (V "n") (Seq [
      Set "t" (Add (V "x") (V "y"));
      Set "x" (V "y");
      Set "y" (V "t");
      Set "n" (Sub (V "n") (C 1))
    ]);
    V "x"
  ] in
  let state : State = Hashtbl.create 10 in
  begin
    Hashtbl.add state "n" 25
    run fib state (* 75025 *)
  end

[zpdDG4gta8XKpMCd]

annoyingly enough this works:

interface Expression {
    myself: Binary<Expression> | Unary<Expression> | Conditional<Expression>;
}

[isiahmeadows]

@aleksey-bykov I earlier suggested caching aliases and interfaces the same way, which would fix the problem pretty simply. I don't have much experience with the compiler or type checker, or I would probably be willing to take a stab at it.

[calebmer]

@isiahmeadows I actually like the caching aliases idea. It’s very annoying in declaration files that some of my larger union types are duplicated wherever it appears instead of being the cached union type.

[JsonFreeman]

It will involve introducing an actual type object in the compiler for type aliases. That is the main change as far as i know.

[chuckjaz]

This side benefit is that the fly-over hints and error message would be much better as currently they show the expanded union instead of the alias. I am tending to use union types more an more and even mildly complicated alias types render the fly-over hints useless as well as make the type errors very difficult to read.

[JsonFreeman]

Yes, that is an understated benefit that would probably be quite useful.

[isiahmeadows]

@chuckjaz I agree that it is rather annoying. Even something at least like `type Typeof = 'boolean' | 'string' | ... would be nice (and better than just a 'boolean' | 'string' | ... IMO).

[flying-sheep]

this is the signature of webpack conditions:

interface ConditionSpec {
    /** The Condition must match. The convention is the provide a RegExp or array of RegExps here, but it's not enforced. */
    test?: Condition;
    /** The Condition must match. The convention is the provide a string or array of strings here, but it's not enforced. */
    include?: Condition;
    /** The Condition must NOT match. The convention is the provide a string or array of strings here, but it's not enforced. */
    exclude?: Condition;
    /** All Conditions must match. */
    and?: Condition[];
    /** Any Condition must match. */
    or?: Condition[];
    /** The Condition must NOT match. */
    not?: Condition;
}
type Condition = string | RegExp | ((absPath: string) => boolean) | ConditionSpec | Condition[];

is there any trick to make this possible or do i have to resort to any?

[chuckjaz]

Try,

interface ConditionSpec {
    /** The Condition must match. The convention is the provide a RegExp or array of RegExps here, but it's not enforced. */
    test?: Condition;
    /** The Condition must match. The convention is the provide a string or array of strings here, but it's not enforced. */
    include?: Condition;
    /** The Condition must NOT match. The convention is the provide a string or array of strings here, but it's not enforced. */
    exclude?: Condition;
    /** All Conditions must match. */
    and?: Condition[];
    /** Any Condition must match. */
    or?: Condition[];
    /** The Condition must NOT match. */
    not?: Condition;
}
interface ConditionArray extends Array<Condition> { }
type Condition = string | RegExp | ((absPath: string) => boolean) | ConditionSpec | ConditionArray;

[flying-sheep]

then it just say that test recursively references itself.

i created a hack that allows shallow type safety (and just allows any one level deeper`, but to faithfully represent this (really not that complex type), i fear i’d need this feature…

[chuckjaz]

@flying-sheep I am using this style in one of my projects and it works (though my example is not as complex as yours) and my example works on the play ground and in VS Code using TypeScript 2.0. What am I missing?

[flying-sheep]

well:

node_modules/.bin/dt --print-files --path webpack                                                                        webpack-2 ✭ ✱ ◼
-----------------------------------------------------------------------------
 Files
-----------------------------------------------------------------------------
/home/phil/Dev/JS/DefinitelyTyped/webpack/index.d.ts
/home/phil/Dev/JS/DefinitelyTyped/webpack/tsconfig.json
/home/phil/Dev/JS/DefinitelyTyped/webpack/webpack-tests.ts
=============================================================================
                    DefinitelyTyped Test Runner 2.0.0
=============================================================================
 Typescript version: 2.1.0-dev.20161108
 Typings           : 1
 TypeScript files  : 1
 Total Memory      : 7933 mb
 Free Memory       : 183 mb
 Cores             : 8
 Concurrent        : 6
============================== Syntax checking ==============================
== Errors when compiling /home/phil/Dev/JS/DefinitelyTyped/webpack/tsconfig.json ==
\home\phil\Dev\JS\DefinitelyTyped\webpack\index.d.ts
         Line 226: 'test' is referenced directly or indirectly in its own type annotation.
x
-----------------------------------------------------------------------------
 Elapsed time    : ~1.196 seconds (1.196s)
 Successful      : 0.00% (0/1)
 Failure         : 100.00% (1/1)
=============================== Header format ===============================
.
-----------------------------------------------------------------------------
 Elapsed time    : ~0.005 seconds (0.005s)
 Successful      : 100.00% (1/1)
 Failure         : 0.00% (0/1)
-----------------------------------------------------------------------------
 Total
-----------------------------------------------------------------------------
 Elapsed time    : ~1.216 seconds (1.216s)
 Syntax error    : 100.00% (1/1)
 Invalid header  : 0.00% (0/1)
-----------------------------------------------------------------------------
=============================================================================
                    Errors in files
=============================================================================
----------------- For file:/home/phil/Dev/JS/DefinitelyTyped/webpack/tsconfig.json
\home\phil\Dev\JS\DefinitelyTyped\webpack\index.d.ts
         Line 226: 'test' is referenced directly or indirectly in its own type annotation.
=============================================================================

[chuckjaz]

Can you make this into a branch I can pull?

[flying-sheep]

no problem

[chuckjaz]

The problem seems to be some weird interaction between the RegExp type and the optional test member of the ConditionSpec interface. If you make test required (remove the ?), or remove RegExp from Condition, or change test to not be the same of any member of RegExp, String or Function the error goes away.

@mhegazy Is this intentional. The error seems weird to me. BTW, this is new to 2.0. 1.8 does not produce this error.

[flying-sheep]

@chuckjaz sadly that’s not an an option, as this interface is correct as it is.

hmm, what i could do is

interface BaseConditionSpec {
    test?: Condition;
    include?: Condition;
    exclude?: Condition;
    and?: ConditionArray;
    or?: ConditionArray;
    not?: Condition;
}
interface TestConditionSpec { test: Condition }
interface IncludeConditionSpec { include: Condition }
[...]
type ConditionSpec = TestConditionSpec | IncludeConditionSpec | [...];

which would also be correct (an empty object would probably be legal, but useless)

[chuckjaz]

This seems to work:

interface ConditionSpec {
    /** The Condition must match. The convention is the provide a string or array of strings here, but it's not enforced. */
    include?: Condition;
    /** The Condition must NOT match. The convention is the provide a string or array of strings here, but it's not enforced. */
    exclude?: Condition;
    /** All Conditions must match. */
    and?: Condition[];
    /** Any Condition must match. */
    or?: Condition[];
    /** The Condition must NOT match. */
    not?: Condition;
}

interface TestConditionSpec {
    test: Condition;
}
interface ConditionArray extends Array<Condition> { }
type Condition = string | RegExp | ((absPath: string) => boolean) | TestConditionSpec | ConditionSpec | ConditionArray;

This implies that including test implies that you cannot also include or. That seems desirable because I am not sure what supplying and and or would mean, for example.

[flying-sheep]

well, but test and exclude together _do_ make sense.
(e.g. { test: /.*[.]js/, exclude: 'node_modules' })

i tried this, but it’s worse (more errors)

[chuckjaz]

How about:

    interface BaseConditionSpec {
        /** The Condition must match. The convention is the provide a string or array of strings here, but it's not enforced. */
        include?: Condition;
        /** The Condition must NOT match. The convention is the provide a string or array of strings here, but it's not enforced. */
        exclude?: Condition;
    }

    interface TestConditionSpec extends BaseConditionSpec {
        /** The Condition must match. The convention is the provide a RegExp or array of RegExps here, but it's not enforced. */
        test: Condition;
    }

    interface AndConditionSpec extends BaseConditionSpec {
        /** All Conditions must match. */
        and: ConditionArray;
    }

    interface OrConditionSpec extends BaseConditionSpec {
        /** Any Condition must match. */
        or: ConditionArray;
    }

    interface NotConditionSpec extends BaseCondtionSpec {
        /** The Condition must NOT match. */
        not: Condition;
    }

    interface ConditionArray extends Array<Condition> {} 
    type Condition = string | RegExp | ((absPath: string) => boolean) | TestConditionSpec | OrConditionSpec | AndConditionSpec | NotConditionSpec| ConditionArray;

[flying-sheep]

thanks, this did it!

[ethanresnick]

Another use case I ran into, just in case it helps when evaluating potential solutions or raising the priority of this issue a bit:

I have a function that generates html from a tuple, where the first entry is the tag name, the second is the attributes (which can be omitted), and the third is entry is the contents (which can be another tag).

// the below generates <div id="adiv"><span>content!</span></div>
html(["div", {id: "adiv"}, ["span", "content!"]])

The signature for this function would be something like:

html(content: TagBlock)

where a TagBlock refers to a TagContents type, which indirectly refers to a TagBlock:

type TagBlock = [TagName, TagAttributes, TagContents] | [TagName, TagContents];

type TagName = 'div' | 'span' | ... ... | 'input';
type TagAttributes = any;
type TagContents = string | number | TagBlock;

EDIT: I think the way to work around this at the moment is to do something like the below, which kinda works...but is really ugly:

export type TagBlock = TagBlockNoAttributes | TagBlockWithAttributes;

export interface TagBlockNoAttributes extends Array<any> {
  0: TagName,
  1: TagContents
}

export interface TagBlockWithAttributes extends Array<any> {
  0: TagName,
  1: TagAttributes,
  2: TagContents
}

[zpdDG4gta8XKpMCd]

what makes you think think your workaround works? it is literally the same
as the original type expression

On Sep 1, 2017 5:04 PM, "Brandon Bloom" [e-mail] wrote:

I just ran in to this while trying to add types to a pretty simple
recursive structure:

type Tree = string | string[];

I worked around it like this:

type GenericTree = T | T[];type Tree = GenericTree;

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/Microsoft/TypeScript/issues/6230#issuecomment-326683355,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AA5Pzaog8jnSyh6TvROCTC6Fbk6k0GPOks5seHFhgaJpZM4G62Xy
.

[brandonbloom]

Sorry, posted that comment by accident - wasn't done editing it.

[kgtkr]

type Flat<T> = T extends (infer P)[] ? Flat<P> : T;

error

[coolreader18]

Hi, this works (with --strict true):

type A = string | B;
interface B<T extends A = symbol> {
  a: T extends symbol ? A : T;
}

So...

[zpdDG4gta8XKpMCd]

@coolreader18 so what?
this works too: interface List<A> { value: A; rest: List<A> | null; }

[coolreader18]

Because this:

type A = string | B;
interface B<T extends A = A> {
  a: T;
}

doesn't work.
Sorry, I was working on a solution to this for a bit and forgot why it was important that what I found worked.

Edit:
You can do it with a unique symbol to:

const _S: unique symbol;
type A = string | B;
interface B<T extends A = typeof _S> {
  a: T extends typeof _S ? A : T;
}

[zpdDG4gta8XKpMCd]

so what is your point? linking a type to itself via interface isn't very useful of impressive, recursive interface's were here from version 0.8 of typescript, here we are talking about type's which are different in this regard, try using type instead of interface in your example and you will see what i am talking about

[teroneko]

@kgtkr

type Flat<T> = T extends (infer P)[] ? Flat<P> : T;

error

This works like a charm:

type InferDiscard<V> = V extends { _: infer T } ? T : V;
type Flat<T> = InferDiscard<T extends (infer P)[] ? { _: Flat<P> } : T>;
type Flatted = Flat<["a", ["b", ["c", ["d"]]]]>;
// Results in "a" | "b" | "c" | "d"

Thanks @calebmer for the hint. 😄

[jordwest]

@devlato found a way around this that worked in TS <= 3.2:

For the example in the description:

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

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

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

type D<T extends D<T> = D<T>> = C<T> | string;

Unfortunately this no longer works in TS 3.3 - see #29803

[mike-marcacci]

Is there any way to currently express a type like the one described by @aleksey-bykov above?

type RawJSON =
  | null
  | string
  | number
  | { [key: string]: RawJSON }
  | RawJSON[];

While this is a bit contrived, my real-world use case is in representing GraphQL type definitions, which this limitation makes impossible to correctly describe. Currently I define an arbitrary, fixed number of types for each "depth", with the final one resolving unsafely to any. In practice I don't see arrays nested very deeply, so this is fine, but I dislike that a user will silently lose type safety if they do.

[mike-marcacci]

As a followup, I have a few questions that might help move this along:

1. Is there any theoretical objection to this? If this was correctly implemented in a PR, would it be considered?
2. Is there any practical limitation on implementing this? For example, are the internal data structures in TS unable to represent this?
3. Is there anybody actively working on this (either at MS or in the community)?

[weswigham]

type RawJSON =
  | null
  | string
  | number
  | { [key: string]: RawJSON }
  | RawJSONArray;

interface RawJSONArray extends Array<RawJSON> {}

is the canonical example workaround.

[masaeedu]

Assuming we had the ability to abstract over type constructors, one approach that would make this easier from an implementation point of view would be to disallow arbitrary recursion, and instead have a special Fix type constructor baked in that acts as the equivalent of:

// :: type Fix : (* -> *) -> *
type Fix<F> = F<Fix<F>>

Then you can express any recursive type as an ordinary non-recursive type with an extra type parameter. The Fix type would be used to "tie the knot", producing the fixpoint of an unsaturated type constructor:

type RawJSONF<X> = | null
                   | string
                   | number
                   | { [key: string]: X }
                   | X[]

type RawJSON = Fix<RawJSONF>

This would make it easy for the type checker to distinguish recursive from non-recursive types, since all recursive types would be of the form Fix<F>, and during typechecking F can be instantiated repeatedly until we match some case that no longer mentions F's final type parameter.

[isiahmeadows]

@masaeedu Slight problem: you need some form of quantification plus some form of lambda-like abstraction for type-level operators. Typing that isn't exactly trivial, since you basically need a recursive type to define a type. (And by that point, it'd be easier to introduce dependent types.)

I would like higher-order generic type support, but a fixpoint combinator really isn't on that list due to pragmatic concerns around type theory.

[masaeedu]

@isiahmeadows I don't quite follow what you mean by "you basically need a recursive type to define a type". The proposal above doesn't require quantification, which is orthogonal in the lambda cube to type constructors, the only feature it does actually require. Given the ability to define non-recursive type constructors in user code, and a baked in fixpoint combinator for type constructors, you can express any recursive type constructor.

I don't understand the aside about dependent types either, but once again you also don't need dependent types for the proposal above, since they are also an orthogonal feature in the lambda cube to type constructors.

[isiahmeadows]

You're correct that the above doesn't require quantification, but that doesn't hold for the general case of the Y combinator, which supports arbitrary anonymous recursion, powerful enough it enables untyped lambda calculus to compute anything any Turing machine can.

But it's worth noting that you don't need unbounded recursion to support that type - you could just use a variant of this, generalized to also include unions and intersections. The Turing-completeness of TS's type system could then be safely broken by applying a similar check with indexed types. And although they do appear open to that in theory, they concluded that for the time being, "we're not quite ready for this sort of thing". (They weren't fond of the fact it seemed to complicate consumer code, and you'd have to fix that by normalizing conditional types to nest the conditions' results as far as possible, something TS doesn't currently do.)

[masaeedu]

but that doesn't hold for the general case of the Y combinator

Well no, not even the Y combinator at the type level requires quantification. Quantification or its absence is an orthogonal feature of a type system to the availability of and restrictions on type constructors.

powerful enough it enables untyped lambda calculus to compute anything any Turing machine can

It doesn't seem like Turing completeness is relevant here, given that the type system is already Turing complete. But while we're talking about irrelevant things: we don't need to talk about some other combinator to discuss this; introduction of Fix suffices to break strong normalization of a simply typed lambda calculus at the type level and make type checking undecidable, just as STLC + fix at the term level loses strong normalization.

Whether you allow:

type LList<X> = { case: "nil" } | { case: "cons", x: X, xs: LList<X> }

or:

type LList<X, R> = { case: "nil" } | { case: "cons", x: X, xs: R }
type List<X> = Fix<LList<X>>

does not have any bearing on the properties of the type system, it's purely an implementation and user experience concern.

There are workarounds that let us formulate things in a way where the Fix combinator is more restrictive, but without even a basic kind system it's difficult to reason about out whether they prevent the introduction of Turing completeness. And besides, as I mentioned earlier, the type system is Turing complete anyway!

[zpdDG4gta8XKpMCd]

sorry for crashing the party, but i am not sure where it is all going, i only wish i could do the following:

type Expression = BinaryExpression<Expression> | UnaryExpression<Expression> | TrenaryExpression<Expresion> | /* ...other stuff */

am i asking for too much?

[masaeedu]

@aleksey-bykov I don't think so. Before we started talking about Turing completeness and all kinds of other irrelevant tangents, I was suggesting that it would be easier to instead implement support for:

type ExpressionF<X> = BinaryExpression<X> | UnaryExpression<X> | ...
type Expression = Fix<ExpressionF>

if perhaps less convenient to use.

[zpdDG4gta8XKpMCd]

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> };

[kevinbarabash]

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]

@kenhowardpdx have you looked at this: https://github.com/microsoft/TypeScript/issues/6230#issuecomment-480917723

[kevinbarabash]

@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.

[kevinbarabash]

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]

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]

@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]

@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>

[isiahmeadows]

@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.)

[sandorfr]

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]

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;