Skip to content

Functional Programming

Functional Design Patterns - Missing Values

When working in software, a common problem that we run into is what should we do if we can't get a value or compute an answer.

For example, let's say that you go to the library to checkout the latest book from Nathalia Holt, but when you search for it, you realize that they don't have any copies in stock.

How do you handle the absence of value? From an Object Oriented Programming (OOP), you might be able to leverage a reasonable default or the Null Object Pattern. Another approach would be to return to always return a list and if there are no values, then the list would be empty.

No matter the choice you make, we need some way to model the lack of a value. Tony Hoare referred to null as his billion dollar mistake as its inclusion in languages have created countless bugs and errors.

In most functional languages, the idea of null doesn't exist, so how do they handle missing values?

Revisiting Functions

In a previous post, we mention that a function is a mapping between two sets such that every element on the left (first set) is mapped to a single element on the right (the second set). So what happens when we have a mapping that's not a function?

In these cases, we have two solutions to choose from:

  1. Restrict the function input to only be values that can be mapped (e.g., restrict the domain)
  2. Expand the possible values that the function can map to (e.g., expand the range)

When refactoring a mapping, I tend to stick with option 1 because if we can prevent bad data from being created or passed in, that's less error handling that needs to be written and it becomes simpler to reason about. However, there are plenty of times where our type system (or business rules) can't enforce the valid inputs.

Number Math

Let's say that we're working on a "word calculator" where the user can enter a phrase like "one thousand twelve" and it returns "1012" as output. If we think about our input set (domain) and outputs, we would have the following (mapping from string to number).

Mapping from string to number

The issue is that we can't guarantee that the strings the user gives us would represent a number (for example, how would you convert "platypus" to a number?)

Since we can't restrict the input, we have to expand the output. So let's update our output to be number | 'invalid'

Mapping from string to number or 'invalid'

With this change, anytime we call convertToNumber, we'll need to add some handling on what to do if the output is invalid.

Here's some pseudocode of what this mapping could look like

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
type WordCalculatorResult = number | 'invalid'

function convertToNumber(phrase:string): WorldCalculatorResult {
    if (phrase === 'one') return 1;
    if (phrase === 'two') return 2;
    // ... other logic
    return 'invalid';
}

console.log(convertToNumber('one')); // prints "1";
console.log(convertToNumber('kumquats')) // prints invalid

Leaky Context

So far, so good as we have a function that converts words to numbers. Let's now say that we want to square a number. Writing such a function is straightforward.

1
2
3
function square (x:number): number {
    return x*x;
}

With both convertToNumber and square defined, let's try to combine these together:

Compilation error when combining convertToNumber and Square

This doesn't work because convertToNumber can return invalid which there's no way for the square function to work with that. Due to this limitation, we could rewrite the code to check for invalid before calling square.

1
2
3
4
5
const result = convertToNumber('one');

if (result !== 'invalid') {
    console.log(square(result));
}

This approach will work, but the downside is that we need to add error handling logic in our pipeline now. If this was the only place where it's being used, then it's not too bad. However, if we were using convertToNumber in multiple places, then we have to remember to add this error handling logic. In fact, we would have almost the same if check everywhere.

Let's take a look at a different way of solving this problem by using the Maybe type.

Introducing the Maybe Type

In our original approach, we already had a type called WordCalculatorResult for the computation. Instead of it being a number or invalid, we could instead create a new type, called Maybe that looks like the following:

1
type Maybe<T> = { label: 'some', value: T } | { label: 'none' }

By leveraging generics and tagged unions, we have a way to represent a missing value for any type. With this new definition, we can rewrite the convertToNumber function to use the Maybe type.

1
2
3
4
5
6
function convertToNumber(phrase:string): Maybe<number> {
    if (phrase === 'one') return {label:'some', value:1};
    if (phrase === 'two') return {label:'some', value:2};
    // other logic
    return {label:'none'};
}

I don't know about you, but typing out {label:'some'} is going to get tiring, so let's create two helper functions, some and none that handle putting the right label if we have a value or not.

1
2
3
4
5
6
7
function some<T>(value:T): Maybe<T> {
    return {label:'some', value};
}

function none<T>(): Maybe<T> {
    return {label:'none'};
}

Which allows us to replace all of the {label:'some', value:x} with some(x) and {label:'none'} with none().

1
2
3
4
5
6
function convertToNumber(phrase:string): Maybe<number> {
    if (phrase === 'one') return some(1);
    if (phrase === 'two') return some(2);
    // other logic
    return none();
}

Now that convertToNumber returns a Maybe, our pipeline would look like the following:

1
2
3
4
5
const result = convertToNumber('one');

if (result.label === 'some') { // checking if we're a Some type
    console.log(square(result.value));
}

Introducing Transformations With Map

Now the problem we're wanting to solve is to get rid of having to do an if check on some in order to call the square function. Given that we're wanting to transform our number into a different number, we can write another function, called map that takes two parameters: the Maybe we want transformed and the function that knows how to transform it. Let's take a look at how to write such a function.

1
2
3
4
5
6
7
function map<T,U>(m:Maybe<T>, f:(t:T)=>U): Maybe<U> {
    if (m.label === 'some') { // Is Maybe a Some?
        const transformedValue = f(m.value); // Grab the value and transform it by calling function f
        return some(transformedValue) // return a new Maybe with the transformed value
    }
    return none(); // Return none since there's no value to transform
}

With map implemented, let's update our code to use it!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
const convertResult = convertToNumber('one'); // 
const transformedResult = map(convertResult, square);

if (transformedResult.label === 'some') { // checking if we're a Some type
    console.log(transformedResult.value);
}

/* The above could be simplified as the following
const result = map(convertToNumber('one'), square);
if (result.label === 'some') {
  console.log(result.value)
}
*/

Thanks to map and Maybe, we're able to write two pure functions (convertToNumber and square), glue them together, and delegate our error handling to one spot (instead of having to sprinkle this throughout the codebase).

Calling Side Affects Using Tee

With the addition of map, we've now simplified our if check to only call console.log now (instead of calling the square function then console.log). If we wanted to truly get rid of this if statement, then we need a way to invoke the console.log as a side effect. We don't want to combine console.log into square because square is business rules and we don't want to add side effect logic to our business rules.

Similar to what we did for map, let's add a new function, called tee, that takes in three arguments: a Maybe, a function to call if the Maybe has a value, and then a function to call if Maybe doesn't have a value.

Let's take a look at what an implementation would look like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/*
 Inputs:
    m: A Maybe to work with
    ifSome: A function that takes in a T (which comes from the Maybe) and returns void
    ifNone: A function that takes no inputs and returns void
 Outputs:
    Returns m so that we can continue chaining calls
*/
function tee<T>(m:Maybe<T>, ifSome:(t:T)=>void, ifNone:()=>void): Maybe<T> {
    if (m.label === 'some') {
        ifSome(m.value);
    } else {
        ifNone();
    }
    return m;
}

With tee implemented, we can update our pipeline to take advantage of it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
const convertResult = convertToNumber('one'); // 
const transformedResult = map(convertResult, square);

const ifSome = (t:number) => console.log(`Result is ${t}`);
const ifNone = () => console.log('Failed to calculate result.');

tee(transformedResult, ifSome, ifNone);

// if we wanted to get rid of the temp values, we could do the following
// const result = tee(map(convertToNumber('one'), square)), ifSome, ifNone);

Cleaning Up by using an Object

We've now centralized the if logic to the functions that work on Maybes which is helpful, but as we're already seeing, the code can be hard to parse as you need to read from the outside in (which is very Clojure or Scheme in nature).

Instead of building up functions this way, we can instead create a TypeScript class and use a fluent interface pattern by doing the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
export class Maybe<T>
{
  private constructor(private readonly value:T|undefined=undefined){}
  map<U>(f:(t:T)=>U): Maybe<U> {
    return this.value !== undefined ? Maybe.some(f(this.value)) : Maybe.none();
  }
  tee(ifSome:(t:T)=>void, ifNone:()=>void) {
    if (this.value !== undefined) {
      ifSome(this.value);
    } else {
      ifNone();
    }
    return this;
  }
  static some<T>(value:T): Maybe<T> {
    return new Maybe(value);
  }
  static none<T>(): Maybe<T> {
    return new Maybe();
  }
}
// Defined in index.ts
function convertToNumber(phrase:string): Maybe<number> {
    if (phrase === 'one') return Maybe.some(1);
    if (phrase === 'two') return Maybe.some(2);
    // other logic
    return Maybe.none();
}

function square(x:number): number {
    return x*x;
}

// By using the fluent interface pattern, we can chain methods together and have this code read
// more naturally
convertToNumber("one")
  .map(square)
  .tee(
    (v)=> `Answer is ${v}`, 
    () => "Unable to calculate result"
  );

Wrapping Up

When writing software, a common problem we run into is what to do when we can't calculate a value or a result. In this post, we looked at techniques to restrict the function's input or expand their output to handle scenarios. From there, we looked into a type called Maybe and how it can represent the absence of value, but still provide a way to remove having to explicitly write error handling code by consolidating the checks into a map call. Lastly, we look into taking the various functions that we wrote and combine them into a formal Maybe class that allows us to leverage a fluent interface and chain our interactions together.

Functional Design Patterns - Reduce and Monoids

When learning about a loops, a common exercise is to take an array of elements and calculate some value based on them. For example, let's say that we have an array of numbers and we want to find their sum. One approach would be the following:

1
2
3
4
5
const values = [1, 2, 3, 4, 5];
let total = 0;
for (const val in values) {
    total += val;
}

This code works and we'll get the right answer, however, there's a pattern sitting here. If you find yourself writing code that has this shape (some initial value and some logic in the loop), then you have a reducer in disguise.

Let's convert this code to use the reduce function instead.

1
2
const values = [1, 2, 3, 4, 5];
const total = values.reduce((acc, curr) => acc + curr, 0);

The reduce function takes two parameters, the reducer and the initial value. For the initial value, this is the value that the result should be if the array is empty. Since we're adding numbers together, zero makes the most sense.

The reducer, on the other hand, says that if you give me the accumulated result so far (called acc in the example) and an element from the array (called curr in the above example), what's the new accumulation?

Reduce is an extremely powerful tool (in fact, I give a presentation where we rewrite some of C#'s LINQ operators as reduce).

But there's another pattern sitting here. If you find that the initial value and elements of the array have the same type, you most likely have a monoid.

Intro to Monoids

The concept of Monoid comes from the field of category theory where a Monoid contains three things

  1. A set of values (you can think about this as a type)
  2. Some binary operation (e.g., a function that takes two inputs and returns a single output of said type)
  3. Some identity element such that if you pass the id to the binary operation, you get the other element back.

There's a lot of theory sitting here, so let's put it in more concrete terms.

If we have a Monoid over the a type A, then the following must be true:

1
2
3
4
5
6
7
8
function operation<A>(x:A, y:A): A 
{
    // logic for operation
}
const identity: A = // some value of type A
operation(x, identity) === operation(identity, x) === x

operation(x, operation(y, z)) === operation(operation(x, y), z)

Here's how we would define such a thing in TypeScript.

1
2
3
4
export interface Monoid<A>{
    operation: (x:A, y:A)=> A;
    identity:A;
}

Exploring Total

With more theory in place, let's apply it to our running total from before. It turns out that addition forms a Monoid over positive numbers with the following:

1
2
3
4
const additionOverNumber: Monoid<number> = {
    identity: 0,
    operation: (a:number, b:number) => a+b;
}

Wait a minute... This looks like what the reduce function needed from before!

In the case where we have a Monoid, we have a way of reducing an array to a single value for free because of the properties that Monoid gives us.

Exploring Booleans

Thankfully, we're not limited to just numbers. For example, let's take a look at booleans with the && and || operators.

In the case of &&, that's our operation, so now we need to find the identity element. In other words, what value must id be if the following statements are true?

1
2
3
const id: boolean = ...
id && true === true
id && false === false

Since id has to be a boolean, the answer is true. Therefore, we can define our Monoid like so

1
2
3
4
const AndOverBoolean: Monoid<boolean> = {
    identity: true,
    operation: (a:boolean, b:boolean) => a && b
}

With this monoid defined, let's put it to use. Let's say that we wanted to check if every number in a list is even. We could write the following:

1
2
3
const values = [1, 2, 3, 4, 5];

const areAllEven = values.map(x=>x%2===0).reduce(AndOverBoolean.operation, AndOverBoolean.identity);

Huh, that looks an awful lot like how we could have used every.

1
2
const values = [1, 2, 3, 4, 5];
const areAllEven = values.every(x=>x%2===0);

Let's take a look at the || monoid now. We have the operation, but we now we need to find the identity. In other words, what value must id be if the following statements are true?

1
2
3
const id: boolean = ...;
id || true === true
id || false === false

Since id has to be a boolean, the answer is false. Therefore, we can define our monoid as such.

1
2
3
4
const OrOverBoolean: Monoid<boolean> = {
    identity: false,
    operation: (x:boolean, y:boolean) => x || y
}

With this monoid defined, let's put it to use. Let's say that we wanted to check if some number in a list is even. We could write the following:

1
2
3
const values = [1, 2, 3, 4, 5];

const areAllEven = values.map(x=>x%2===0).reduce(OrOverBoolean.operation, OrOverBoolean.identity);

Similar to the AndOverBoolean, this looks very similar to the code we would have written if we had leveraged some.

1
2
3
const values = [1, 2, 3, 4, 5];

const isAnyEven = values.some(x => x%2 === 0);

Wrapping Up

When working with arrays of items, it's common to need to reduce the list down to a single element. You can start with a for loop and then refactor to using the reduce function. If the types are all the same, then it's likely that you also have a monoid, which can give you stronger guarantees about your code.

Exploring Map with Property Based Thinking

When thinking about software, it's natural to think about the things that it can do (its features like generating reports or adding an item to a cart).

But what about the properties that those actions have? Those things that are always true?

In this post, let's take a look at a fundamental tool of functional programming, the map function.

All the code examples in this post will be using TypeScript, but the lessons hold for other languages with Map (or Select if you're coming from .NET).

Examining Map

In JavaScript/TypeScript, map is a function for arrays that allow us to transform an array of values into an array of different values.

For example, let's say that we have an array of names and we want to ensure that each name is capitalized, we can write the following:

1
2
3
4
5
6
const capitalize = (name:string): string => {
  return n[0].toUpperCase() + n.substring(1);
}
const names = ["alice","bob","charlotte"];

const properNames = names.map(capitalize);

In our example, as long as we have a pure function that takes a string and returns a new type, then map will work.

What Does Map Guarantee?

Map is a cool function because it has a lot of properties that we get for free.

  1. Maintains Length - If you call map on an array of 3 elements, then you'll get a new array with 3 elements. If you call map on an empty array, you'll get an empty array.

  2. Maintains Type - If you call map on array of type T with a function that goes from T to U, then every element in the new array is of type U.

  3. Maintains Order - If you call map on array with one function, then call map with a function that "undoes" the original map, then you end up with the original array.

Writing Property Based Tests

To prove these properties, we can write a set of unit tests. However, it would be hard to write a single test that that covers a single property.

Most tests are example based in the sense that for a specific input, we get a specific output. Property based tests, on the other hand, uses random data and ensures that a property holds for all inputs. If it finds an input where the property fails, the test fails and you know which input caused the issue.

Most languages have a tool for writing property-based tests, so we'll be using fast-check for writing property based tests and jest for our test runner

Checking Length Property

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import fc from "fast-check";

describe("map", () => {
  it("maintains length", () => {
    // This is known as the identify function
    // as it returns whatever input it received
    const identity = <T>(a: T): T => a;

    // Fast Check assert that the following holds for all arrays of integers
    fc.assert(
      // data is the array of numbers
      fc.property(fc.array(fc.integer()), (data): void => {
        // We call the map function with the identify function
        const result = data.map(identity);

        // We make sure that our result has the same length
        expect(result).toHaveLength(data.length);
      })
    );
  });

If we run this test, we'll end up passing. But what is the value of data?

By adding a console.log in the test, we'll see the following values printed when we run the test (there are quite a few, so we'll examine the first few).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
console.log
    [
       2125251991,  1334674146,
      -1531633149,   332890473,
       1313556939,   907640912,
        887735692, -1979633703,
       -259341001,  2015321027
    ]

  console.log
    [ 1307879257 ]

  console.log
    []

  # quite a few more...

Checking Type Property

We've proven that the length property is being followed, so let's look at how we can ensure that result has the right type.

To keep things simple, we're going to start with a string[] and map them to their lengths, yielding number[].

If map is working, then the result should be all numbers.

We can leverage typeof to check the type of each element in the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// An additional test in the describe block

it("maintains type", () => {
  const getLength = (s:string)=>s.length;
  fc.assert(
    // asserting with an array of strings
    fc.property(fc.array(fc.string()), (data): void => {
      // mapping to lengths of strings
      const result = data.map(getLength);

      // checking that all values are numbers
      const isAllValid = result.every((x) => typeof x === "number");
      expect(isAllValid).toBeTruthy();
    })
  );
});

Like before, we can add a console.log to the test to see what strings are being generated

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
console.log
  [ 'ptpJTR`G4', 's >xmpXI', 'H++%;a3Y', 'OFD|+X8', 'gp' ]

console.log
  [ 'Rq', '', 'V&+)Zy2VD8' ]


console.log
  [ 'o%}', '$o', 'w7C', 'O+!e', 'NS$:4\\9aq', 'xPbb}=F7h', 'z' ]

console.log
  [ '' ]

console.log
  [ 'apply', '' ]

console.log
  []
## And many more entries...

Checking Order Property

For our third property, we need to ensure that the order of the array is being maintained.

To make this happen, we can use our identity function from before and check that our result is the same as the input. If so, then we know that the order is being maintained.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
it("maintains order", () => {
  const identity = <T>(a: T) => a;

  fc.assert(
    fc.property(fc.array(fc.string()), (data): void => {
      const result = data.map(identity);

      expect(result).toEqual(data);
    })
  );
});

And with that, we've verified that our third property holds!

So What, Why Properties?

When I think about the code I write, I'm thinking about the way it works, the way it should work, and the ways it shouldn't work. I find example based tests to help understand a business flow because of it's concrete values while property based tests help me understand the general guarantees of the code.

I find that once I start thinking in properties, my code became cleaner because there's logic that I no longer had to write. In our map example, we don't have to write checks for if we have null or undefined because map always returns an array (empty in the worse case). There's also no need to write error handling because as long as the mapping function is pure, map will always return an array.

For those looking to learn more about functional programming, you'll find that properties help describe the higher level constructs (functors, monoids, and monads) and what to look for.

Finding properties can be a challenge, however, Scott Wlaschin (of FSharpForFunAndProfit) has a great post talking about design patterns that I've found to be immensely helpful.