Learner’s Guide to Functional Programming#0: Sum Types, Booleans and Naturals in Javascript

After writing the first article of the Learner’s Guide to Functional Programming series yesterday on implementing functional lists, I have realized I may have jumped in too fast. Hence, I decided to move one step back and start by introducing Sum Types, and building Booleans and Naturals using them. We have already implicitly introduced them in the previous article, but this article will make it explicit and clear.

Learner’s Guide to Functional Programming#1: Implementing Lists in JavaScript

Below is the definition from Wikipedia.

In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. Only one of the types can be in use at any one time, and a tag field explicitly indicates which one is in use. It can be thought of as a type that has several “cases”, each of which should be handled correctly when that type is manipulated.

So, the rules are simple. We have several variants denoted with different tags. You may remember we had the following definition for the List type in the first article.

type List = { variant: "nil" } | { variant: "cons", elem: any, rest: List }

Let’s forget about that for now and focus on a simpler example, booleans. Booleans have two values, true and false, each one can be defined with a variant. Below is the typescript definition for boolean.

type Boolean = { variant: "True" } | { variant: "False" }

Visual Representation of Bool Variants

These variants do not hold any extra information in addition to their tags. Using only tag-checks, we can implement classical logic operators not, and, or, xor as shown below.

const True = () => ({ variant: "True" });
const False = () => ({ variant: "False" });

const not = (b) => (
    b.variant === "True" ? False() : True()
)

const and = (b1, b2) => (
    b1.variant === "True" ? b2 : False()
)

const or = (b1, b2) => (
    b1.variant === "True" ? True() : b2
)

const xor = (b1, b2) => (
    b1.variant === "True" ? not(b2) : b2
)

You may realize I am kind of cheating here. I am using if-expressions and strict equality for checking variants. I do this because in JavaScript land, I don’t have any kind of primitive expression for pattern matching on types as other more functional languages such as OCaml, Haskell, Racket or Rust have.

Our little library on the other hand is very useful at this point, we can compute any valid logical formula in classical logic with these 6 functions we have.

Another useful operator on booleans is If-Then-Else expression as we have already seen. We can implement is as below.

const ifThenElse = (b, t, e) => (
    b.variant === "True" ? t : e
)

This expression will return t if b is True, else e , same way with the if-expression we have been using.

You may have realized booleans are kind of boring. They are very simple, for the very reason I talked at the beginning, none of the variants have any type of data. Let’s stir things up a bit with natural numbers.

Peano Arithmetic

So, coming from the mainstream imperative programming side, we tend to take primitive types for granted. Booleans, integers, strings are just given to us, we usually don’t have to work for them. That’s why I was very surprised and excited when one of our first tasks was to encode and implement functions on natural numbers as part of a functional programming class. This encoding is called Peano Numbers. Let’s see if I can get you excited about them like me.

type Nat = { variant: "O" } | { variant: "S", n: Nat }

We have two variants, the first one is “O” that represents 0, and the second one is “S”, also short for successor, that represents n+1 for some number n. So, let’s have the constructors for each variant.

Visual Representation of Nat Variants

const O = () => ({ variant: "O" });
const S = (n) => ({ variant: "S", succ: n });

These functions allow us to express all naturals starting from 0.

0: O()
1: S(O())
2: S(S(O())

In simpler terms, the number of nested S calls correspond to our natural number.

Okay, we can have numbers, but can we do useful operations with them? Indeed we can, let’s look at our operators.

// Checking if we have 0 or some successor.
const isZero = (n) => (
    n.variant === "O"
)

// As we are talking about naturals, the lowest number is 0, 
// so predecessor of 0 is also 0. For S variant, we just look
// what the number is successor of.
// We have the relation succ(n) = pred(n+1)
const pred = (n) => (
    isZero(n) ? n : n.succ
)


// We combines the facts that n + m = (n - 1) + (m + 1)
// and 0 + m = m. We decrease n as we increase m until n = 0.
const add = (n, m) => (
    isZero(n) ? m : add(pred(n), S(m))
)

// We combine the facts that n - m = (n - 1) - (m - 1)
// and n - 0 = n. We decrease both numbers until m is 0.
const sub = (n, m) => (
    isZero(m) ? n : sub(pred(n), pred(m))
)

// We combine the facts that n * m = m + (n-1) * m
// and 0 * n = 0. We decrease n until n = 0.
const mul = (n, m) => (
    isZero(n) ? O() : add(m, mul(pred(n), m))
)

If you are careful, you might have realized the rather hidden recursive structure here. We almost always use the O variant as our base case, and we recurse over S variant. In add, sub, and mul, we use two relations, one for our base case on O, and one for our recursive case S.

Of course, without comparison operators, we couldn’t talk about numbers. Let’s add comparisons.

// Two numbers are equal in two cases.
// 1. Both of them are equal to 0
// 2. None of them are equal to 0, and their predecessors are equal
const eq = (n, m) => (
    (isZero(n) && isZero(m))
    || (!isZero(n) && !isZero(m) && eq(pred(n), pred(m)))
)

// n is less than or equal to m in two cases.
// 1. n is equal to 0
// 2. m is not equal to 0, and (n - 1) <= (m - 1)
const lte = (n, m) => (
    isZero(n) || (!isZero(m) && lte(pred(n), pred(m)))
)

// n is less than m when
// n != m, and n <= m.
const lt = (n, m) => (
    (!eq(n, m)) && lte(n, m)
)

// For greater than, we just use the contrapositive relations.
const gt = (n, m) => (
    !lte(n, m)
)
// For greater than or equals,
// we just use the contrapositive relations.
const gte = (n, m) => (
    !lt(n, m)
)

Conclusion

I am hoping that this article has shown the convenience of sum types(or tagged unions or discriminated unions, pick according to your taste) in expressing various types of data. I would suggest you read the first article on implementing lists again after reading this one. Lastly, I really hope it showed you that there are alternatives to our data models. Binary encoded integers are not the only possible encoding for numbers, as random access arrays are not the only encoding for lists. Every encoding has their own pros and cons, and explicitly thinking in terms of datatypes, variants, and encodings is very helpful in designing software models for real world.