TypeScript のタグ付きユニオンで再帰データ型を扱えるのか分からなくなったので試しにリストを実装

list.ts

// TypeScript のタグ付きユニオンで再帰データ型を扱えるのか分からなくなったので試しにリストを実装
// 結論、扱えます

// Haskell でいうところの data List a = Empty | Cons a (List a)
interface Empty {
  kind: "Empty"
}

interface Cons<T> {
  kind: "Cons"
  head: T
  tail: List<T> // ここに List<T> を指定できる。OK牧場でした
}

export type List<T> = Empty | Cons<T>

// リストを生成する
const outList1: List<number> = {
  kind: "Cons",
  head: 1,
  tail: {
    kind: "Cons",
    head: 2,
    tail: {
      kind: "Cons",
      head: 3,
      tail: { kind: "Empty" }
    }
  }
}

// ...値を生成しづらいので値コンストラクタを用意
export function Empty(): Empty {
  return { kind: "Empty" }
}

export function Cons<T>(head: T, tail: List<T>): Cons<T> {
  return { kind: "Cons", head, tail }
}

// リストっぽくなったぞ
const ourList2: List<number> = Cons(1, Cons(2, Cons(3, Empty())))

// List<T> への map 関数を実装
type map = <T, U>(f: (a: T) => U, xs: List<T>) => List<U>

export const map: map = (f, xs) => {
  switch (xs.kind) {
    case "Empty":
      return Empty()
    case "Cons":
      return Cons(f(xs.head), map(f, xs.tail))
    default:
      assertNever(xs)
  }
}

export function assertNever(_: never): never {
  throw new Error()
}

console.log(map(i => i * 2, ourList2))

// output:
// {
//   kind: 'Cons',
//   head: 2,
//   tail: {
//     kind: 'Cons',
//     head: 4,
//     tail: { kind: 'Cons', head: 6, tail: [Object] }
//   }
// }
//
// 想定どおり