First class mapped (folded, appended, traversed, etc.) types

masaeedu commented 6 years ago

Search Terms

Mapped types, dependent typing, higher kinded types, type families

Suggestion

TypeScript currently has baked in support for mapped types, with special syntax for transforming type level maps and type level lists (tuples). Borrowing an example from #26063:

type Box<T> = { value: T }
type Boxified<T> = { [P in keyof T]: Box<T[P]> }

type A = [string, number]
type MappedA = Boxified<A> // => [Box<string>, Box<number>]

type B = { foo: string, bar: number }
type MappedB = Boxified<B> // => { foo: Box<string>, bar: Box<number> }

The logic for when a type is treated as a mappable type unto itself, and when it is simply treated as an heterogeneous map for the purposes of type mapping is built out of various edge cases.

The code above is analogous at the value level to writing the following:

const box = t => ({ value: t })
const boxified = t => MAP{ [p in t]: box(t[p]) } // Special syntax baked into the language

const a = ["hello", 1]
const mappedA = boxified(a) // => [{ value: "hello" }, { value: 1 }]

const b = { foo: "hello", bar: 1 }
const mappedB = boxified(b) // => { foo: { value: "hello" }, bar: { value: 1 } }

The MAP{ [p in t]: box(t[p]) } thing above stands out as something of an oddity; you don't usually see a "map operator" built directly into a language. Given a way to inductively break down and reconstruct data, users are perfectly capable of defining a map function for each type of data themselves:

// There are no linked lists in JS, so let's graft an algebra onto arrays
// for breaking them down and building them up recursively
const nil = []
const cons = x => xs => [x, ...xs]
const match = ({ nil, cons }) => xs =>
  xs.length === 0 ? nil : cons(xs[0])(xs.slice(1))

// How to map over lists (ignoring the baked in `.map` operation from the prototype or a sec)
const map = f =>
  match({
    nil: nil,
    cons: x => xs => cons(f(x))(map(f)(xs))
  })

console.log(map(x => x * 2)([1, 2, 2, 3]))
// => [2, 4, 4, 6]

Similarly, for maps:

// Again, need to graft on an algebra for deconstructing and reconstructing objects
const empty = {}
const withKey = k => v => o => ({ [k]: v, ...o })
const match = ({ empty, withKey }) => o => {
  const keys = Object.keys(o)

  if (keys.length === 0) return empty

  const [k, ...ks] = keys
  const { [k]: v, ...o_ } = o
  return withKey(k)(v)(o_)
}

// How to map over objects
const map = f =>
  match({
    empty: empty,
    withKey: k => v => o => withKey(k)(f(v))(map(f)(o))
  })

console.log(map(x => x * 2)({ foo: 1, bar: 2, baz: 2, quux: 3 }))
// => { foo: 2, bar: 4, baz: 4, quux: 6 }

The important thing to notice here is that once we have a way to break down and reconstruct the data recursively, we don't need any language-level features to express mapping over the data; both implementations of map require only the ability to define and apply functions, and for such functions to themselves be valid arguments and results (i.e. the features found in a minimal lambda calculus).

Moving back to the type level, we can promote our value level implementation of map to a type constructor in pseudo-TypeScript:

type Nil = []
type Cons<X, R> = [X, ...R]

type Map<F, A> =
  A extends Nil ? Nil :
  A extends Cons<infer X, infer R> ? Cons<F<X>, Map<F, R>> :
  never

// NB: we need a type level bottom that inhabits all kinds (corresponding
// to a type error), never is not the right answer here

type Box<V> = { value: V }
type A = [number, string]
type MappedA = Map<Box, A> // => [{ value: number }, { value: string }]

Using the ability to abstract over type level functions and to apply them, i.e. utilizing the lambda calculus at the type level, the user is able to define "mapped types" without the need for this to be implemented in the language.

In fact, mapped types (i.e. structure preserving transformations), are just one useful tool for massaging types. It would similarly be useful for the user to be able to fold down a type level list into a type level union (using the binary | type constructor), or to fold down a type level list of object types into their intersection (using the binary & type constructor).

AFAICT the primary missing features here are HKTs (#1213) and recursive type constructors (#6230), but it's possible there are other features related to spread types, conditional types, and infer that are missing. This provides good motivation for implementing these features in a sound way; it would allow powerful abstractions like mapped types to be implemented and extended in libraries rather than in the core language.

Checklist

My suggestion meets these guidelines:

[x] This wouldn't be a breaking change in existing TypeScript / JavaScript code
[x] This wouldn't change the runtime behavior of existing JavaScript code
[x] This could be implemented without emitting different JS based on the types of the expressions
[x] This isn't a runtime feature (e.g. new expression-level syntax)

jack-williams commented 6 years ago

What does the type-level version of map look like for objects under this proposal?

masaeedu commented 6 years ago

@jack-williams Similar to the value-level map for objects:

type Empty = {}
type WithKey<K, V, O> = { [k: K]: V, ...O }

type Map<F, O> =
  O extends WithKey<infer K, infer V, infer O> ? WithKey<K, F<V>, Map<F, O>> :
  O extends Empty ? Empty :
  never

microsoft / TypeScript