Swift, Algebraically: Zero and One
Part 2 of 3
Previous: Sum Types, Product Types, Exponential Types
The previous post introduced the idea of how we can understand programming from a mathematical point of view. It showed how enumerations are sum types, structures are product types, and functions are exponential types. In this post we look at how zero and one are defined in this theory.
A set with one value is called a singleton set. (Not that kind of singleton!) Since we're thinking about types as sets of values, what would be the type that corresponds to the singleton set? We saw that each case of an enumeration is a single value, so one way to represent the singleton set could be with an enumeration that has a single case.
enum Singleton {
case one
}How would we use this? Let's say we have a function which has a Singleton parameter.
func getData(_ singleton: Singleton) -> Data { ... }There is only one thing we can do when we call this function.
let data = getData(.one)But if we can only pass one value, why pass anything at all? The function parameter is meant to provide some kind of information to the function. Passing a Singleton provides no information because it always has the same value.
There are other ways to represent a singleton set. Recall that structures, classes and tuples are composite types which hold other types. But what if they hold no other types? We could define a structure without properties.
struct Singleton {}Now to call getData we could pass it an instance of the Singleton type.
let data = getData(Singleton())Notice that, similar to an enumeration with only one case, a structure with no properties provides no information. It always has the same value. We can also define Singleton using an empty tuple like this.
typealias Singleton = ()And we would pass it to getData like this.
let data = getData(Singleton)But since we are now dealing with a type alias we can also do this.
let data = getData(())Wait a minute – this looks like Void. In fact, this is exactly how Void is defined!
typealias Void = ()Swift already has the type which represents the singleton set, it's Void.
All these different ways of defining the singleton set are equivalent. But you can see that an empty tuple is the most concise and unambiguous. The two other methods are ambiguous because we can define other enumerations with a single case or other structures with no properties. It wouldn't be clear why we should prefer one over the other. But there is only one way to specify an empty tuple. We can give it different type aliases, but the aliases would still refer to the same type. The Void type, or the empty tuple, is a set with a single value. We can call it the unit type.
What does the unit type mean when we use it in function types? In Swift we can define functions without specifying a parameter or a return type. Functions do require a return type, but if you don't specify one, the return type is assumed to be Void. Parameters are not required and there is no implicit parameter if you don't specify one. But we already saw that if the parameter is a unit type, it doesn't provide any information anyways. From a mathematical point of view, we can think of functions with no parameters as having a Void parameter.
Now let's look at the size of functions with Void. For any function with Void as its parameter, the size will be the size of the return type. Remember that if the parameter type has m values and the return type has n values, the number of possible functions for that function type is n^m. The size of Void is 1, so the total size is n^1 = n. All this means is that for any function type with a Void parameter, it will have one function for each value of the return type. For example, there are only two possible functions that go from Void to Bool. One returns true and the other returns false.
What if the function type has a Void result type? In that case it only has one function, 1^m = 1. We can specify different function types going from a particular type to Void, such as Number→Void or String→Void, but they are all the same function because they all return Void. They map all values to Void. We can see this in the fact that we can encapsulate all these functions in a single generic function.
func unit<T>(value: T) -> Void {
return ()
}But wait a minute, there are a ton of different functions that return Void but do different things. They can't all be the same. They do different things, but from a mathematical point of view, they are the same function. Math doesn't "do" anything. If a function "does" something, it is not math. The non-math part of a function is called a side effect. Typical side effects are printing to the console, writing to disk, and making a call to a backend service. If you see a function which returns Void, it more than likely performs a side effect. Why else would you call such a function?
There are other ways in which a function may not be mathematical. A function could throw an exception, or it could never return because it has entered an endless loop. It could also use global state or a randomly generated value in its calculation of the result value. A strictly mathematical function is called a pure function. A pure function has no side effects and it always returns the same value for a given input value. This requirement is necessary for a function to represent a specific mapping between the values in the parameter type to the values of the return type. If the mapping changes every time the function is called, there is no way to reason mathematically about it.
All the types we have discussed so far have at least one item in their set of values. What would it mean for a type to have an empty set of values? Swift actually does have this type. It's called Never and it consists of an enumeration with no cases.
enum Never { }A function type which returns Never has no values, 0^m = 0. There are no functions with a Never result type. A function can't have a Never result type because every element in a domain must map to something. This seems odd at first glance because we can define functions which return Never. In fact, the Swift standard library includes functions such as fatalError which do that. fatalError never returns because it stops the execution of the program. This is the purpose of the Never type in Swift. It indicates to the compiler that for whatever reason, the function never returns. But notice that stopping the program is a side effect. fatalError is not a pure function, so we can't include it in a mathematical description of the language. We have to qualify our original conclusion – there are no pure functions with a Never result type.
A function type with a Never parameter has a single value, n^0 = 1. There is only one function with a Never parameter. A function with an empty domain is still technically a function even though there are no elements to map from. It satisfies the definition of a function. Maybe we could have stated the definition of a function as, "if there is an element in the domain, it must be mapped to a single element in the codomain." We can also express this idea with a generic function.
func never<T>(value: Never) -> T { }We don't have to return anything because the body of the function will never be executed and the compiler knows this. We can define functions with a Never parameter, but they can't be called because there is no way to create a Never value. This doesn't seem practical, but this kind of function is useful in certain contexts where a function is required but we know it will never actually be needed.
There is one case that is a bit ambiguous. Technically, we could have a function that goes from Never to Never since then the domain doesn't have any elements to map. It satisfies the definition of a function, but on the other hand it is inconsistent with the exponential rule which says that there are no functions with an empty return type. We'll let the mathematicians figure this one out.