Understanding Monads with Javascript

The original article is Understanding Monads With JavaScript ( Ionuț G. Stan ).
I would be grateful for comments on errors / typos / inaccuracies of the translation in PM

From the author

For the past few weeks, I've been trying to understand monads. I'm still learning Haskell, and, to be honest, I thought I knew what it was, but when I wanted to write a small library — well, for training — I found that although I understand how monadic bind (>>=) works bind (>>=) and return , but I can't imagine where the state comes from. So, probably, I don’t understand how it all works. As a result, I decided to re-examine the monads using the example of Javascript. The plan was the same when I displayed Y Combinator : I took the original task (here it is an interaction with an immutable state clearly), and went all the way to the solution, changing the original code step by step.

I chose Javascript, because it forces me to write everything that Haskell obligingly hides due to its laconic syntax or various semantics (lambda expressions, operators and embedded function currying). And finally, I'm better at comparing, so I solved this problem also on CoffeeScript and Scheme, here are links to code snippets:

• CoffeeScript: gist.github.com/936519
• Scheme: gist.github.com/936695

')

Restrictions

In this article I will confine myself to the monad of state, this is enough to understand what monads are in general. So here are our limitations:

• no changeable state
  Haskell uses monads, since it does not have a mutable state.
  
• no explicit state
  When you do not have a mutable state, you are forced to pass the resulting state everywhere. Writing and reading such a code is hardly fun, while monads hide all this ugliness (you will see it later).
  
• no duplication of code
  This remark goes hand in hand with the previous one, but I still carry it separately, because removing duplicate code is a powerful tool for exploring new heights.
  

Mnogoubufniasilya

The article turned out to be quite saturated, so I thought it would be nice to add additional material, and recorded a short video with all the steps that are described below. This is like the tl; dr version, and should help show all the described transitions, but it looks like watching the video will not be very useful without reading the article.
I recommend watching it directly on Vimeo , where it is available in HD.

Our guinea pig

I will use the stack as our test subject, because it has an easy-to-understand structure, and its normal implementation uses state changes. Here is how the javascript stack is usually implemented:

 var stack = []; stack.push(4); stack.push(5); stack.pop(); // 5 stack.pop(); // 4 

An array in Javascript has all the methods we expect to see in the stack: push and pop . What I don’t like is that they change a state. Well, at least I don't like it in this article.
Every step I describe is a worker. Just open the console of your browser, and refresh this page: you will see several groups of lines 5 : 4 . However, in the text of the article I will only bring changes from the previous step.

Stack with explicit state handling

The obvious solution for avoiding a changeable state is to create a new state object for each change. In Javascript, this might look like this:

 // .concat()  .slice() -   ,    ,     ,     var push = function (element, stack) { var newStack = [element].concat(stack); return newStack; }; var pop = function (stack) { var value = stack[0]; var newStack = stack.slice(1); return { value: value, stack: newStack }; }; var stack0 = []; var stack1 = push(4, stack0); var stack2 = push(5, stack1); var result0 = pop(stack2); // {value: 5, stack: [4]} var result1 = pop(result0.stack); // {value: 4, stack: []} 

As you can see, pop and push return the resulting stack. pop also returns the value from the top of the stack. Each subsequent stack operation uses a previous version of the stack, but this is not so obvious due to the difference in the representation of the returned values. We can strengthen the duplication of code by normalizing the returned values: make push return undefined :

 var push = function (element, stack) { var value = undefined; var newStack = [element].concat(stack); return { value: value, stack: newStack }; }; var pop = function (stack) { var value = stack[0]; var newStack = stack.slice(1); return { value: value, stack: newStack }; }; var stack0 = []; var result0 = push(4, stack0); var result1 = push(5, result0.stack); var result2 = pop(result1.stack); // {value: 5, stack: [4]} var result3 = pop(result2.stack); // {value: 4, stack: []} 

This is the same duplication of code, which I mentioned above. Duplication, which also means explicit state transfer.

Rewrite the code in the continue transfer style

Now I will replace these intermediate results with function calls, since it is easier for me to abstract away from functions and parameters than simple variables. To do this, I will create a bind helper function that simply applies the transferred continuation to the result of the stack operation. In other words, it binds a continuation to a stack operation.

 var bind = function (value, continuation) { return continuation(value); }; var stack0 = []; var finalResult = bind(push(4, stack0), function (result0) { return bind(push(5, result0.stack), function (result1) { return bind(pop(result1.stack), function (result2) { return bind(pop(result2.stack), function (result3) { var value = result2.value + " : " + result3.value; return { value: value, stack: result3.stack }; }); }); }); }); 

The value of the entire expression returned in finalResult is of the same type as the value of an individual push or pop operation. We need a uniform interface.

Currying push and pop

Next, we need to detach the stack argument from push and pop , because we want bind pass it implicitly.
To do this, we use another trick of lambda calculus, called currying . In other words, it could be called procrastination of the use of a function.
Now, instead of calling push(4, stack0) we will call push(4)(stack0) . In Haskell, we would not need this step, because there the functions are already curried.

 var push = function (element) { return function (stack) { var value = undefined; var newStack = [element].concat(stack); return { value: value, stack: newStack }; }; }; var pop = function () { return function (stack) { var value = stack[0]; var newStack = stack.slice(1); return { value: value, stack: newStack }; }; }; var stack0 = []; var finalResult = bind(push(4)(stack0), function (result0) { return bind(push(5)(result0.stack), function (result1) { return bind(pop()(result1.stack), function (result2) { return bind(pop()(result2.stack), function (result3) { var value = result2.value + " : " + result3.value; return { value: value, stack: result3.stack }; }); }); }); }); 

Preparing bind for passing stacks

As I said in the previous part, I would like bind deal with passing an argument with an explicit stack. To do this, first, let's make it so that bind stack as the last parameter, but in the form of a curried function, i.e. let bind return a function that takes a stack as an argument. Also, now push and pop partially applied, that is, we no longer pass them the stack directly, this is now done by bind .

 var bind = function (stackOperation, continuation) { return function (stack) { return continuation(stackOperation(stack)); }; }; var stack0 = []; var finalResult = bind(push(4), function (result0) { return bind(push(5), function (result1) { return bind(pop(), function (result2) { return bind(pop(), function (result3) { var value = result2.value + " : " + result3.value; return { value: value, stack: result3.stack }; })(result2.stack); })(result1.stack); })(result0.stack); })(stack0); 

Remove stacks at the end

Now we can hide the intermediate stacks by changing bind so that it analyzes the return value of the stackOperation function, stackOperation out the stack, and stackOperation it to the continuation, which should be a function that accepts the stack. We must also wrap the return value { value: value, stack: result3.stack } into an anonymous function.

 var bind = function (stackOperation, continuation) { return function (stack) { var result = stackOperation(stack); var newStack = result.stack; return continuation(result)(newStack); }; }; var computation = bind(push(4), function (result0) { return bind(push(5), function (result1) { return bind(pop(), function (result2) { return bind(pop(), function (result3) { var value = result2.value + " : " + result3.value; // We need this anonymous function because we changed the protocol // of the continuation. Now, each continuation must return a // function which accepts a stack. return function (stack) { return { value: value, stack: stack }; }; }); }); }); }); var stack0 = []; var finalResult = computation(stack0); 

Hide remaining stack

In the previous implementation, we hid several intermediate stacks, but added another one, in the function that returns the final value. We can hide this stack trace by writing another result helper function. In addition, it will hide the view of the state we are storing - a structure with two fields, value and stack .

 var result = function (value) { return function (stack) { return { value: value, stack: stack }; }; }; var computation = bind(push(4), function (result0) { return bind(push(5), function (result1) { return bind(pop(), function (result2) { return bind(pop(), function (result3) { return result(result2.value + " : " + result3.value); }); }); }); }); var stack0 = []; var finalResult = computation(stack0); 

This is exactly what the return function in Haskell does. It wraps the result of the calculation in a monad. In our case, it wraps the result in a closure that the stack accepts, and this is precisely the monad of computations with a variable state — a function that takes its state. In other words, result/return can be described as a factory function that creates a new context with a state around the value that we give it.

We make the state internal

We do not need our continuations to be aware of the structure returned by the push and pop functions, which actually represent the insides of the monad. So we modify bind to transfer only the necessary minimum of data to callbacks.

 var bind = function (stackOperation, continuation) { return function (stack) { var result = stackOperation(stack); return continuation(result.value)(result.stack); }; }; var computation = bind(push(4), function () { return bind(push(5), function () { return bind(pop(), function (result1) { return bind(pop(), function (result2) { return result(result1 + " : " + result2); }); }); }); }); var stack0 = []; var finalResult = computation(stack0); 

Perform a stack calculation

Since we can combine stack operations, we want to perform these calculations and use the result. This is generally called the evaluation of a monad. In Haskell, a stateful computation monad provides three functions for computing it: runState , evalState and execState .
For the purposes of this article, I will replace the State suffix with a Stack .

 // Returns both the result and the final state. var runStack = function (stackOperation, initialStack) { return stackOperation(initialStack); }; // Returns only the computed result. var evalStack = function (stackOperation, initialStack) { return stackOperation(initialStack).value; }; // Returns only the final state. var execStack = function (stackOperation, initialStack) { return stackOperation(initialStack).stack; }; var stack0 = []; console.log(runStack(computation, stack0)); // { value="5 : 4", stack=[]} console.log(evalStack(computation, stack0)); // 5 : 4 console.log(execStack(computation, stack0)); // [] 

If all we are interested in is the final calculated value, then evalStack is what we need. It starts the monadic calculation, discards the final state, and returns the calculated value. Using this function, we can pull the value out of the monadic context.
If you have ever heard that you cannot escape (escape) from a monad, then I will say that this is true only in a small number of cases, such as the IO monad. But this is another story, the main thing is that you can leave the monad of calculations with a variable state.

Is done

If you are still with me, then I will say that the monad in Javascript may look like this. Not as cool and readable as in Haskell, but this seems like the best thing I could do.
Monads are a rather abstract concept, because it almost does not indicate what to write. Basically, it says that you have to create a function that takes several arguments (state in the case of a stateful monad) and two additional functions: result and bind . The first will work as a factory for the function you created, and the second will provide the outside world with only the necessary data on the monad, and do all the boring work, such as passing a state, using the continuation that will receive the value computed by the monad. Everything that should be inside the monad - remains inside. Just like in OOP - you can even create monadic getters / setters.
For the record, here’s what a Haskell computation would look like:

 computation = do push 4 push 5 a <- pop b <- pop return $ (show a) ++ " : " ++ (show b) 

The main reason why it looks better on Haskell is the support of monads at the syntax level in the form of do notation. It's just sugar for a version that still looks better than in Javascript. Haskell, thanks to support for operator redefinition and laconic lambda expressions, allows for a more readable implementation of monads:

 computation = push 4 >>= \_ -> push 5 >>= \_ -> pop >>= \a -> pop >>= \b -> return $ (show a) ++ " : " ++ (show b) 

In Haskell >>= , this is what I called bind in Javascript, and return is what I called result . Yes, return in Haskell is not a keyword, but a function. In other cases, return is a unit . Brian Marick called >>= decider in his Clojure monad video . Patcher, of course, he called return .

Some sugar for javascript

In fact, it is much better to perform monadic calculations in Javascript using the auxiliary function sequence . Due to the dynamic nature of Javascript, the sequence can take an arbitrary number of arguments, which are monadic operations that must be executed sequentially, and the last argument an action that must be performed on the result of monadic actions. All non-undefined monadic calculations will be passed to this callback.

 var sequence = function (/* monadicActions..., continuation */) { var args = [].slice.call(arguments); var monadicActions = args.slice(0, -1); var continuation = args.slice(-1)[0]; return function (stack) { var initialState = { values: [], stack: stack }; var state = monadicActions.reduce(function (state, action) { var result = action(state.stack); var values = state.values.concat(result.value); var stack = result.stack; return { values: values, stack: stack }; }, initialState); var values = state.values.filter(function (value) { return value !== undefined; }); return continuation.apply(this, values)(state.stack); }; }; var computation = sequence( push(4), // <- programmable commas :) push(5), pop(), pop(), function (pop1, pop2) { return result(pop1 + " : " + pop2); } ); var initialStack = []; var result = computation(initialStack); // "5 : 4" 

The authors of the book Real World Haskell compare monads with a software emulated semicolon ( programmable semicolon ). In our case, we have a software-emulated comma, since I used it to separate monadic actions in a sequence .

Monads, like deferred calculations

Often you have heard how monads were called calculations. At first I did not understand why. We can say, they say, because they calculate different things, but no, no one says: “monads calculate”, they usually say, “monads are calculations”. I finally understood (well, or think I understood) what this means after completing a draft article. All these chains of actions and values ​​do not calculate anything until they are told to do it. It is simply a large chain of partially applied functions that can be performed after a call with an initial state. Here is an example.

 var computation = sequence( push(4), push(5), pop(), pop(), function (pop1, pop2) { return result(pop1 + " : " + pop2); } ); 

Does this piece of code calculate anything after execution? Not. You must run it with runStack , evalStack or execStack .

 var initialStack = []; evalStack(computation, initialStack); 

It seems that push and pop produce actions on some global value, while in fact they are always waiting for this value to be passed to them. It's almost like in OOP, when we have this as the context of the calculation. In our case, this is implemented through currying and partial application, and also indicates a new context in each expression. And, if in OOP the context is called implicit, then using monads you make it even more implicit (if there is one at all).
The advantage of monads (and functional programming in general) is that you get easily combinable blocks. And all this thanks to currying. Each time two monadic actions are performed sequentially, a new function is created that is awaiting execution.

 var computation1 = sequence( push(4), push(5), pop(), pop(), function (pop1, pop2) { return result(pop1 + " : " + pop2); } ); var computation2 = sequence( push(2), push(3), pop(), pop(), function (pop1, pop2) { return result(pop1 + " : " + pop2); } ); var composed = sequence( computation1, computation2, function (a, b) { return result(a + " : " + b); } ); console.log( evalStack(composed, []) ); // "5 : 4 : 3 : 2" 

This may seem of little use when performing operations on a stack, but when designing, for example, a parser combinator library, this becomes quite useful. This allows the library author to provide only a few primitive functions for the parser monad, and then the library user can mix these primitives as he needs, eventually coming to the built-in DSL.

the end

Well, I hope this article has been helpful to you. Her writing (and translation - note ) definitely helped me to improve the understanding of monads.

Links

Books

• Programming in haskell
• Learn You a Haskell For Great Good!
• Real world haskell

Articles and documents

• A Schemer's Introduction to Monads
• Monadic parsing in haskell
• Monadic Parser Combinators
• Monads in Python
• What the hell are monads?

Video

• The Quick Essence of Functional Programming
• Monad Tutorial in Clojure, Part 1
• Monad Tutorial in Clojure, Part 2
• Monad Tutorial in Clojure, Part 3
• Monad Tutorial in Clojure, Part 4