05 How MapReduce and Monad Operate Around Values #

Hello, I am Ishikawa.

In the previous class, while learning about the mechanics of composition and pipelines, we were introduced to reducers for the first time. We also encountered the concepts of map, filter, and reduce when discussing transduction. In today’s class, we will further understand the principles of transduction through the built-in functional methods of arrays in JavaScript, so that we not only know the result but also understand the reasoning behind it.

In addition, we will explore the concept of monads that can be derived from map as a functor and see how they enhance the interaction between functions.

Core Operations on Data #

Before we start, let me first explain what you should focus on in this lesson. In this course, I will guide you through the map, filter, and reduce methods that come with JavaScript itself. These methods are essential for manipulating values. At the same time, I will also answer the question raised in the previous lesson on how to achieve reduce with mapping and filtering. This serves as the foundation for our later discussions on functors and monads.

Alright, let’s start with map.

Mapping and Functors #

We often hear that array.map is a functor. But what is a functor?

In practice, a functor is a data type or data structure value with an operator utility. Let’s take a common example. In JavaScript, a string is a data type, and an array is both a data type and a data structure. We can use a string to represent a word or a sentence. If we want to convert each letter in the following image to uppercase, it is a process of transformation and mapping.

Let’s represent a mapping functor for strings with an abstract code. As you can see, the stringMap takes the string “Hello World!” as input and returns the uppercase “HELLO WORLD!” by applying the uppercaseLetter utility function.

stringMap(uppercaseLetter, "Hello World!"); // HELLO WORLD!

Similarly, if we have a mapping functor for arrays called arrayMap, we can convert each element of the array ["1","2","3"] into an integer and output an array of integers [1, 2, 3].

["1","2","3","4","5"].map(unary(parseInt)); // [1,2,3,4,5]

Filtering and Predicate #

After discussing functors, let’s take a look at filters and predicates.

As the name suggests, filtering means to remove unwanted elements. But there is one thing to note: filtering can be bidirectional. We can filter out elements we don’t want, or filter in elements we want.

Now let’s talk about predicates. In the previous lesson on tools for processing input parameters, we also discussed predicates. For example, identity can be seen as a predicate. In functional programming, a predicate is a filtering condition, so we often use predicate functions in filters.

Let’s consider an example. Suppose we have a isOdd function that determines whether a value is odd. It is a predicate, and its filtering condition is to filter out odd numbers from an array. So, if we use it to filter [1,2,3,4,5], the result will be [1,3,5].

[1,2,3,4,5].filter(isOdd); // [1,3,5]

JavaScript also provides built-in some() and every() methods for predicates. They can determine whether a group of elements in an array all satisfy a certain condition.

For example, in the array containing the numbers [1,2,3,4,5], if we want to determine whether each element is less than 6, the result will be true. If we want to determine whether they are all odd numbers, the result will be false, because there are both odd and even numbers in the array.

let arr = [1,2,3,4,5];
arr.every(x => x < 6)      // => true, all values are less than 6
arr.every(x => x % 2 === 1) // => false, not all numbers are odd

Similarly, some() can help us determine whether there are any numbers or odd numbers less than 6 in this array. In this case, both of these conditions return true. let arr = [1,2,3,4,5]; arr.some(x => x < 6) // => true, there are numbers smaller than 6 in the array arr.some(x => x % 2 === 1) // => true, there are some odd numbers in the array

Although some() and every() are assertion methods built into JavaScript, compared to filter(), they don’t seem as “functional” because their return value is only true or false, without returning a set of data like filter() does for further functional operations.

reduce and Reducer #

Lastly, let’s talk about reduce. In fact, the main purpose of reduce is to combine the values in a list into a single value. As shown in the diagram below:

In reduce, there is a reducer function and an initial value. For example, in the following example, with an initial value of 3, the reducer function calculates the result of multiplying 3 by 5, then multiplying that result by 10, and finally multiplying the resulting value by 15, resulting in a final value of 2250.

[5,10,15].reduce( (arr,val) => arr * val, 3 ); // 2250

Besides being able to implement it independently, reduce can also be implemented using the map and filter methods. This is because the initial value of reduce can be an empty array [], allowing us to treat the result of iteration as another array.

Let’s take a look at an example:

var half = v => v / 2;
[2,4,6,8,10].map( half ); // [1,2,3,4,5]

[2,4,6,8,10].reduce(
    (list,v) => (
        list.push( half( v ) ),
        list
    ), []
); // [1,2,3,4,5]

var isEven = v => v % 2 == 0;
[1,2,3,4,5].filter( isEven ); // [2,4]

[1,2,3,4,5].reduce(
    (list,v) => (
        isEven( v ) ? list.push( v ) : undefined,
        list
    ), []
); // [2,4]

As you can see, here I intentionally used a side effect. From the first lesson, we know that array.push is an impure function that modifies the original array instead of creating a copy and modifying it. And if we want to completely avoid side effects, we can use concat. However, we also know that although concat follows the principles of pure functions and immutability, it has a performance issue when dealing with large amounts of copying and modification. So at this point, you probably already guessed the principle of transducers mentioned in the previous lesson.

Yes, we intentionally used side effects to improve performance!

You might think that this violates the principles of pure functions and immutability. In fact, it doesn’t, because in principle, the changes we made are all within the scope of the function, and as I mentioned earlier, the side effects to pay attention to are usually from external sources.

Therefore, in this example, we don’t need to sacrifice performance for side effects that have almost no negative impact. Transducers, on the other hand, leverage side effects to achieve performance improvements.

Monad #

Alright, let’s go back to the question mentioned at the beginning of the course: what is the difference between a monad and a functor?

In the preface, we also mentioned that a functor is actually a value with some functionality around it. So we know that array.map can be seen as a functor. It has a set of values, and methods like map can be applied to each value in the array, providing a mapping functionality. And a monad is a functor with some additional special functionality, the most common of which are chain and applicative functor. Let me show you in more detail.

Array as functor #

As we mentioned earlier, array.map is a functor. It has a built-in wrapper object that has mapping functionality. Similarly, we can also write our own Just Monad with a mapping method. We can use it to wrap a value (val). At this point, the monad becomes a new data structure based on the value, which contains a map method.

function Just(val) {
    return { map };

    function map(fn) { return Just( fn( val ) ); }
}

As you can see, its usage is similar to the array map we saw earlier. For example, in the example below, we use map to apply a function v => v * 2 to the value 10 wrapped in the Just monad, and it returns 20.

var A = Just( 10 );
var B = A.map( v => v * 2 ); // 20

Chain as bind or flatMap #

Now let’s talk about chain.

Chain is usually called flatMap or bind. Its role is to flatten or unwrap the value (val) wrapped by Just. You can use chain to apply a function to a wrapped value and return a result value. The code below shows an example:

function Just(val) {
    return { map, chain };
    
    function map(fn) { return Just( fn( val ) ); }
   
     // aka: bind, flatMap
    function chain(fn) { return fn( val ); }
}

Here’s another example. We use the chain method function to apply an “add one” function as a parameter to monad A. It returns a result of 15 + 1 = 16, and the returned value is a flattened or unwrapped 16.

var A = Just( 15 );
var B = A.chain( v => v + 1 );

B;          // 16
typeof B;   // "number"

Monoid #

Okay, since we mentioned chain, let’s also take a look at monoid.

In the previous lesson, we talked about function composition. In composition, there is a concept called the problem of consistent signatures. For example, if one function returns a string and the next function expects a number as input, they cannot be composed. Therefore, the functions received by the compose function must conform to consistent fn :: v -> v function signatures, which means that the parameters received and the return value types of the functions must be the same.

Then, functions that satisfy these type signatures form a monoid. When you see this formula, does it seem familiar? Yes, its concept is based on the previously mentioned identity function. In TypeScript, identity is also an example of generic usage. For example, in languages like C# and Java, generics can be used to create reusable components, where a component can support multiple types of data. This allows users to use the component with their own data types. Its basic principle is also based on an identity function like this.

function identity<T>(arg: T): T {
    return arg;
}

Identity has a use in monads. If we use identity as a parameter in the monad, it can serve as an inspection tool. For example, let’s use Just to wrap the value 15, and then when calling the chain method, we pass identity as a parameter, and the returned value is a flattened or unwrapped 15. So we can see that it also serves as a log here.

var A = Just( 15 );
A.chain (identity) // returns 15

Applicative Functor #

Lastly, let’s take a look at the applicative functor, or ap for short.

The purpose of ap is actually quite simple. As the name suggests, its purpose is to apply a wrapped function to a wrapped value.

function Just(val) {
    return { map, ap };

    function map(fn) { return Just( fn( val ) ); }

    function ap(anotherMonad) { return anotherMonad.map( val ); }
}

Here’s an example. You can see that ap takes the value inside monad B, applies it to monad A through the mapping of monad A. Since the mapping accepts a function type value, here we pass in a curried add function that first remembers the first parameter 6 through closure, then adds the input 10, and finally outputs the result of 16.

var A = Just( 6 );
var B = Just( 10 );

function add(x,y) { return x + y; }

var C = A.map( curry( add ) ).ap( B );

C.chain(identity); // returns 16

If we put all these functionalities together, its overall implementation would look something like this:

function Just(val) {
    return { map, chain, ap, log };

    // *********************
    
    function map(fn) { return Just( fn( val ) ); }

    // aka: bind, flatMap
    function chain(fn) { return fn( val ); }

    function ap(anotherMonad) { return anotherMonad.map( val ); }

    function log() {
        return `simpleMonad(${ val })`;
    }
}

Speaking of functors and applicative functors, let’s also take a look at array.of, a factory method in arrays. Its purpose is to receive a set of parameters and create a new array.

var arr = Array.of(1,2,3,4,5); // returns: [1,2,3,4,5]

In functional programming, we call functors that implement the of factory method as pointed functors. With a pointed functor, we can put a set of values into an array container, and then use a mapping functor to map each value. And the applicative functor is a pointed functor that implements the apply method.

Summary #

In today’s class, we learned several core operations for arrays in functional programming. We answered the question of how to achieve reduce using mapping and filtering, which was discussed in the previous class. At the same time, we gained a deeper understanding of the principles of reducer and transducer.

We now know that array.map is actually a functor, which includes the mapping function. It can operate on each value in an array and return a new array. A monad can be seen as a functor with some additional special features. Of course, different monads can also be combined with each other. For example, combining just with nothing, which is an empty value monad, can form a maybe monad to handle exceptions related to empty values.

In addition to functors and monads, there are other concepts in functional programming, such as either and IO. Either is used to replace conditional operations like if-else or try-catch, and its value contains a single value. IO can be used to delay the execution of functions, and its value contains a function. I won’t go into much detail here, but if you’re interested, you can delve deeper into these concepts.

Discussion question #

From the perspective of functional programming, do you think promises in JavaScript can be considered monads?

Feel free to share your thoughts and answers in the comments section, and consider sharing today’s content with more friends.