DEV Community: Nitin Patel

What does the phrase Monadic Bind mean in Haskell?

Nitin Patel — Fri, 07 Jun 2019 09:57:03 +0000

I’ve been learning Haskell for a few months now and I think I have a good understanding of what monads are. I’m not an expert so I should warn you this answer might be completely wrong.

I originally posted this as a Quora answer. Reposting it here:

Monadic bind is the name given to the (>>=) function or bind function, also known as chain, flatMap, or joinMap.

I personally like to call it the “then” function borrowing the word from JavaScript Promises. It is much more intuitive that way if you read it as “then” instead of “bind”.

Consider the following Haskell program which takes a number from stdin and prints its square root in stdout.

If you read the (>>=) as then. The program basically read as:

main = getLine then stringToNumber then squareRoot *then *print.

If you have programmed in JavaScript and you’re familiar with Promises, you will find this approach quite intuitive.

In Practice, most people use the “Do Notation” which is just syntactic sugar over the monadic bind syntax. Once, you understand this, do notation should be quite easy.

For reference, here’s the same program converted to “Do notation”.

But what does (>>=) function actually do?

It’s just a monoid in the category of endofunctors. What’s the problem?

To know what this function actually does, we first need to know what a monad is. The definition of monad can be found on Wikipedia Page on Monads:

a **monad* is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic.*

Right now, this sentence doesn’t make sense, hopefully, it will make some sense after I give a few examples.

Example 1: Handling Null values (Maybe type).

I’ll use JavaScript syntax for convenience.

Let’s say we have a value which may or may not exist (nullable), we want to perform some computations on the value. These computations could also fail and return null values. Our code will be:

This code violates the DRY Principle and is quite ugly because of all the nesting. Let’s try to abstract out the repetitive code.

We can design a maybe data type which holds either some value or Null. And we can define a function that does null checking for you.

Now, instead of our functions returning null, it will return this Maybe data type. Here’s an example implementation with some functions returning Maybe type.

Then we can write our program into a flat pipeline instead of the nested hell we had earlier.

If at any point the function returns Null, all other computations will be skipped. (Like if we divide by zero or square root a negative number).

Now, look again at the definition of the monad I gave above, and see if it makes a little bit more sense now:

a **monad **is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic.

Example 2: Handling Async Values (Promises)

Let’s say that instead of returning Null values, our functions returned *Async *values, meaning that values that don’t exist yet but will be available in future. (For example, it’s an API request or Database call).

Here, instead of checking for null values, we need to *wait *for the value of the previous result to be available because we execute any function.

JavaScript had a solution to this called The **Callback Pattern. **Callback pattern solved this problem but it resulted in the same kind of nested callback hell we saw earlier. more about callbacks.

This is why the popular approach to handling async values in JavaScript is to use Promises.

We have seen that the then function in Maybe type performs an “if check” for us between every function execution. The then *function in Promises waits for the previous result and executes the given function when it is available.

This allows us to convert a nested callback code into a flat pipeline of functions.

Hopefully, you can see a pattern here and somewhat grasp the abstract concept of monads.

But what about the IO Monad in Haskell?

The IO Monad works on the same principle. As we have seen before, monadic bind performs some intermediate computation in between functions, removing the need for us to write boilerplate code.

In this case, the boilerplate code would be pulling out the value obtained by performing side effect and passing it to the next function in our chain of functions.

They’re also quite similar to promises meaning that they guarantee the order of execution by creating a dependency on previous value for the function to execute. Example,

main = function1 >>= function2 >>= function3

Here, function1 depends *on the value returned by function2. It cannot run until function1 is finished. Similarly, function3* **cannot run until function2 has finished.

If you want to actually see what bind function in IO monad does, watch this video. It is the best explanation I’ve found for IO monad.

** sidenote: Promise is not actually monad, but it’s pretty close and solves the same problem that monads solve. My purpose here is to build intuition and not be 100% accurate.*

How To Correctly Shuffle An Array in JavaScript

Nitin Patel — Wed, 22 May 2019 06:34:56 +0000

About 9 years ago, TechCrunch published this story. Microsoft had this browser ballot screen on browserchoice.eu where Microsoft was supposed to show all the different browser choices to users in random order.

"randomly" sorted

Except, it was far from random. Internet Explorer showed up in the last position about 50% of the time and Chrome was most likely to show up in the top 3. What gives? Well, here’s the code they used for doing the random shuffle:

array.sort(function (a, b) { return 0.5 — Math.random() })

At first glance, this seems like a reasonable solution. In fact, if you google search “random shuffle javascript” this code is the top result that pops up.
The code uses javascript’s sort function with a custom comparator. This comparator a number between 0.5 and -0.5.

One of the problems with this sorting algorithm, however, is that it does not work. If you want a random shuffle in which every permutation is equally likely. This algorithm fails badly at it. Here’s an interesting statistical analysis on the results of this algorithm.

Other than being wrong, it is also very inefficient. The time complexity of a regular sort function is O(n.logn). But in this case, the sort function is given a very inconsistent ordering. So, this could go into an infinite loop or stop after a few exchanges depending on the algorithm used for sorting.

The Correct Way — Fisher-Yates Algorithm

Shuffling an array of values is one of the oldest problems in computer science. And the most popular solution to it has been known since 1938. It is the Fisher-Yates shuffle.

Unlike the Microsoft shuffle, this algorithm actually shuffles the array randomly and has O(n) time complexity assuming you have a random number generator with O(1) complexity.

The original fisher yates algorithm, described is 1938 goes something likes this:

Write down the numbers from 1 through N.

Pick a random number k between one and the number of unstruck numbers remaining (inclusive).

Counting from the low end, strike out the kth number not yet struck out, and write it down at the end of a separate list.

Repeat from step 2 until all the numbers have been struck out.

The sequence of numbers written down in step 3 is now a random permutation of the original numbers. Source: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Fisher_and_Yates'_original_method

The modern version of this algorithm (from the book The Art of Computer Programming by Donald E. Knuth) goes like this:

 — To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
 j ← random integer such that 0 ≤ j ≤ i
 exchange a[j] and a[i]

In javascript, it’d be implemented as:

for(let i = array.length — 1; i > 0; i--){
  const j = Math.floor(Math.random() * array.length)
  const temp = array[i]
  array[i] = array[j]
  array[j] = temp
}

Final Thoughts

When trying to solve a problem, look for tried-and-tested approaches.

We as programmers stand on the shoulders of giants. These algorithms have been polished and refined in the last 7+ decades. There is very little chance that your own implementation is going to be better than that.

Converting XML to JSON using Recursion

Nitin Patel — Fri, 28 Sep 2018 12:39:09 +0000

The other day, I was working on an app which needed to fetch data from a third party rest api, and what happened next is the thing of the one of the worst nightmares of a JavaScript developer.

The server sent back response in.. gasp.. XML instead of JSON like any sane rest api would do.

So, I came up with a way to easily convert XML into JavaScript Object. Here’s an example of the data I was trying to read.

Keep in mind that this code makes use of WebAPIs so it is not available in server side javascript like NodeJS. This works great for front end applications like React or Angular.

The format of XML is generally something like this:

<book>
    <title>Some title</title>
    <description>some description </description>
    <author>
        <id>1</id>
        <name>some author name</name>
    </author>
    <review>nice book</review>
    <review>this book sucks</review>
    <review>amazing work</review>
</book>

I want the ouput to look a little something like this:

{
  "book": {
    "title": "Some title",
    "description": "some description",
    "author": { "id": "1", "name": "some author name" },
    "review": ["nice book", "this book sucks", "amazing work"]
  }
}

Since, XML has a lot of nested tags, this problem is a perfect example of a practical application of recursion.

Before we begin to code, we need to understand something called the DOMParser Web API.

According to the MDN documentation,

The DOMParser interface provides the ability to parse XML or HTML source code from a string into a DOM TREE.

In simple words, it converts and XML string into a DOM Tree. Here’s how it works.

Lets say we have an some XML stored in a string, strxml. We can parse the data in it as a DOM tree like this:

let strxml = `<book><title>Some title</title>
<description>some description </description>
<author>
    <id>1</id>
    <name>some author name</name>
</author>
<review>nice book</review>
<review>this book sucks</review>
<review>amazing work</review></book>
`;

const parser = new DOMParser();  // initialize dom parser
const srcDOM = parser.parseFromString(strxml, "application/xml");  // convert dom string to dom tree. 

// Now we can call DOM methods like GetElementById, etc. on scrDOM.

Now that we have got the basics right. Let’s start writing the psuedo code.

Initialize variable jsonResult is empty object. 
If scrDOM has no children nodes:
    return innerHTML of the DOM. // This is our base case.

For each childNode in children nodes:
    Check if childNode has siblings of same name. 
    If it has no siblings of same name: 
        set childnode name as key whose value is json of the child node. (we're calling the function recursively.)
    If it has no siblings of same name
        set childnode name as key whose value is an empty array, every child whose name is same as this pushed into this array.
return jsonResult

Here’s the JavaScript code:

/**
 * This function coverts a DOM Tree into JavaScript Object. 
 * @param srcDOM: DOM Tree to be converted. 
 */
function xml2json(srcDOM) {
  let children = [...srcDOM.children];

  // base case for recursion. 
  if (!children.length) {
    return srcDOM.innerHTML
  }

  // initializing object to be returned. 
  let jsonResult = {};

  for (let child of children) {

    // checking is child has siblings of same name. 
    let childIsArray = children.filter(eachChild => eachChild.nodeName === child.nodeName).length > 1;

    // if child is array, save the values as array, else as strings. 
    if (childIsArray) {
      if (jsonResult[child.nodeName] === undefined) {
        jsonResult[child.nodeName] = [xml2json(child)];
      } else {
        jsonResult[child.nodeName].push(xml2json(child));
      }
    } else {
      jsonResult[child.nodeName] = xml2json(child);
    }
  }

  return jsonResult;
}

// testing the function
let xmlstr = `<book><title>Some title</title>
<description>some description </description>
<author>
    <id>1</id>
    <name>some author name</name>
</author>
<review>nice book</review>
<review>this book sucks</review>
<review>amazing work</review></book>
`;

// converting to DOM Tree
const parser = new DOMParser();
const srcDOM = parser.parseFromString(xmlstr, "application/xml");

// Converting DOM Tree To JSON. 
console.log(xml2json(srcDOM));

/** The output will be
{
  "book": {
    "title": "Some title",
    "description": "some description",
    "author": { "id": "1", "name": "some author name" },
    "review": ["nice book", "this book sucks", "amazing work"]
  }
}
*/

This is the basic algorithm / code for converting an XML string into a JSON object. Since, it uses recursion, it can go very deep into the DOM tree and parse every single element.

This works for most of the cases. You can modify this algorithm according to your own needs or requirements.

DEV Community: Nitin Patel

What does the phrase Monadic Bind mean in Haskell?

But what does (>>=) function actually do?

a monad is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic.

a monad is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic.

How To Correctly Shuffle An Array in JavaScript

The Correct Way — Fisher-Yates Algorithm

Final Thoughts

Converting XML to JSON using Recursion

DEV Community: Nitin Patel

What does the phrase Monadic Bind mean in Haskell?

But what does (>>=) function actually do?

a **monad* is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic.*

a **monad **is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic.

How To Correctly Shuffle An Array in JavaScript

The Correct Way — Fisher-Yates Algorithm

Final Thoughts

Converting XML to JSON using Recursion

a monad is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic.

a monad is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic.