Practical Guide to Fp-ts: P4 — Arrays, Semigroups, Monoid

Introduction

Welcome to the fourth post on learning fp-ts the practical way. This series is dedicated to learning fp-ts and functional programming with no mathematical knowledge required.

In this post, I'm going to introduce how to use arrays effectively in fp-ts and how we can use semigroups and monoids to easily compose operations over arrays.

Array Basics

The most basic data structure you'll encounter on a daily basis is the Array data type. Arrays are useful to us because we can use them to perform computations by traversing over its elements. But before we jump into traversals with fp-ts, lets start with the basics by going back to loops.

For Loop

The traditional way of traversing over an array is to use a loop with an index variable, i.

const foo = [1, 2, 3]

let sum = 0
for (let i = 0; i < foo.length; i++) {
  sum += foo[i]
}
console.log(sum) // 6

For-of Loop

Instead of using an index counter, we can also directly iterate over the elements using the for-of syntax.

const foo = [1, 2, 3]

let sum = 0
for (const x of foo) {
  sum += x
}
console.log(sum) // 6

Functional Loops

But lets be real, all the cool kids these days are using the fancy functional map, reduce, filter syntax.

const foo = [1, 2, 3, 4, 5]

const sum = foo
  .map((x) => x - 1)
  .filter((x) => x % 2 === 0)
  .reduce((prev, next) => prev + next, 0)
console.log(sum) // 6

In fp-ts, we can do the same thing but with different syntax.

import * as A from 'fp-ts/lib/Array'
import { pipe } from 'fp-ts/lib/function'

const foo = [1, 2, 3, 4, 5]

const sum = pipe(
  A.array.map(foo, (x) => x - 1),
  A.filter((x) => x % 2 === 0),
  A.reduce(0, (prev, next) => prev + next),
)
console.log(sum) // 6

However, this just looks like syntactic sugar, so let us digress. Why should you install fp-ts when you can just use the regular array methods?

Array Extensions

If you come from the Python world, you'll be shocked to find that Typescript doesn't have built in array methods like zip. You should use fp-ts because it gives you the additional batteries you need to do fancy array manipulation.

import * as A from 'fp-ts/lib/Array'
import { pipe } from 'fp-ts/lib/function'

const foo = [1, 2, 3]
const bar = ['a', 'b', 'c']

const zipped = pipe(foo, A.zip(bar))
console.log(zipped) // [[1, 'a], [2, 'b], [3, 'c']]

The cool thing about this is that it preserves the type-safety of the elements in the array. The type of zipped is Array<[number, string]> rather than Array<Array<number | string>>. In other words, zipped is an array of tuples.

If you find this cool, then you might also be interested in the unzip, partition, and flatten operators.

Array Type Safety

One of things that's not type-safe safe in Typescript is array access and mutations. If you're coming from the Java world, then you should know in Typescript, there is no such thing as an IndexOutOfBounds exception. Accessing an element that is out of bounds returns undefined. You can also create undefined behaviour when you mutate an array outside of its bounds.

const foo = [1, 2, 3]

const x: number = foo[4] // no compile error
foo[5] = 2 // no runtime error
console.log(foo) // [1, 2, 3, undefined, undefined, 2]

Now just by looking at this code snippet, I can assure you, that we are indeed living in scary times. However, there is light at the end of tunnel; type safe array access is coming in Typescript 4.1. The term they use is for it pedantic index signatures.

In the meantime, in our never ending search for purity, we must look to fp-ts to save us from the gallows of undefined.

Lookup

If we want to be type safe when accessing an element in an array, we should use the lookup function. It takes two parameters, an index and an array and returns an Option type.

import * as A from 'fp-ts/lib/Array'
import { pipe } from 'fp-ts/lib/function'

pipe([1, 2, 3], A.lookup(1)) // { _tag: 'Some', value: 2 }
pipe([1, 2, 3], A.lookup(3)) // { _tag: 'None' }

Because it returns an Option, we are forced to deal with the possible none case.

However, this can become cumbersome when we are interested in the first element, otherwise known as the head of the array and when we know the array is not empty.

const foo = [1, 2, 3]
if (foo.length > 0) {
  // We don't want an Option since we know it will always be some
  const firstElement = A.head(foo) // { _tag: 'Some', value: 1 }
}

To deal with this, fp-ts has another type known as the NonEmptyArray. The NonEmptyArray type also has a head operator but it return the underlying value instead of an Option.

Examine the type definition to see the difference.

// Array
export declare const head: <A>(as: A[]) => Option<A>

// NonEmptyArray
export declare const head: <A>(nea: NonEmptyArray<A>) => A

Now we must answer the question: how do we go from Array<A> 🠂 NonEmptyArray<A>.

In our example, we can do this by replacing our if statement with a isNonEmpty guard.

// Fp-ts Type guard
export declare const isNonEmpty: <A>(as: A[]) => as is NonEmptyArray<A>

import * as A from 'fp-ts/lib/Array'
import * as NEA from 'fp-ts/lib/NonEmptyArray'

const foo = [1, 2, 3]
if (A.isNonEmpty(foo)) {
  const firstElement = NEA.head(foo) // 1
}

Voilà, we have the value instead of an Option.

In short, if you really care about type safety, use lookup to access elements in your array.

Be sure to also checkout the insertAt and updateAt operators.

Partitioning Non-Homogenous Arrays

In Typescript, we can have two types of arrays: homogenous and non-homogeneous. In a homogenous array, every element must be of the same type. Elements in a non-homogenous arrays can take on union of types.

// Homogenous
const foo = [1, 2, 3] // number[]

// Non Homogenous
const bar = [1, '2', 3] // (string | number)[]

When we iterate over a non-homogenous array, we are limited by what is common between the union of types.

type Foo = {
  readonly _tag: 'Foo'
  readonly f: () => number
}

type Bar = {
  readonly _tag: 'Bar'
  readonly g: () => number
}

declare const arr: Array<Foo | Bar>
for (const a of arr) {
  console.log(a._tag) // Ok
  console.log(a.f()) // Error: not assignable to Bar
  console.log(a.g()) // Error: not assignable to Foo
}

But, lets say we had this problem domain. We want to sum all elements belonging to Foo using f() and multiply it by the maximum of all elements belong to Bar using g().

Trivially, we can compute it imperatively.

function compute(arr: Array<Foo | Bar>) {
  let sum = 0
  let max = Number.NEGATIVE_INFINITY

  arr.forEach((a) => {
    switch (a._tag) {
      case 'Foo':
        sum += a.f()
        break
      case 'Bar':
        max = Math.max(max, a.g())
        break
    }
  })

  return sum * max
}

This is great. It gets the job done. And its not too verbose. How does it look in fp-ts?

import * as A from 'fp-ts/lib/Array'
import * as NEA from 'fp-ts/lib/NonEmptyArray'
import * as O from 'fp-ts/lib/Option'
import * as E from 'fp-ts/lib/Either'
import { pipe } from 'fp-ts/lib/function'

const compute = (arr: Array<Foo | Bar>) =>
  pipe(
    A.array.partitionMap(arr, (a) =>
      a._tag === 'Foo' ? E.left(a) : E.right(a),
    ),
    ({ left: foos, right: bars }) => {
      const sum = A.array.reduce(foos, 0, (prev, foo) => prev + foo.f())
      const max = A.array.reduce(bars, Number.NEGATIVE_INFINITY, (max, bar) =>
        Math.max(max, bar.g()),
      )

      return sum * max
    },
  )

You probably think this looks ugly and verbose. And you would be are correct. But however, isn't functional code suppose to be more concise? The problem with this is, we have to write a lot what I called plumbing code to reduce the sum and the max to a single numeric value.

To clean this up, we need to learn about Semigroups and Monoids.

Semigroups

A Semigroup is a type that is able to take two homogenous values and produce a single homogenous value. Semigroups must implement a function known as concat. An example of a concat operation is addition: given two numbers, we can concatenate them together by addition to produce a single number.

The type definition for a Semigroup looks like this.¹

export interface Semigroup<A> {
  readonly concat: (x: A, y: A) => A
}

This is useful to us because we can use it to generalize the addition operation prev + foo.f() from our reduce function.

Also important to note is, when implementing a Semigroup, we don't need to literally concat both elements x and y, we just need to produce a number. For example you could have a semigroup that always returns one.

const onlyOne: Semigroup<number> = {
  concat: (_, _) => 1,
}

What this also means is that we can implement a semigroup for finding the max of our bars.

const semigroupMax: Semigroup<number> = {
  concat: (x, y) => Math.max(x, y),
}

Or more concisely.

const semigroupMax: Semigroup<number> = {
  concat: Math.max,
}

Going back to our original problem domain, we can see how this paradigm can be useful for sum and maximum operations. However, we have a problem. The function takes two elements. What happens if our input array is empty?

To solve this problem we need to learn about Monoids.

Monoids

Monoids are an extension of Semigroup but it also includes the empty or default element.

In fp-ts, this is what the type definition looks like

export interface Monoid<A> extends Semigroup<A> {
  readonly empty: A
} 

If you go back to the reduce functions we wrote previously, we specified 0 as the empty element for addition and Number.NEGATIVE_INFINITY for Math.max. We would plug in the same values for a monoid.

For example, we can create a monoidMax by extending semigroupMax.

import { Monoid } from 'fp-ts/lib/Monoid'

const monoidMax: Monoid<number> = {
  concat: semigroupMax.concat,
  empty: Number.NEGATIVE_INFINITY,
}

Now we can replace our reduce functions with foldMap functions alleviating the responsibility of the reduction to the monoid.²

import { Monoid, monoidSum } from 'fp-ts/lib/Monoid'

const compute = (arr: Array<Foo | Bar>) =>
  pipe(
    A.array.partitionMap(arr, (a) =>
      a._tag === 'Foo' ? E.left(a) : E.right(a),
    ),
    ({ left: foos, right: bars }) => {
      const sum = A.array.foldMap(monoidSum)(foos, (foo) => foo.f())
      const max = A.array.foldMap(monoidMax)(bars, (bar) => bar.g())

      return sum * max
    }, 
  ) 

Hey, that's nice! Its less verbose and its clear what the function does now. Let's extend our usecase and have a condition where we want to swap the operations. That is, Math.max on foos and sum on bars.

With monoids this is very easy, we can create a higher order function and dynamically create the behaviour we want.

const compute = (fooMonoid: Monoid<number>, barMonoid: Monoid<number>) => (
  arr: Array<Foo | Bar>,
) =>
  pipe(
    A.array.partitionMap(arr, (a) =>
      a._tag === 'Foo' ? E.left(a) : E.right(a),
    ),
    ({ left: foos, right: bars }) => {
      const sum = A.array.foldMap(fooMonoid)(foos, (foo) => foo.f())
      const max = A.array.foldMap(barMonoid)(bars, (bar) => bar.g())

      return sum * max
    },
  )

declare const i: number
if (i % 2 === 0) {
  compute(monoidSum, monoidMax)
} else {
  compute(monoidMax, monoidSum)
}

Whereas imperatively it might look something like this.

function compute(arr: Array<Foo | Bar>, invert: boolean) {
  let sum = 0
  let max = Number.NEGATIVE_INFINITY

  arr.forEach((a) => {
    switch (a._tag) {
      case 'Foo':
        if (invert) {
          max = Math.max(max, a.f())
        } else {
          sum += a.f()
        }
        break
      case 'Bar':
        if (invert) {
          sum += a.g()
        } else {
          max = Math.max(max, a.g())
        }
        break
    }
  })

  return sum * max
}

From this you can understand, the imperative approach gets much worse as the cyclomatic complexity increases. Whereas in functional programming, because it so composable, allows use to easily change behaviours of our program without creating additional complexity in the code.

That's all for this post. As always, if you like this kind of content, please give me a follow on Twitter and send me a DM or email for what you want to see next!

1. Actually Semigroup inherits from Magma which is generalization of Semigroup. The difference Semigroups operations are associative. See the fp-ts definitions for Semigroup and Magma. ↩

2. Note I imported monoidSum which is just a monoid for addition. ↩