Repository: TypeScript
Issue: Provide declaration of sparse array
Labels: Suggestion,Awaiting More Feedback

# lib Update Request

While majority of arrays in JavaScript / TypeScript are dense arrays, occasionally there are use cases for sparse array. (We are using it in Canva for some core data structures.)

Sparse array has some interesting behavior different from a dense array, for example, all the methods iterating it (like `forEach`, `map`, `every`, etc.) only visits occupied slots, while `@@iterator` and index access (for index < length) can visit empty slots with `undefined`.

I've done some spike to declare sparse array as an interface with a subset of array, and so far I have:
<details>

```typescript
export interface ReadonlySparseArray<T> {
  //
  // From lib.es5.d.ts
  //

  readonly length: number;
  join(separator?: string): string;
  slice(start?: number, end?: number): SparseArray<T>;
  indexOf(searchElement: T, fromIndex?: number): number;
  lastIndexOf(searchElement: T, fromIndex?: number): number;
  every<S extends T>(
      predicate: (value: T, index: number) => value is S,
  ): this is ReadonlySparseArray<S>;
  every(predicate: (value: T, index: number) => unknown): boolean;
  some(predicate: (value: T, index: number) => unknown): boolean;
  forEach(callbackFn: (value: T, index: number) => void): void;
  map<U>(callbackFn: (value: T, index: number) => U): SparseArray<U>;
  filter<S extends T>(predicate: (value: T, index: number) => value is S): S[];
  filter(predicate: (value: T, index: number) => unknown): T[];
  reduce(
      callbackFn: (previousValue: T, currentValue: T, currentIndex: number) => T,
      initialValue?: T,
  ): T;
  reduce<U>(
      callbackFn: (previousValue: U, currentValue: T, currentIndex: number) => U,
      initialValue: U,
  ): U;
  reduceRight(
      callbackFn: (previousValue: T, currentValue: T, currentIndex: number) => T,
      initialValue?: T,
  ): T;
  reduceRight<U>(
      callbackFn: (previousValue: U, currentValue: T, currentIndex: number) => U,
      initialValue: U,
  ): U;
  readonly [n: number]: T | undefined;

  //
  // From lib.es2015.core.d.ts
  //

  find<S extends T>(predicate: (value: T, index: number) => value is S): S | undefined;
  find(predicate: (value: T, index: number) => unknown): T | undefined;

  //
  // From lib.es2019.array.d.ts
  //

  flatMap<U>(callback: (value: T, index: number) => U | readonly U[] | ReadonlySparseArray<U>): U[];
}

export interface SparseArray<T> extends ReadonlySparseArray<T> {
  //
  // From lib.es5.d.ts
  //

  length: number;
  pop(): T | undefined;
  push(...items: T[]): number;
  shift(): T | undefined;
  splice(start: number, deleteCount?: number): SparseArray<T>;
  splice(start: number, deleteCount: number, ...items: T[]): SparseArray<T>;
  unshift(...items: T[]): number;
  [n: number]: T | undefined;
}
```

</details>

It seemingly works fine to some extent, with two issues (apart from all the things lacked currently) I see:

First, it has problem with assigning dense array to the type. Ideally, a dense array can be assigned to a variable with sparse array type, but not the reverse. When `T` is simple, it works as expected, however, when `T` gets more complicated, the assignment sometimes gets mysteriously rejected with something like:
> Type 'SomeComplicatedType[]' is not assignable to type 'ReadonlySparseArray<SomeComplicatedType>'.
>   The types returned by 'slice(...).map(...)' are incompatible between these types.
>     Type 'U[]' is not assignable to type 'SparseArray<U>'.

However, if I add a simple assignment to the start of a file with this kind of errors, e.g. `const _a: SparseArray<string> = ['a'];`, then all the errors go away in that file. This is likely a bug in TypeScript's type checker that I haven't been able to construct a minimal reproducible example for (will create a separate issue if I can construct it).

Second, the type for index definition is actually wrong. It should really have a getter returning `T | undefined`, but a setter only accepting `T`, because `undefined` should only be accepted for a sparse array of `T | undefined`, not a sparse array of `T`, since it would turn an empty slot into an occupied slot with `undefined`, affecting behavior of the iterating methods. But as far as I know, there is no way to declare different type for setter and getter on interface in TypeScript.

Given all these challenges and that it's an existing thing in JavaScript, I think it would be good to have the type declarations provided by TypeScript directly.