Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

2257 - MinusOne #2563

Open
somebody1234 opened this issue Aug 10, 2021 · 6 comments
Open

2257 - MinusOne #2563

somebody1234 opened this issue Aug 10, 2021 · 6 comments
Labels
2257 answer Share answers/solutions to a question en in English

Comments

@somebody1234
Copy link

somebody1234 commented Aug 10, 2021 •
edited
Loading

TS Playground.

Uses tuples for arithmetic, and a trampoline to bypass instantiation limit. Since it's rated as medium difficulty though, this is probably completely overkill and I'm probably missing something blindingly obvious.

type ArrayOfLength<N extends number, Intermediate extends unknown[]=[]> = Defer<
    number extends N
  ? unknown[]
  : Intermediate['length'] extends N
  ? Result<Intermediate>
  : ArrayOfLength<N, [unknown, ...Intermediate]>
>;

type MinusOne<T extends number> =
  x2e3<ArrayOfLength<T>>['value'] extends [unknown, ...infer U]
? U['length']
: never;

interface Defer<T> {
  next: T,
  value: unknown,
}

interface Result<T> extends Defer<Result<T>> {
  value: T,
}

type x1e0<T> = T[Extract<"next", keyof T>];

type x1e1<T> = (
  x1e0<T> extends infer T
    ? x1e0<T> extends infer T
      ? x1e0<T> extends infer T
        ? x1e0<T> extends infer T
          ? x1e0<T> extends infer T
            ? x1e0<T> extends infer T
              ? x1e0<T> extends infer T
                ? x1e0<T> extends infer T
                  ? x1e0<T> extends infer T
                    ? x1e0<T>
                    : never
                  : never
                : never
              : never
            : never
          : never
        : never
      : never
    : never
)

type x1e2<T> = (
  x1e1<T> extends infer T
    ? x1e1<T> extends infer T
      ? x1e1<T> extends infer T
        ? x1e1<T> extends infer T
          ? x1e1<T> extends infer T
            ? x1e1<T> extends infer T
              ? x1e1<T> extends infer T
                ? x1e1<T> extends infer T
                  ? x1e1<T> extends infer T
                    ? x1e1<T>
                    : never
                  : never
                : never
              : never
            : never
          : never
        : never
      : never
    : never
)

type x1e3<T> = (
  x1e2<T> extends infer T
    ? x1e2<T> extends infer T
      ? x1e2<T> extends infer T
        ? x1e2<T> extends infer T
          ? x1e2<T> extends infer T
            ? x1e2<T> extends infer T
              ? x1e2<T> extends infer T
                ? x1e2<T> extends infer T
                  ? x1e2<T> extends infer T
                    ? x1e2<T>
                    : never
                  : never
                : never
              : never
            : never
          : never
        : never
      : never
    : never
)

type x2e3<T> = (
  x1e3<T> extends infer T
    ? x1e3<T>
    : never
)
@somebody1234 somebody1234 added answer Share answers/solutions to a question en in English labels Aug 10, 2021
@github-actions github-actions bot added the 2257 label Aug 10, 2021
@somebody1234
Copy link
Author

4.5 beta has TCO - however this is still not enough for the final test case as it only goes up to 1000 iterations.

@DaniGuardiola
Copy link

@somebody1234 I'd love to understand what's going on in your solution, care to explain (or link me to resources that explain the techniques)? :)

@somebody1234
Copy link
Author

The x<n>e<m> is a trampoline (seems to be used in the Lisp sense - a loop that iteratively invokes a function, i.e. essentially turning a recursive function into an iterative one) - I've taken the implementation from somewhere else so I'm not 100% sure how exactly it works - however it seems it uses extends infer to essentially reset the recursion depth, so we can bypass the maximum recursion depth

ArrayOfLength<N> is the normal way to generate a tuple of length N, except refactored to be lazy (= use Defer and Result)

Do note however that this is generally not very useful since:
a) If you have this many iterations it's probably going to start degrading compiler performance
b) As mentioned above, the TCO improvements should already be plenty for almost all real world use cases.

Worth noting though, that extends infer does still have real world use cases wrt recursion, since it can be used to stop those "type is excessively deep" errors by changing <complex type or recursive call> to <complex type or recursive call> extends infer U ? U : never

@somebody1234
Copy link
Author

Worth noting that if/when this gets merged, there will be a much, much easier way to do this (and type-level arithmetic in general)

@Lionad-Morotar
Copy link
Contributor

Lionad-Morotar commented Apr 19, 2022 •
edited
Loading

中文解答。可能有问题，欢迎交流。

  • Defer 意味着惰性计算，一定要通过取得其 next 属性，才能得到下一个 Defer。
  • type Result 继承了 Defer<Result> 使得 Result 可以无限次数调用 next 属性来得到其自身。
  • 所以，只要尽可能设计一个可以调用足够多次数的函数去获取某个 Defer 的 next 属性就好了。

在 JavaScript 中可以使用 While 循环轻松调用无限次数，但是在 TypeScript 的类型系统中（在这段代码中），需要手动枚举。x2e3、x1e3、x1e2、x1e1 这几个函数就是用来手动调用 next 属性的。每次执行 x2e3，同时执行十次 x1e3；每次执行 x1e3，同时执行十次 x1e2... 这算是一个类似 for 循环之类的东西，最后，执行 x1e1 获取 next 属性。

可以通过计算获得一楼的代码到底执行了多少次 x1e1：2 * 10 * 10 * 10 === 2000，所以最多只能计算到 MinusOne<1999>，从 MinusOne<2000> 开始，代码就会报错。如果需要计算更大的数字，则要手动改造 x2e3 来获得更多次循环。

我的这段代码也许更易读一些：TypeScript Playground

This was referenced Apr 19, 2022
Open
Open
@tenkirin
Copy link
Contributor

I couldn't understand it, but I'm impressed!

我看不懂，但我大受震撼！

理解できないけど、震撼されてしまう！

image

@Lionad-Morotar Lionad-Morotar mentioned this issue Apr 22, 2022
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
2257 answer Share answers/solutions to a question en in English
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@somebody1234 @DaniGuardiola @Lionad-Morotar @tenkirin