Classifying Functions by Sets and by Types

Same inputs, different headaches, and one compiler that refuses to be your therapist!

When teaching advanced topics on programming languages and computing theory students often want to clarify the differences between the usages of the term function in different contexts. A function can be described in two ways. In set thinking you specify a domain and a codomain, then say the function assigns to every input in the domain exactly one output in the codomain. In type thinking you specify the input type and the output type of a computation, then require that any implementation respect the rules carried by those types. The two views often lead to different solutions once you try to build real systems.

When we say that a set or a type classifies a function, we are referring to how functions can be described or categorized based on their input and output. The notion of classification depends on whether we are in the context of set theory (sets) or type theory (types). Let me explain this concept in both contexts.