Types and Type Systems

A type function is evaluated at compile-time, not while the program runs.

Programming

Predicting When a Type Function Runs

Most of the functions you have written probably run while your program is doing its ordinary work. You pass in a value, the function computes something, and you get a value back. A type function is different in two important ways: the thing that flows through it is a type rather than a value, and its work is finished at a different point in the life of a program. Before reading the rest of this article, try to make a prediction about the timing.

What do you think happens?

When is a type function evaluated?

While the program is running, each time the function is called
While the program is being compiled, before it runs
Only when the user provides input to the program
Only after the program has finished executing

Reveal answer

Answer:

While the program is being compiled, before it runs

A type function is evaluated at compile-time, not while the program is running. The work of deciding the type happens before the program executes, so the result is already settled when the program starts its ordinary work.

From Values to Types

Think about a function you already know. You pass in a number, a string, or a list, and you get back another value. The values are the material the function works on. A type function changes the kind of material that flows through it. Instead of working with values, it works with types. The idea is that the type itself becomes the thing a function manipulates.

The chapter section that introduces this idea presents type functions as a building block that programmers and library implementers can use. As you read about them, keep three questions in mind: what goes into a type function, what comes out, and when the work happens. Those three questions organize everything that follows.

What a Type Function Is

Definition

A type function is a function that takes a type as its argument, returns a type, or does both. It is evaluated at compile-time, not while the program is running.

Key point

The most important word in the definition is compile-time. That word is what separates a type function from the ordinary functions most learners are used to. A type function does its work while the program is being compiled, so its result is already settled by the time the program starts doing its ordinary work.

The three parts to track are the input, the output, and the evaluation step. The input is a type or something that a type function can use to produce a type. The output is a result that the type function produces. The evaluation step is the moment the function does its work, and for a type function that moment is compile-time. Because the input of many type functions is a type, the work is about the structure or properties of that type rather than about any particular runtime data.

Type functions are also available as ready-made tools. The source notes that the standard library provides a variety of type functions, so you do not have to invent them yourself. Their purpose is to help library implementers and programmers write code that takes advantage of the language, the standard library, and code in general. In this sense, type functions are less a single trick and more a shared vocabulary. When a library offers a type function, it gives you a dependable way to ask a question about types or to produce a type, and you can build on that answer in your own code.

Tracing a Type Through a Function

A useful way to understand a type function is to follow a type through it one step at a time. Picture a type entering the function as its argument. The function is evaluated at compile-time and produces a result. The diagram below shows that path: the type goes in, the function does its compile-time work, and a result comes out before the program runs.

What happens to a type as it enters a type function, and what comes out the other side during compilation?

Worked example

Following one type through a type function

Trace what happens when a type is given to a type function as its argument, and identify when the result becomes available.

1
Supply the input
The type is passed to the type function as its argument. The input is a type, so the work concerns that type's structure or properties.
2
Evaluate at compile-time
The compiler evaluates the type function while the program is being compiled. Nothing about this step waits for the program to run.
3
Collect the result
The function produces its result during compilation, so the outcome is fixed before execution begins.
4
Start the program
When the program starts doing its ordinary work, the result from the type function is already settled and can be relied upon.

Result

The type enters the function as an argument, the function is evaluated during compilation, and the result is already settled when the program begins running.

Two Shapes of Type Function

The definition names two possibilities separated by the word or. A type function may accept a type and return something else, or it may accept something and return a type. The source describes both shapes as belonging to one concept, so treat them as two variations of the same idea rather than two unrelated tools. What separates them is which side of the arrow the type sits on: on the input side, or on the output side.

How do the two kinds of type function differ in which side of the arrow the type sits on?

Question	Type takes a type as argument	Type returns a type
Where does the type sit?	On the input side of the function	On the output side of the function
What flows in?	A type	Something other than the result type
What comes out?	Something other than necessarily a type	A type
When is it evaluated?	At compile-time	At compile-time

Both shapes belong to one concept and are evaluated at compile-time.

When the Work Happens

Timing is what makes type functions distinctive. A type function is evaluated while the program is being compiled, not while it is running. The timeline below places the type function within the two stages. It runs during compilation, and it is absent from the stage in which the program carries out its ordinary work.

At which stage of building and running a program does the type function execute, and which stage is it absent from?

Misconceptions About Type Function Timing

Common mistake
Assuming a type function runs each time the program executes a line that uses it
Why it fails
A type function is evaluated at compile-time, so its work is not repeated during ordinary program execution.
Do this instead
Think of the type function as settling its result during compilation, before the program starts.
Common mistake
Treating a type function like an ordinary function that accepts and returns values
Why it fails
A type function changes the kind of thing that flows through it. It works with types instead of values.
Do this instead
Ask what goes in and what comes out: a type may be the input, the output, or both.
Common mistake
Believing the two shapes of type function are unrelated tools
Why it fails
The source describes both shapes as variations of one concept, separated by the word or.
Do this instead
Identify which side of the arrow the type sits on, then apply the same compile-time understanding to both.
Common mistake
Thinking the result depends on particular runtime data
Why it fails
Because the input is often a type, the work concerns the structure or properties of that type rather than any particular runtime data.
Do this instead
Focus on the type that was passed in, not on values that appear while the program runs.

Practice Classifying Type Functions

EASY

A type function is described as taking a type as its argument and producing a value that is not a type. Explain which side of the arrow the type sits on, and state at what stage of building and running a program the function is evaluated.

Hints

Recall the two shapes: a type may sit on the input side or the output side.
Recall the word that defines when the work happens.

Your attempt (not saved)

MEDIUM

Without looking back, describe in your own words the path a type takes through a type function, from input to result, and say when the result becomes available.