Total Avoidance of Partiality

Posted on September 22, 2017

TL;DR

Functions map values from their domain to values in their co-domain. When a function provides a mapping for every domain value, then it is total, otherwise it is partial. Partial functions are bad and total functions are good.

You can often make a partial function total by expanding its co-domain or shrinking its domain.

Functions, Domains, and Co-domains

Remember when you learnt about functions in high school mathematics? Neither do I. Oh well, let’s just learn it again.

A function maps inputs to outputs.

f(x) = x + 1      // where x is an integer
g(x,y) = x * y    // where x and y are both integers

f is a function that maps an integer to another integer by adding one to it. g is a function that maps two integers to another integer by multiplying them together.

The set of values that a function can take as inputs is called its domain and the set of values that a function can return as outputs is called its co-domain. The domain of our f function is the set of all integers and it’s co-domain is also the set of all integers. The domain for the g function is the set of all pairs of integers, (x,y), and it’s co-domain is the set of all integers.

Unfortunately, in practice that’s not quite the whole story, especially in programmer-land. Often, the functions we encounter, and write, end up only mapping some of the values in their domain to values in their co-domain.

Partial to Lying

Looking at our f and g functions above it is hard to imagine a way to “break” them. There is no integer that we could pass to f such that there was no way for the expression x + 1 to evaluate to another integer.

This can’t be said of most functions we write when programming, especially in languages that support throwing exceptions, because anything can break at any time. Consider the following C# code, which calculates the average per-item cost from a collection of items in a shopping cart.

public decimal CalculateAverageItemCost(Cart cart) =>
  cart.Items.Sum(i => i.Price) / cart.Items.Length;

The domain of the CalculateAverageItemCost function is all the inhabitants of the Cart type. It’s co-domain is the set of values that populate the C# decimal type. If we give this function a Cart, we get back a decimal. At least that’s what the signature says.

But what about when Cart.Items is an empty collection?

That’s right, a DivideByZeroExcpetion is thrown. Well, that signature isn’t worth the internet it’s written on. I’m sure you’ll agree that throwing an exception is hardly the same thing as returning a decimal!

This irresponsible behaviour makes CalculateAverageItemCost a partial function. And the problem with partial functions is that they are lies. I was promised a decimal and I didn’t get one. How can I ever trust a function again?

When some values in a function’s domain are not mapped to values in its co-domain, then it is a partial function.

Getting back to Total Trust

There is nothing more sacred than the relationship between a programmer and their functions. We must mend this rift, lest we doom ourselves to a broken existence, full of pain and suffering.

Let’s start with a healthy dose of honesty. There is no function we could write that returns a decimal output for every possible Cart input. It doesn’t exist, because a cart with no items in it doesn’t have a average per-item cost. We simply can’t satisfy this signature.

This means we’ll need to change the signature to something we can satisfy. A promise we can actually keep, if you will. Our goal is to be able to map every input passed to CalcualteAverageItemCost to some output. We can achive this by expanding the output space (co-domain) or shrinking the input space (domain).

Both of these approaches will allow us to map every input to an output, making our CalculateAverageItemCost a total function.

When every value in a function’s domain is mapped to a value in its co-domain, then it is a total function.

Expanding the Co-domain

If we can’t guarantee that we can return a decimal output, what type of output could we guarantee? Well, we’d need a type that could model the presence of a decimal average (for when the cart has items), and the absence of an average (for when the cart is empty). Let’s call this type Maybe and use it to rewrite our CalculateAverageItemCost function.

public Maybe<decimal> CalculateAverageItemCost(
  Cart cart
) =>
  cart.Items.Length > 0
    ? Just(cart.Items.Sum(i => i.Price) / cart.Items.Length)
    : Empty();

Just and Empty are both functions that return a value of type Maybe. Just puts a decimal “inside” the Maybe structure while Empty, as the name suggests, represents the absence of a value.

With these changes we’ve removed the possibility of throwing an exception by returning Empty instead. Of course, in C#, both Cart and Cart.Items could be null, in which case we’d be throwing exceptions again, but I’ve ignored those cases for the sake of a clear example.

The point is that we have turned our partial function into a total function by conceptually expanding our co-domain from decimal to Maybe.

A partial function can be turned into a total function by expanding it’s co-domain.

Shrinking the Domain

We could also leave the function returning a decimal, and instead constrain the input (domain).

In this case we’d need an input type that gives us a guarantee that the cart could never be empty. Let’s call this type NonEmptyCart and say that the NonEmptyCart API makes it impossible to construct a cart that has no items.

With this new type under out belt we could rewrite out function once again.

public decimal CalculateAverageItemCost(
  NonEmptyCart cart
) =>
  cart.Items.Sum(i => i.Price) / cart.Items.Length;

Here we’ve removed the possibility of the exception by limiting the inputs the function can take. This means we can use the function in less places, since NonEmptyCart is a more constrained type than Cart, but this is a small price to pay for being sure that you can use it safely.

A partial function can be turned into a total function by shrinking it’s domain.