One of these things you eventually learn in Haskell is (Indexed) Type Families. The basic concept of a Type Family is the idea that you can have functions at the type level, I/E a function that accepts a type as parameter, and returns a type as a result.
-- Totally not valid Haskell, but this is the idea
g :: Type -> Type
g Int = Bool
g _ = Char
In the example above, if we call g String
, we would get the type Char
as a result. Even though we would really want to do this directly (the Dependent Haskell guys are working on it), there is a specific syntax and bunch of extensions to be able to do:
type family G a where
G Int = Bool
G a = Char
This does pretty much the same, except that it's not actually a function, but a type. You write:
myVariable :: G Int -- this is Bool
myVariable = True
But, with this, we have the basics of type-level functions. We write a function G
which accepts a type as parameter, and returns another type as result. And we implement this type-level function by enumerating the different cases in pattern-matching fashion.
Well, you can do this in Typescript too!
Conditional types in Typescript
On Typescript 2.8, the team introduced Conditional Types, with the syntax:
T extends U ? X : Y
The idea is that if T
is assignable to U
(T
is U
or a subtype of U
), then the resulting type will be X
, otherwise Y
. This is all we need to construct type families: a type-level if
. If this is not clear enough for you, let's work out the magic:
Deconstructing pattern matching
Pattern matching is a powerful set of syntactic sugar that allows you to write very little code to mean a lot. It is intended to implement deep testing of the structure and values of a given data, and it does it by trying to match the data with potential candidates:
case value of
Just [x1, 5, x3] -> do_something
Just (x:xs) -> do_something_else
Just _ -> do_this_instead
Nothing -> do_a_different_thing
The code above is very obvious on what it does, but it's also very deep. Let's go over the details:
The first branch states if value
is a Just
, and that Just
contains a list of exactly three elements, and the second element is 5, then go and name the first element x1
and the third element x3
, and call do_something
.
The second branch states if we haven't matched the first branch, and value
is a Just
, and that Just
contains a list with at least an element, then go and name the first element of the list x
, and the rest of the list xs
, and call do_something_else
.
The third branch states if we haven't matched neither the first or the second branch, and value
is a Just
, then call do_this_instead
.
The fourth branch states if we haven't matched neither the first, or the second, or the third branch, and value
is a Nothing
, then call do_a_different_thing
.
All of this in this small case
statement. But this tells us how can we reconstruct our case
statement into plain old conditionals. We try to match on the pattern by constructing a condition that represents the pattern, and assigning bindings to the variables that have been bound by the pattern match:
const value: null | Array<number> = ...
if(value !== null && value.length === 3 && value[1] === 5) {
// branch for Just [x1:5:x3]
const x1 = value[0];
const x3 = value[2];
do_something()
} else if (value !== null && value.length > 0) {
// branch for Just (x:xs)
const x = value[0];
const xs = value.slice(1);
do_something_else()
} else if (value !== null) {
// branch for Just _
do_this_instead()
} else if (value === null) {
// branch for Nothing
do_a_different_thing()
}
As you can see, the TypeScript version is significantly more verbose, but that doesn't stop us from using the same principle to construct pattern matching wherever we need.
Type-level pattern matching in Typescript: constructing Type Families
Now that we know how to construct conditional types, and how to transform pattern matching into a bunch of conditionals, we are in a position to construct Type Families. Let's go back to our previous example:
type family G a where
G Int = Bool
G a = Char
So if a
is an Int
, the resulting type is a Bool
, otherwise, the resulting type is a Char
. Let's do this in Typescript:
type G<A> = A extends number ? boolean : string;
I had to substitute number
for Int
and string
for Char
because Typescript doesn't have these types, but you get the general idea: for each branch in the Type Family, construct a nested conditional type, like:
type G<A> = A extends Type1 ? Result1 :
A extends Type2 ? Result2 :
...
A extends Typen ? Resultn :
Otherwise;
Wherever we need a type wildcard, we can substitute with A extends any
that will match every type, and if we need to check multiple type variables, we can nest conditionals, although this tends to get hairy sooner than later.
Conclusion
With this, we have one of the most important elements of type-level computation: the type-level function. Brace yourselves for type-level Turing-completeness abuses!