Monad & Monoid

Summarizing from the previous article, we have new tools: class Functor to implement a map control function for any data type including primitive types and structured types, and class Applicative to apply composite data structures that are locally storing a function f onto another value of the same type of structure as if using the function f directly.

In this article we will learn about pattern named Monad and Monid which are also very popular in the Functional environment. Let’s start with Monad , which continues to be a class that extends from the Functor -> Applicative line.

Monad

Here we will reiterate a bit about the previously known class . First we have a class Functor that is used to create a binding that implements the map function as a HOF handler for any data type.

Applicative then extends from Functor with the additional constraint that it requires writing implementation code for the apply function, and the special feature of apply is that it allows us to apply the functionality of a function that is being stored inside a structure. wrapper data structure onto another data structure of the same type.

And now we have Monad further extending from Applicative with the additional constraint that it requires writing implementation code for the bind function, to be able to pass a Wrapped a value to a func : (a -> Wrapped b) . The point here is that we have an arbitrary function func designed to take a value of a and return a value of b placed in a Wrapped wrapper of the type of a .

That means the bind operation will have to parse the Wrapped a ‘s structure to extract the a and pass it to the func function. So we have the class Monad definition as follows.

Because it is not supported at the syntax level of the language, we still have to write the definition with the apply and map functions inherited from the previous class ; And the starting point for naming Type Variable will take precedence from the newly appeared bind function.

Then in the implementation code we reuse the code of the module MaybeExt of the previous article. We already have the apply and map functions working fine when implementing the class Applicative . Now we will change the step of class declaration from Applicative to Monad .

The bind function we need to implement first takes a value of a in the Wrapped wrapper type, and so we have the type information Maybe a . The next parameter is the function func : (a -> Wrapped b) will have the corresponding style information as (a -> Maybe b) .

The logic in the function is that we have a case where Maybe a can be Nothing or Just a . In case the bind function receives Nothing , it will not apply the func function but return Nothing , and in the other case, we will separate the a value in the pattern and pass it to func .

And from the type information of the functions we can reverse-reference to set the specific type information for the Type Variable in the instanceMonad declaration.

Summary of the code of the module MaybeExt :

Now we open Elm REPL again to try using MaybeExt.bind

The basic meaning of using Monad as we see here is the addition of a bind function that allows us to attach a data structure that can be complex in form to an anonymous lamda function with a very concise definition; Because the data structure analysis logic has been generalized in the bind function and so the lamda will only represent the main processing logic that we want.

This is the point where we can think about in applying to another environment like JavaScript , the state-based branching logics of data structures are actually very repetitive and can be generalized into HOF as seen.

Among JavaScript ‘s structured data types, only Array has been defined with many HOF including map , but there is still no apply like the example JavaScript code at the end of the previous article and bind with the general logic. shouting like Monad here.

You can try the code to add these HOF to the class Set class Map in JavaScript to use. Certainly, HOF will be very useful and reduce a lot of data conversion operations to Array to use the available HOF , especially in the case of the class Set .

To avoid confusion, apply and bind of the class Function in JavaScript have no meaning equivalent to the Applicative and Monad functions of the same name here; Because those are just methods that replace the normal function call syntax or attach the reference address of the object to the function that needs to use this pointer.

The HOF we are talking about belong to the module of data structures, and will have detailed implementation logic that varies depending on the structure of each data type. If we implement HOF in JavaScript , it will be in the form of methods of data object like funcArray.apply(valueArray) or static methods of class to have the same syntax as Elm here.

Monoid

The concept of Monoid is quite simple, but I myself do not have the vocabulary of Math so I do not know how to translate this name. However, to describe the nature, we can understand that a Monoid interface will include components called: an Associative association function, an Identity characteristic value, and a controller function that implements the association. concatenate a list of values ​​using Associative .

First we have Associative which is an implementation that satisfies the condition that how the pivot values ​​are sorted will not affect the final result; For example, addition + , multiplication * , etc. or an interactive description implementation in software does not necessarily involve Mathematics.

The next element, Identity is a meaningless value for the Associative implementation. For example we have the value 0 meaningless with the calculation + by x + 0 = x , or the value 1 meaningless with the calculation * by x * 1 = x .

And the other factor is the control function, which does not belong to the Monoid definition in Mathematics, so we will talk about it in the following example code. First we will have a general definition of the Monoid interface with the generic names of the elements set in the Functional Programming environment and append , empty , and concat respectively.

With the examples x + 0 = x and x * 1 = x , we can see that the data type number or any other data type can have more than one Monoid interface; As long as we can specify an Associative & Identity pair, we will definitely be able to write a control function that binds a list of values ​​to use.

That way we can create separate module for each Monoid to have a concise and intuitive usage syntax, instead of concentrating all the Monoid into one module such as Sum , Product instead of NumberExt . Now we will look at the example code of the module Sum with Associative association which is the addition + operation and the Identity characteristic value of 0 .

In place of the concat handler we are using Associative and Identity to calculate the sum of a list of arithmetic values. This is the application of Monoid to solve the problem of summation of values ​​for a set.

Since pure Declarative environments have no loop syntax, the recursive algorithm is the only way to do the summation of a list, and in all other cases when we need to convert a list. list into a single symbolic value.

The basic elements for using the recursive algorithm are the Associative and Identity components of Monoid . For example, when calculating the sum, we consider the calculation (+) as Associative and need to specify the corresponding Identity to be 0 to make the edge case breakpoint for the logic branching each iteration; Or when calculating the product, we consider the calculation (*) as Associative and need to indicate that Identity is 1 in the edge case .

Obviously, in the case of real-world data processing, we might want to use the built-in HOF instead of a lengthy recursive function definition; For example List.foldr or List.foldl , or in JavaScript array.reduce , _.reduceRight ; And the concant function will now be able to be written in a generic copy/paste form for module that implement Monoid .

Ok, so we have gone through all the basic concepts of Functional Programming . Now we can continue to learn how to use Elm to build SPA - Single Page Application . In the last article of the Sub-Series Declarative , we had to pause at the paragraph to learn about tools that support URL structure analysis to move on to learn about the HOD in this Sub-Series.

For the convenience of following and re-reading the relevant knowledge about Elm Architecture and Browser.Element driver, I will write a new article to continue in the paused part of Sub-Series Declarative . After building a simple SPA , we will consider whether to return to this Sub-Series Functional and create another project Elm Fullstack .