All of the example source code can be found in my GitHub Repo.

Monad 20160815b
Elements of a Monad, then some.

This article came about as a result of my investigation into what is meant by the word Monad from a programming (not Mathematical, and only just Computer Science) perspective. My deliberations (and confusions) on the topic can be found here.

Part 1: Setting-up

We are going to start our journey with an extremely simple function that converts a temperature in Fahrenheit (F) to its equivalent value in Celsius (C). It has 1 input value and 1 output value, both numeric, and no preserved data (state).

f( F => C)

The “f” of the formula above indicates the conversion function. The chart below plots a number of temperatures measured in degrees F on the vertical (y) and degrees C on the horizontal (x). The plot of (C,F) is shown below as the blue line. This has two features to not: 1) F = 32 when it crosses the C=0 line and 2) the line has a slope (or gradient to use the correct term).

JoM_1a

When our calculation works, temperatures converted from F will equal C.

f(F) => C

The process of converting F to C involves trying to change the blue line so it 1) passes through the origin (the point where both x & y are zero), and 2) change the gradient to a 45° slope (not shown above). The change in gradient shows we have a 1:1 conversion, thus f(F) = C.

  1. Deduct the value from F when F crosses C at zero: 32. This results in the magenta plot (F’) that passes through the origin.
  2. We then have to resolve the gradient, which increases by 180F for 100C, or 9F for every 5C (9/5), so we;
    1. divide F’ by 9, results in the yellow plot (F”) and
    2. finally, we multiply F” by 5 gives us C.

So the algorithm is C = (F -32) / (9/5),

which is equal to: C= (F -32) x 5/9,

which is equal to: C= ((F -32) /9) x5.

Example 1a shows this function (FtoC) and demonstrates that 77F is equal to 25C. We start with numF assigned the value 77, subtract 32 = 45, divided by 9 = 5, and multiply by 5 results in 25;

(77-32 = 45, /9 = 5, x5 = 25).

We now start to engineer this function to achieve a higher, more generic capability but using this test case as control. At all stages the function must demonstrate an accurate conversion.

Example 1b pulls each of the elements of the calculation out into their own (sub-) functions. The FtoC function calls on the sub-functions to perform the exact same calculation.

JoM_1b

Next we pull the sub-functions completely out of the FtoC function but reference them through an array. This is where it starts to get over engineered: We process through the array of functions one at a time using the Array.forEach method. The initial value (numF) is passed to the first call (as candidate C), which is applied to the first function in the array.  The result of the calculation is then passed to the second call, and so on with the final calculation being output from the function (as numC).

The last example (1d) in this part, switches the data and function around. The array of (instruction) functions are assigned to FtoC and passed to a function (process) along with the initial value of F (77). The process then iterates through the array of functions in the same manner as the previous example (lc).

Part 2 – Following the Monadic path

Example 2a uses a Functional Programming (FP) technique called currying to generate the FtoC (partial application) function by calling the ‘process’ function with the set of instructions (array of functions). The ‘process’ function returns a new (lambda or anonymous) function that expects the input temperature (numF). The calculation is only performed when F is supplied to the FtoC function. This places us in an excellent position to manipulate the calculation in-process and augment the process with whatever additional facilities we like, but without disruption the original instruction functions.

In example 2b we have evolved the numeric temperature to a string that includes the scale the number represents. Thus, the input is now “77°F” and the expected output is “25°C” (the degree symbol is encoded as the hex value \xB0.) Note we have not changed the original calculation functions; they still expect and return numbers. So we have to;

a) extract the numeric value from the string at the start of the process and,

b) add a ‘fnComplete’ function to perform the final conversion of number to string (°C).

This makes the ‘process’ function rather specific but this is addressed in example 2c.

In 2c we have created three supporting functions; Return, Bind and Lift, which perform the following tasks:

  • Return: Converts the numeric temperature to a string (°C) presentation (aka the Monadic value MV).
  • Bind: Extracts the numeric temperature from the string (MV) before calling a Monadic Function MF (explained in later).
  • Lift: is used to elevate a regular (numeric) function to a Monadic Function; a function that returns a Monadic Value (string in this case).

Monad 20160815b

We still iterate through the set of instructions but we create the Monadic version of each instruction (using Lift to create MF) before calling Bind with MV and MF. Bind returns a new MV that is fed back into the next function. This means the fnComplete only need to log the output but could be used to convert the MV back to a normal value (number) if so desired.

The last step (example 2d) in this leg of our journey makes no significant changes to the functionality of our program but group the Return and Bind functions into an objMonad object that we pass into the process function. This means Lift is made a little more complicated as it now has to call objMonad.Return function, but it is these two functions (Bind and Return), as a minimum, that define a monad. We have climbed the first hill on out journey and can see out destination in the distance.

Part 3 – Avoiding dead-ends

The route to Monad is potholed and we don’t want our journey to be cut short. Using the Monadic approach we can trap faults mid-process and recover gracefully; again without changing the original functions.

Ok, in example 3b I will be changing the original divideBy function to introduce a (division by zero error) but this is for example only. In example 3a we have renamed the ‘process’ function to ‘doMonad’ because its purpose is to support the execution of a Monad, but it retains the same interface signature (Monad functions, Instructions array and completion function.)

Internally the doMonad function the processing of the instructions in a slightly different way. Instead of calling each function in turn and passing it, as input, the output of the pervious instruction we use a common FP technique called recursion. This involves a new sub-function called doInst, which is passed the input data and the next instruction to be performed. doInst calls the Bind function with the input data (MV) and the Lift-ed instruction (MF). If there are any more instructions to be performed, doInst calls itself with the return of the last instruction (a new MV) and a reference to the next instruction in the process.

The description of doInst, given above, does not quite match the example code (3a) but this to ensure scope is not compromised. To explain: strT is the Monadic Value (MV), objMonad is the object containing the main Monad functions, and arrRest is a shrinking array of instruction functions. As each instruction is performed it is removed from the list (array) before the next doInst cycle.

So, let’s introduce the ‘division by zero’ fault in example 3b and observe our stumble. So 77°F equals Infinity°C does it? I think not. As contrived as this fault is, it simulates the a kind of fault where a step in the process fails, not detected and made worst by further processing. So, let’s no correct this fault directly but trap it before it escalates.

If you re-run example 3b and observe the console you will notice the multiplyBy_5 instruction was called even though the input data was known not to be numeric. The best place to trap this fault is within the Bind because it is within the Bind we extract the numeric component of the MV before calling MF. We are able to confirm check the input data and curtain the process to avoid making a bigger mistake.

Observer the console output as you execute example 3c in the browser. Note, not only did the result not report the ‘Infinity’ error but the process was terminated as soon as the fault was found.

We have just passed through the village of Maybe and past the half-way point of our journey. Maybe is a form of Monad that is configured to determine if the MF should be performed given the value within MV.

Part 4 – Adopting a pure approach

In this leg of our trip we have return to the main path and restored the divideBy_9 instruction to its original form.

In the land of Functional Programming, the residences try to be pure so they have decreed that, the use of if conditions and mutable (changeable) variables are forbidden. Example 4a removes ‘ifs’ from the doInst function but the strM variable remains because it is assigned but not changed. It is retained at all only because it is referenced several times.

In example 4b we have removed the variables numF from the Bind function and strFinalResult from the completion function. We have also changed strM in the doInst function from a variable to an argument of the inner anonymous function, in example 4c.

Part 5 – A path of many routes

There is often more than one way of getting to a destination. So what if our process is less direct and involves multiple passes. An example might be the multiplication of two matrices.

Example 5a, shows a simple (non-monadic) approach to producing a new matrix (list or array) of values produced through the multiplication of values from two other matrices.

[1,3,5] x [10,20,30] = [10,20,30,30,60,90,50,100,150]

In example 5b we extract from the process the mechanism for iterating over the elements of the arrays. However, this approach results in arrays of arrays so we also need the flattenList function to resolve the output to a single (9 element) list.

We need to go “Monadic” (example 5c). We bring back the Monad object, Lift and doMonad functions but we leave iterating through the instructions to the Bind function.

Our instructions include two generators of matrices (arrays of numbers), along with the instruction that multiplies elements of the matrices. This means our initial input data is an empty array but we could have used a more complicated data structure to pass in the source matrices.

The completion function and objMonad.Return method only call the flattenList function, which means all the Monadic values output from this process will be a 1 dimensional array.

The doMonad calls the Bind method returning the final result to the completion function; that’s nice and simple. Before calling Bind it Lifts the first instruction into the monadic function (mf). It also compiles a Monadic Value (mv) from the initial (empty) array and a list of the remaining instructions.

The big change, as indicated earlier, is to the objMonad.Bind method, so let us dive deeper into what this is doing and why.

We have made Bind a recursive function, which means it keeps calling itself (with different input data) until it runs out of instructions. So, from the top (line 13), we assign an empty array just in case a fault occurs but in expectation that it will be populated through the result of later calls.

Whilst we are not on the last instruction we call the function in anticipation of receiving and array (matrix), which we then iterate through calling the next instruction with each element of the matrix.

JoM_5a

This means, initially we get the array containing [1, 3, 5], for each element we call the second instruction, which provided use with the second matrix [10,20,30]. When we have only the last function (knowing this is the multiplier) we pass the element from the first array along with each element of the second array. The last instruction returns an array containing a single value, which is consolidated into an array in response to the second array. In turn this (flattened) array of three values for each of the elements of the first array is consolidated into a nine-element (3 groups of 3) array. Finally, the completion function flattens the result in to a 1 dimensional array of 9 elements.

This is a complicated example so experiment with it. Observe during execution in the browser, who the elements are extracted and the (Bind-Mult) and the new lists constructed (Bind-List), with the final (Bind-List) containing a single list of 9 elements.

We have reached the end of our journey and after a freshen-up we shall review our voyage.

Part 6 – Review the voyage

To look back at our trip we will reverse the initial temperature calculation we used as an example at the outset. Instead of Fahrenheit to Celsius (F to C), examples 6a to 6d will convert Celsius to Fahrenheit.

Example 6a – Non-Monadic: We generate a function “CtoF” that expects a string representing a temperature in Celsius (25°C) and will return the same temperature in Fahrenheit, as a string (77°F).

An array of five instruction functions first converts the input data from string to numeric, perform the mathematic conversion and generate the string format of the calculated output data.

The process function takes the array of instructions and returns the array that performs the actual calculation using an iterative process. Not a monad in sight.

Our first monadic example (6b) brings back our objMonad object with its Return and Bind methods; not to forget the Lift function. We use a compound monadic value (mv) that includes not only the temperature value but also a reducing list of instructions. This enables our Bind function to employ a recursive approach but it does so by calling itself.

We use an iterative approach again in example 6c but through an intermediate function ‘fnIterate’ which calls the Return and Bind methods on behalf of the doMonad process. The Bind method only has to perform MF(MV) and can forget about the method of processing. The use of the intermediate function is enabled through the provision of an optional 4th parameter on the doMonad call of ‘iterative’, along with reference to the iterative forms of the Finale (completion) function and objIterativeMonad methods.

In our final example (6d) we return to a recursive approach but using an intermediate function called ‘fnRecurse’. The doMonad is configured with objRecursiveMonad, the “recursive” switch and the fnRecursiveFinale function.

All of the example source code can be found in my GitHub Repo.

Supplemental

In the YouTube channel FunFunFunction (https://www.youtube.com/channel/UCO1cgjhGzsSYb1rsB4bFe4Q), the host MPJ provides a very good explanation of Monad (https://www.youtube.com/watch?v=9QveBbn7t_c) but make sure to pick up the correct explanation of Functors (https://www.youtube.com/watch?v=DisD9ftUyCk) first. I highly recommend you check-out the rest of his Functional Programming videos (https://www.youtube.com/playlist?list=PL0zVEGEvSaeEd9hlmCXrk5yUyqUag-n84).

In essence: A Functor is a collection of like objects that implements the MAP method to facilitate the processing of all items in the collection using a common (callback) function.

A Monad is a super-functor that also implements a FLATMAP (aka Bind) method, which extracts the value out of the item before processing it and enables the processing of far more complicated items.

The flatmap operation is a combination (or composition) of the Map and Flatten operations. The flatten function converts a collection of collections into a single collection. When processing items in a collection each process could potentially result in zero, one or many new values in its own collection. The end result being a collection of collections. The flatten operation reduces this to a single-level collection, so the flatmap operation first iterates over the collection of items and performs a function on each item, using the Map operator, before passing the result to the Flatten operator to ensure the output retains the same structure as the input. This is important to enable composition of monadic functions.

Advertisements