Practical Guide to Fp-ts: P4 — Arrays, Semigroups, Monoid
Tags: functional, fpts, typescript
Published: 2020-09-15 01:58:08

---
layout: 'post'
title: "Practical Guide to Fp-ts: P4 — Arrays, Semigroups, Monoid"
description: "Learn how to use Fp-ts practically. Introduces the functional array, semigroups, and monoid."
tags: fp, fpts, typescript
canonical_url: https://rlee.dev/practical-guide-to-fp-ts-part-4
series: Practical Guide to Fp‑ts
published: true
---

## 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](https://en.wikipedia.org/wiki/Semigroup) and [monoids](https://en.wikipedia.org/wiki/Monoid) 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`.

```ts
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.

```ts
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.

```ts
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.

```ts
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`](https://docs.python.org/3.9/library/functions.html#zip). You should use fp-ts because it gives you the additional batteries you need to do fancy array manipulation.

```ts
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](https://en.wikipedia.org/wiki/Tuple)_.

If you find this cool, then you might also be interested in the [unzip](https://gcanti.github.io/fp-ts/modules/Array.ts.html#unzip), [partition](https://gcanti.github.io/fp-ts/modules/Array.ts.html#partition), and [flatten](https://gcanti.github.io/fp-ts/modules/Array.ts.html#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. 

```ts
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](https://github.com/microsoft/TypeScript/issues/40124). The term they use is for it [_pedantic index signatures_](https://github.com/microsoft/TypeScript/pull/39560).

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

![undefined goes brrr](https://rlee.dev/assets/blog/practical-guide-to-fp-ts/undefined-goes-brrr.png)

### Lookup

If we want to be type safe when accessing an element in an array, we should use the [lookup](https://gcanti.github.io/fp-ts/modules/Array.ts.html#lookup) function. It takes two parameters, an index and an array and returns an `Option` type.

```ts
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.

```ts
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`](https://gcanti.github.io/fp-ts/modules/NonEmptyArray.ts.html). 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.

```ts
// 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`](https://gcanti.github.io/fp-ts/modules/Array.ts.html#isnonempty) guard.

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

```ts
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](https://gcanti.github.io/fp-ts/modules/Array.ts.html#insertat) and [updateAt](https://gcanti.github.io/fp-ts/modules/Array.ts.html#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.

```ts
// 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.

```ts
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.

```ts
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?

```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.[^1]

```ts
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.

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

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

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

Or more concisely.

```ts
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

```ts
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`.

```ts
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.[^2]

```ts
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](https://en.wikipedia.org/wiki/Higher-order_function) and dynamically create the behaviour we want. 

```ts
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.

```ts
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](https://en.wikipedia.org/wiki/Cyclomatic_complexity#:~:text=Cyclomatic%20complexity%20is%20a%20software,in%201976.) 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](https://twitter.com/ryanleecode) 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](https://en.wikipedia.org/wiki/Associative_property). See the fp-ts definitions for [Semigroup](https://gcanti.github.io/fp-ts/modules/Semigroup.ts.html#semigroup-interface) and [Magma](https://gcanti.github.io/fp-ts/modules/Magma.ts.html).

[^2]: Note I imported `monoidSum` which is just a monoid for addition.