Recursive types?

[m0nkfish]

• I'm submitting a ...
  [ ] bug report
  [x] feature request
  [ ] question about the decisions made in the repository
  [ ] question about how to use this project

• Summary

I'm wondering if it's possible to support recursive ADTs, for example a classic linked list. My own attempts at a generalised ADT library have failed in this regard since the TS compiler can't handle the recursive type aliases

[twop]

Hey,

Thanks for the request!

it is technically possible to use an interesting trick with const declarations

const Obj = {
  prop: Obj // Error: Block-scoped variable 'Obj' used before its declaration.
}

const Obj2 = {
  prop: ()=> Obj2
}

console.log('hey it works', Obj2.prop())

Example: https://stackblitz.com/edit/recursive-type?file=index.ts

I was thinking about it, but in my own practice I haven't found a need for it.

A potential API:

import {Union, of, Self} from 'ts-union';
const List = Union({
  Empty: of(null),
  Elem: of<number, Self>() // 'number' is a type of values to store
})

Then type Self can be substitute (I'm not sure if it will actually work in ts though).

Or something like that

import {Union, of} from 'ts-union';

const List = Union(a => ({
  Empty: of(null),
  Elem: of(a, ()=>List) // or a wrapper defer(()=>List)
}))

Note that the version above is a generic variant, so it is akin to just classic List.

I'm not sure if this complexity is worth it, but feel free to maybe sketch out a syntax + types to brainstorm :)

[m0nkfish]

here's a use case for example, to model effects like PromiseAction - i implemented a quick equivalent in this case but would have used ts-union if there were an established way to reference self in types.

the Self idea is very interesting, i like it! i will see if i can come up with a scratchpad...

---

crude attempt: only replaces one level deep. not sure if possible to recurse within the type??

type Substitute<T, ToReplace, Replacement> =
  T extends ToReplace
  ? Replacement
  : T extends Array<infer U>
  ? Array<Substitute<U, ToReplace, Replacement>>
  : { [K in keyof T] : Substitute<T[K], ToReplace, Replacement> }

type List = 
| { type: 'nil' }
| { type: 'cons', item: number, rest: Self }

type SubbedList = Substitute<List, Self, List>

unfortunately type SubbedList = Substitute<List, Self, SubbedList> returns the usual recursive type error

[m0nkfish]

I kept plugging away - here's a proof-of-concept with the substitution approach

[twop]

@m0nkfish that's awesome!
I wonder how matching will work with Self, essentially matching is also recursive. Do you have an API sketch in mind?

[m0nkfish]

@twop match should be unaffected since Self is substituted in the case creation function. if you want to define a recursive function you can do so:

const List = Union({
  nil: Type<null>(),
  cons: Type<{ head: number, tail: Self }>(),
})
type List = typeof List.T

function sum(list: List): number {
  return List.match(list, {
    nil: () => 0,
    cons: ({ head, tail }) => head + sum(tail)
  })
}

[twop]

Upd: I didn't forget about this feature request. I'm working on a new feature: matching tuple of unions, and I don't want to focus on a new feature until I ship an MVP of matching tuples.

@m0nkfish thanks again for the patience and working on PoV for recursive types ! <3