total and partial functions

2020-09-03

 | 

~4 min read

 | 

798 words

Today I learned about total functions, as well as their antipode, partial functions.

According to NIST, a total function is ”[a] function which is defined for all inputs of the right type, that is, for all of a domain.” A partial function is the opposite, i.e. a function which is not defined for all inputs.

I came across this concept in the context of programming - specifically a linting program that would review applications for adherence to a rule set that functions be written as total functions. Partial functions are generally unnecessary and depending on the language (or the linting rules) may prevent your program from compiling.

You almost never have an excuse for writing a partial function! Partial Functions | Haskell

Inspecting Functions

To help understand why partial functions are unnecessary, as well as solidify these concepts, I wanted to understand how you might rewrite partial functions into total functions.

Two examples that kept coming up were:

  1. Head - a function that returns the first element of a list.
  2. Reciprocal - a function that returns the reciprocal of a number.

Looking first at head, we can see how it might fail:

function head(array: string[]) {
  return array[0]
}
const b = head([])
b.toUpperCase()

If the array is empty, this will pass the type checking, however, it will explode at run time as we try to invoke toUpperCase on undefined.1

On the other hand, reciprocal is interesting in that the built-in javascript implementation of dividing by zero is already total.

function reciprocal(x: number) {
  return 1 / x
}
const y = reciprocal(0)

Whereas other languages, like Python, throw an error when dividing by zero:

>>> 1/0
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: integer division or modulo by zero

Javascript handles the case:

console.log(1 / 0, typeof 1 / 0) // Infinity NaN
console.log(0 / 0) // NaN NaN

(Note: Nan, which stands for “Not-a-Number”, is part of the ECMAScript Number type2)

Refactoring Partial Functions

So, if head is a partial function, how do we refactor it since “You almost never have an excuse for writing a partial function!“?

To help me think about this, I looked at how fp-ts implemented it. fp-ts is a popular library for using functional paradigms with Typescript.

totalHead.ts
// https://github.com/gcanti/fp-ts/blob/5d0126587d36977540962b6580ae95df988234e4/src/ReadonlyArray.ts#L454-L456
export function head<A>(as: ReadonlyArray<A>): Option<A> {
  return isEmpty(as) ? none : some(as[0])
}

// https://github.com/gcanti/fp-ts/blob/5d0126587d36977540962b6580ae95df988234e4/src/ReadonlyArray.ts#L346-L348
export function isEmpty<A>(as: ReadonlyArray<A>): boolean {
  return as.length === 0
}

// https://github.com/gcanti/fp-ts/blob/5d0126587d36977540962b6580ae95df988234e4/src/Option.ts#L109
export const some = <A>(a: A): Option<A> => ({ _tag: "Some", value: a })

// https://github.com/gcanti/fp-ts/blob/5d0126587d36977540962b6580ae95df988234e4/src/Option.ts#L103
export const none: Option<never> = { _tag: "None" }

To allow for all lists, even empty ones, fp-ts checks first the length of the array using isSome. If the list is empty, it returns none. If it’s defined, then it returns some of the first list.3

The most interesting part for me is what Option is. From the Option.ts file:

/**
 * ```ts
 * type Option<A> = None | Some<A>
 * ```
 *
 * `Option<A>` is a container for an optional value of type `A`. If the value of type `A` is present, the `Option<A>` is
 * an instance of `Some<A>`, containing the present value of type `A`. If the value is absent, the `Option<A>` is an
 * instance of `None`.
 *
 * An option could be looked at as a collection or foldable structure with either one or zero elements.
 * Another way to look at `Option` is: it represents the effect of a possibly failing computation.
 *
 * @since 2.0.0
 */

Using this:

import { head } from "fp-ts/Array"

console.log(head([])) // {_tag: None}
console.log(head([1])) // {_tag: some, value: 1}

Conclusion

So, a total function is one that is defined for inputs of an accepted type and it’s possible to refactor partial functions to be total.

We don’t need to write them all for ourselves though. Tools like fp-ts provide guardrails to make it easy. On the other hand, this whole investigation started because as a team we were looking at linting plugins for ESLint which has both a plugin for functional programming and more specifically total functions.

Footnotes

  • 1 “Explode” seems to be common vernacular for runtime errors due to insufficiently or inaccurately typed programs.
  • 2 Making sense of NaN is not always intuitive. I found Kiro Risk’s article “NaN and typeof” helpful for steering me in the right direction.
  • 3 As I’m not well steeped in functional programming I also found it quite interesting that fp-ts wraps return values in an object with a _tag property.

Hi there and thanks for reading! My name's Stephen. I live in Chicago with my wife, Kate, and dog, Finn. Want more? See about and get in touch!