Monad Say What? (Part 1)

Ian Hofmann-Hicks — Fri, 09 Nov 2018 19:08:10 +0000

With all the buzz of late, Functional Programming this and Composition that, terms like Functor and Monad may have crossed your feeds and left you wondering, "what the heck are these people even talking about?". With such strange names and possibly even more foreign explanations that require a deep understanding of Algebra (the abstract kind) and Category Theory, it may be hard to see how these types of constructs fit in our comfy, day-to-day JavaScript code.

In this series we'll explore, from a JavaScript programmers point of view, what a Monad is and how they can be used to great effect in our everyday code. We will be focusing mostly on the usage of these types and not the theory behind them.

So for instance, instead of working to understand the following definition:

A Monad is a Monoid in the Category of Endofunctors

We will work toward understanding a more practical definition:

A Monad is a data type that allows for sequential application of its "effects" or "embellishments" while mapping its underlying data.

Now, while the second definition still may not be clear right now, I think we can agree that working to understanding those words and the meaning derived from how they all fit together seems a bit more approachable.

Understanding the first definition is critical when we venture out and create our own types. Although if you are anything like me, I like to get my hands dirty and build an understanding by first having a play with things and applying the theory when I have a good intuition of how use them. There are a slew of types already implemented in the wild that we can blissfully play with...without understanding the Maths behind them.

These posts assume an understanding of not only the JavaScript language, but how "currying", "partial application" and "function composition" is accomplished in Javascript. If you feel a bit fuzzy on these topics, there are many resources available on the webs to get you sorted out.

So without further ado, lets get cracking.

Part 1: The Algebraic Data Type (ADT)

Many times when people say "I used this Monad for this, or that Monad for that", what they really mean is: "I used this Algebraic Data Type (ADT) for this and that ADT for that". When looking at the code they are presenting, you find that they never touch the Monad part of the type, or in some cases the type is not even a Monad.

I would like to start things off by clearing up this point of contention with me. It seems like a minor thing, but I have found calling things a Monad when we really mean some ADT tends to lead to confusion when we are starting to build our initial intuitions around Monads and other aspects of a data type.

Before we can begin to understand what makes an Algebraic Data Type a Monad or not, we need to first get a feel around what an ADT is. The best way I can think of to broach the topic is provide a simple definition as to what an ADT is. Then demonstrate how an ADT in JavaScript is used in contrast to a (hopefully) more familiar imperative implementation.

Let's take a look at the data we will be processing with our examples:

// data :: [ * ]
const data = [
  { id: '9CYolEKK', learner: 'Molly' },
  null,
  { id: 'gbdCC8Ui', learner: 'Thomas' },
  undefined,
  { id: '1AceDkK_', learner: 'Lisa' },
  { id: 3, learner: 'Chad' },
  { gid: 11232, learner: 'Mitch' },
]

The data is a mixed Array that could contain values of any type. In this specific instance we have three types in play: POJOs (Plain ol' JavaScript Object) of varying shape, a Null instance and an Undefined instance.

Our examples will be defined with the following list of requirements:

Accept any value of any type at its input.
Unless the data is an Array with at least one valid record, an empty Object will be returned.
Return an Object of valid records keyed with a valid id from the included record, effectively filtering out any invalid records.
We define a valid record as an Object with a String keyed with id.
This function does not throw, no matter the input, and provides a reasonable default in the empty Object it returns.

From these requirements, we can implement an imperative function that does the following:

Verify input is an Array, return an empty Object if it isn't.
Declare a result accumulator for building our final result, defaulting it to an empty Object.
Iterate over the provided Array and do the following for each item:
1. Validate the item against our record criteria
2. If passed, add the record to the result, keyed by the id value on the record. Otherwise do nothing.
Return the result.

With a few helpers to help us with some type checking, we can provide an implementation like this:

// isArray :: a -> Boolean
const isArray =
  Array.isArray

// isString :: a -> Boolean
const isString = x =>
  typeof x === 'string'

// isObject :: a -> Boolean
const isObject = x =>
  !!x && Object.prototype.toString.call(x) === '[object Object]'

// indexById :: [ * ] -> Object
function indexById(records) {
  if (!isArray(records)) {
    return {}
  }

  let result = {}

  for (let i = 0; i < records.length; i++) {
    const rec = records[i]

    if (isObject(rec) && isString(rec.id)) {
      result[rec.id] = rec
    }
  }

  return result
}

indexById(null)
//=> {}

indexById([])
//=> {}

indexById([ 1, 2, 3 ])
//=> {}

indexById(data)
//=> {
//   9CYolEKK: { id: '9CYolEKK', learner: 'Molly' },
//   gbdCC8Ui: { id: 'gbdCC8Ui', learner: 'Thomas' },
//   1AceDkK_: { id: '1AceDkK_', learner: 'Lisa' }
// }

As we see, we have a strong implementation that meets our requirements and responds to any input we give it as expected.

As for our ADT implementation, we will be leaning heavily on the crocks library. Even though JavaScript is a fully functional programming language, it lacks some structures that appear in other languages that are not general purpose languages, but are strictly functional. As a result, libraries like crocks are typically used for working with ADTs.

Here is an implementation that implements the requirements using ADTs:

const {
  Assign, Maybe, composeK, converge, isArray,
  isObject, isString, liftA2, mreduceMap, objOf,
  prop, safe
} = require('crocks')

// wrapRecord :: Object -> Maybe Object
const wrapRecord = converge(
  liftA2(objOf),
  composeK(safe(isString), prop('id')),
  Maybe.of
)

// mapRecord :: a -> Object
const mapRecord = record =>
  safe(isObject, record)
    .chain(wrapRecord)
    .option({})

// indexById :: [ * ] -> Object
const indexById = records =>
  safe(isArray, records)
    .map(mreduceMap(Assign, mapRecord))
    .option({})

indexById(null)
//=> {}

indexById([])
//=> {}

indexById([ 1, 2, 3 ])
//=> {}

indexById(data)
//=> {
//   9CYolEKK: { id: '9CYolEKK', learner: 'Molly' },
//   gbdCC8Ui: { id: 'gbdCC8Ui', learner: 'Thomas' },
//   1AceDkK_: { id: '1AceDkK_', learner: 'Lisa' }
// }

One of the differences between the two implementation that I hope was noticed is the lack of familiar flow control and logic patterns in the ADT implementation. Things like for loops and if statements do not appear once in the second implementation. They are still there, of course they are still there, but when working with ADTs we encode these flows/logic in specific types.

For instance, notice that safe function that is used in a couple places? Take a look at the predicate functions passed to the first argument of those calls. Notice that the same checks are being done there, but instead of an if we are using the safe function that returns an ADT called Maybe.

Another thing you may have noticed is the lack of state anywhere in the second implementation. Every variable declared was a function, not a single JavaScript value in sight. We used two bits of state in the original implementation, result to put together our final result and a little helper called rec which just cleans up the code and keeps us from having to reference the indexed value from the Array.

We were able to get rid of the need of the for loop and the result variable, by using the function mreduceMap to fold each record over an Assign type. Assign lets us combine Objects similar to the way Object.assign does in vanilla JavaScript, removing the need to keep track of an accumulator like the result Object. So now that we have a means to accumulate, we can then remove the for loop by leaning on mreduceMap.

The Maybe, Assign, fold, etc. stuff does not need to be understood right now. I only mention them because I want to communicate that every pattern in the original implementation is present in the ADT version, there is no magic going on here. When we code with ADTs, we remove a lot of the mechanical bits like accumulation, logic, control flow and state juggling by encoding them in ADTs and let the types take care of all the "plumbing" for us.

The last thing I hoped was picked up on is how we are using what looks like a fluent api for chaining our operations together in the functions mapRecord and indexById. Seeing code like this may make us believe that we are working with traditional Objects and classes like a typical Object Oriented Programmer might. It is even reinforced when you hear these operations called methods (all the crocks documentation does this). These intuitions and misleading characterizations can get in the way of how we understand the way that ADTs are used in our day to day code.

Next time we will dig a little deeper on ADT usage by exploring how ADTs are not Objects in the sense that an Object Oriented Programmer would view an Object.

Exercises For Fun

Take the first POJ (Plain ol' JavaScript) function and remove the for loop by using the reduce method available on Array.prototype. Take note on what happens to the result variable and how the default value of {} is applied.
Take the first POJ function and, without using timers (setTimeout or setInterval), refactor it to be the MOST INEFFICIENT implementation you can think of. As you refactor, think about what you picked it as the MOST INEFFICIENT.
Using either the first POJ function or your refactor from Exercise 1, identify the discrete actions/transformations that could live in their own functions. Then create those functions and refactor the main function to use them.

Additional Exercises (Also For Fun)

We used a third-party library's type checking predicate functions for doing our type checks. Pick one of the predicates we used and implement your own version of it, throwing different values of different types at your implementation and see if it behaves as expected.
If you happen to be versed in libraries like ramda or lodash-fp, implement the same behavior in a function using just the library you are familiar with. Compare the result of your function with the following pointfree version of the above ADT version:

// wrapRecord :: Object -> Maybe Object
const wrapRecord = converge(
  liftA2(objOf),
  composeK(safe(isString), prop('id')),
  Maybe.of
)

// mapRecord :: a -> Object
const mapRecord = compose(
  option({}),
  chain(wrapRecord),
  safe(isObject)
)

// indexById :: [ * ] -> Object
const indexById = records => compose(
  option({ error: true }),
  map(mreduceMap(Assign, mapRecord)),
  safe(isArray),
)

Forem: Ian Hofmann-Hicks

Monad Say What? (Part 1)

Part 1: The Algebraic Data Type (ADT)

Exercises For Fun

Additional Exercises (Also For Fun)