Linked list comparison between TypeScript and ReScript

list-classes.ts

export abstract class List<T> {
  readonly isEmpty: boolean
  constructor(readonly length: number) {
    this.isEmpty = !length
  }
  *[Symbol.iterator](): Generator<T, void, void> {
    for (let xs = this as List<T>; xs instanceof NonEmptyList; xs = xs.rest)
      yield xs.first
  }
}

export class NonEmptyList<T> extends List<T> {
  constructor(readonly first: T, readonly rest: List<T>) {
    super(rest.length + 1)
  }
}

export class EmptyList extends List<never> {
  static #instance: EmptyList
  constructor() {
    super(0)
    return (EmptyList.#instance ??= this)
  }
}

list-functions.ts

import { EmptyList, List, NonEmptyList } from "./list-classes"

export const empty = new EmptyList()
export const shift = <T>(first: T, rest: List<T>) =>
  new NonEmptyList(first, rest)
export const make = <T>(...xs: T[]) =>
  xs.reduceRight((ys, x) => shift(x, ys), empty as List<T>)
export const convert = <T>(xs: Iterable<T>) => make(...xs)

export const push = <T>(xs: List<T>, x: T): NonEmptyList<T> =>
  xs instanceof NonEmptyList
    ? shift(xs.first, push(xs.rest, x))
    : shift(x, empty)

export const pop = <T>({ first, rest }: NonEmptyList<T>): [List<T>, T] => {
  if (rest instanceof NonEmptyList) {
    const [init, last] = pop<T>(rest)
    return [shift(first, init), last]
  } else return [empty, first]
}

export const unsafeGet = <T>(xs: NonEmptyList<T>, index: number) => {
  if (index < -xs.length || index >= xs.length)
    throw new Error("index out of bounds")
  const safeGet = ({ first, rest }: NonEmptyList<T>, index: number): T =>
    index < 1 ? first : safeGet(rest as NonEmptyList<T>, index - 1)
  return safeGet(xs, index < 0 ? index + xs.length : index)
}

export const unsafeDelete = <T>(xs: NonEmptyList<T>, index: number) => {
  if (index < -xs.length || index >= xs.length)
    throw new Error("index out of bounds")
  const safeDelete = (
    { first, rest }: NonEmptyList<T>,
    index: number,
  ): [List<T>, T] => {
    if (index < 1) return [rest, first]
    else {
      const [skipped, deleted] = safeDelete(rest as NonEmptyList<T>, index - 1)
      return [shift(first, skipped), deleted]
    }
  }
  return safeDelete(xs, index < 0 ? index + xs.length : index)
}

list-tests.ts

import { EmptyList } from "./list-classes"
import * as List from "./list-functions"

const shiftTest = List.shift("hello", List.shift("world", List.empty)) //?
const makeTest = List.make("hello", "world") //? Array.from($)
const emptyTest = List.make() //? Array.from($)
console.assert(emptyTest === new EmptyList())
const pushPopTest = List.pop(List.push(List.push(List.empty, "hello"), "world")) //?
List.unsafeGet(shiftTest, 0) //?
List.unsafeGet(shiftTest, 1) //?
// List.unsafeGet(shiftTest, 2) // exception
const deleteTest = List.unsafeDelete(shiftTest, 0) //? $[0]
List.unsafeDelete(shiftTest, 1) //? $[1]
// List.unsafeDelete(shiftTest, 2) // exception

list.res

type rec list<'t> = EmptyList | NonEmptyList('t, list<'t>, int)

let length = xs =>
  switch xs {
  | EmptyList => 0
  | NonEmptyList(_, _, length) => length
  }
let empty = EmptyList
let shift = (rest, first) => NonEmptyList(first, rest, rest->length + 1)
let make = xs => xs->Belt.Array.reduceReverse(empty, shift)
/*
let makeTest = ["hello", "world"]->make
 * convert is impossible :(
 */

let rec push = (xs, x) =>
  switch xs {
  | EmptyList => empty->shift(x)
  | NonEmptyList(first, rest, _) => rest->push(x)->shift(first)
  }

@warning("-8")
let rec unsafePop = (NonEmptyList(first, rest, _)) =>
  switch rest {
  | EmptyList => (empty, first)
  | NonEmptyList(_, _, _) => {
      let (init, last) = rest->unsafePop
      (init->shift(first), last)
    }
  }

let unsafeGet = (xs, index) => {
  let length = xs->length
  if index < length || index >= length {
    invalid_arg("index out of bounds")
  }

  @warning("-8")
  let rec safeGet = (NonEmptyList(first, rest, _), index) =>
    index == 0 ? first : rest->safeGet(index - 1)
  xs->safeGet(index < 0 ? index + length : index)
}

let unsafeDelete = (xs, index) => {
  let length = xs->length
  if index < length || index >= length {
    invalid_arg("index out of bounds")
  }

  @warning("-8")
  let rec safeDelete = (NonEmptyList(first, rest, _), index) => {
    if index == 0 {
      (rest, first)
    } else {
      let (skipped, deleted) = rest->safeDelete(index - 1)
      (skipped->shift(first), deleted)
    }
  }
  xs->safeDelete(index < 0 ? index + length : index)
}

tsconfig.json

{
  "compilerOptions": {
    "target": "ESNext",
    "strict": true,
  }
}