Automasean

What the Functor

Similarly to any complex mathematical concept, it is important to understand the building blocks of the concepts behind the functional programming paradigm.

Disclaimers:

  • This post will by no means cover an exhaustive list of FP building blocks.
  • The purpose of this post is not to express these concepts with 100% mathematical or grammatical accuracy. The purpose is to build a quick reference to get the point across for my future self 😉
  • I will use TypeScript for concrete definitions, Elm for stand-alone type annotations and the Elm REPL for quick expression evaluation.

Semigroup

Wikipedia's mathematical definition of a semigroup:

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

The binary operation of a semigroup is most often denoted multiplicatively: x·y, or simply xy, denotes the result of applying the semigroup operation to the ordered pair (x, y). Associativity is formally expressed as that (x·y)·z = x·(y·z) for all x, y and z in the semigroup.

In programming, a semigroup can be thought of as a structure or data type with an append function used to combine elements in the structure. This append function must have the associative property (order of application cannot matter). One could say a list of integers under addition is a semigroup.

Let's explore a practical example using code to make things a bit more clear.

interface Semigroup<T> {
  concat(x: T, y: T): T;
}


const everySemigroup: Semigroup<boolean> = {
  concat: (x, y) => x && y
};

You can easily define fold/reduce for a semigroup because you know there is an append function.

const fold = <T>(
    semigroup: Semigroup<T>, 
    initialValue: T, 
    array: Array<T>
  ): T =>
    array.reduce(semigroup.concat, initialValue);

Which ultimately makes it easy to construct valuable utilities.

const every = 
  (booleanArray: Array<boolean>): boolean =>
    fold(everySemigroup, true, booleanArray);

Monoid

Wikipedia's mathematical definition of a monoid:

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are semigroups with identity.

That's pretty much it. A monoid is a semigroup with an identity value. Think of an identity value as a neutral element. If you commutatively combine the identity value with an element in your structure it will always return the same element.

Note: This is different than the identity function.

Identity Element vs Identity Function

The identity function takes an argument and returns the exact same value that passed to it. The identity function itself is a monoid. Check out the following Elm type definition for the identity function.

identity : a -> a

This does a great job of showcasing the power of Elm's type annotations. Any elm function with the signature a -> a is the identity function since a is generic and the only way to ensure you're adhering to the type signature is to conclude that the function will pass back whatever is handed to it.

> identity a = a
<function> : a -> a


> identity 1
1 : number


> identity "return me"
"return me" : String


> identity [1.1, 2.2]
[1.1,2.2] : List Float

Here's the TypeScript implementation of the identity function.

const identity = <T>(foo: T) => foo;

While the identity function is an important tool, the identity element is what we're referring to in our definition of a monoid.

  • Real numbers under the addition operation have an identity value of 0
  • Real numbers under multiplication have an identity value of 1
  • A boolean under the logical AND operation has an identity value of true
  • A boolean under the logical OR operation has an identity value of false

All monoids are semigroups, however, not all semigroups are monoids.

Functor

Wikipedia's mathematical definition of a functor:

In mathematics, specifically category theory, a functor is a map between categories.

In FP a functor can be thought of as a collection-like structure with a map operation.

Consider the Elm definition for List.map:

map : (a -> b) -> List a -> List b

In addition to lists, the following are all examples of functors.

  • promise
  • array
  • maybe
  • either