How to use type-level functions to create static types, dynamically?

Question

In TypeScript, there are type-level functions that allow creating new types based on given literal types/specifications (see Mapped Types, Conditional Types, etc.).

For instance, here is such a function, let say provided by a lib author:

type FromSpec<S> = { 
  [K in keyof S]: S[K] extends "foo" ? ExampleType : never 
};

Its purpose is, given a specification S in the form of a map of string keys and arbitrary literals, it creates a new type in the form of a map with the same set of keys and with values transformed. If a the value is the literal "foo" then it becomes the type ExampleType, otherwise the value is rejected by transforming it into the bottom type never.

Then, an end-user can make use of this function to create new types following the above explanation:

type Example = FromSpec<{some_key: "foo", another_key: "bar"}>
//           = {some_key: ExampleType, another_key: never} 

It's noteworthy that the lib author doesn't know about what exact type a given end-user may want, and thus provides him with a function to create the ones he needs. On the other hand, the end-user can create an infinite set of new types as long as he complies with the function's capabilities.

You can play around this simple example, here.

---

The question is about how this kind of "dynamism" is expressible in other typed languages (e.g., ReasonML/OCaml, Scala, Haskell). Or how, as an end-user, to create new types, at compile-time, by using type-level functions, provided by a lib author (as one would usually do at runtime with value-level functions)?

It's important to note that the question is not about which language is better, etc. It's about finding the most straightforward and explicit way to express such capabilities. Here we saw an example in TypeScript, but is there any more natural way in any other language?

Answer 1

Given Scala is one of the tagged languages, here is a solution in Dotty (aka. Scala 3). Take this with a grain of salt, since Dotty is still under development. Tested with Dotty version 0.24.0-RC1, here is a Scastie that proves this actually compiles.

Scala doesn't have the same sort of built-in type machinery as TypeScript for manipulating records. Not to fear, we can roll our own!

import deriving._

// A field is literally just a tuple of field name and value
type Field[K, V] = (K, V)

// This just helps type-inference infer singleton types in the right places
def field[K <: String with Singleton, V <: Singleton](
  label: K,
  value: V
): Field[K, V] = label -> value

// Here is an example of some records
val myRec1 = ()
val myRec2 = field("key1", "foo") *: field("key2", "foo") *: () 
val myRec3 =
  field("key1", 1) *: field("key2", "foo") *: field("key3", "hello world") *: ()

Then, FromSpec can be implemented using a match-type. The never type in TypeScript is called Nothing in Scala/Dotty.

// Could be defined to be useful - `trait` is just an easy way to bring a new type in 
trait ExampleType
val exampleValue = new ExampleType {}

type FromSpec[S <: Tuple] <: Tuple = S match {
  case Field[k, "foo"] *: rest => Field[k, ExampleType] *: FromSpec[rest]
  case Field[k, v] *: rest => Field[k, Nothing] *: FromSpec[rest]
  case Unit => Unit
}

Finally, let's use FromSpec:

def myRec1Spec: FromSpec[myRec1.type] = ()
def myRec2Spec: FromSpec[myRec2.type] =
  field("key1", exampleValue) *: field("key2", exampleValue) *: () 
def myRec3Spec: FromSpec[myRec3.type] = ??? // no non-diverging implementation