## Sequencing computations in Javascript

Given any sequence of simple assignment statements concluded by a return statement, we can view the whole sequence
as a function that executes the first statement,
and then executes and returns a function that contains the rest of the statements.

For example, this sequence of two statements, which results in 6,

```x = 3;
2*x;
=>
6```

can be re-written as:

```(function(x){
return 2*x;
})(3);
=>
6```

which has the same result, namely 6. This is an "IIFE" or Immediately Invoked Function Expression. We define a function
and then execute it immediately. In this case the functions is being called with the number 3 as its argument.
Assuming we only ever define a single variable in each statement, our IIFE replacement functions will only ever need to
have one argument.

The outer parentheses around the function are needed to satisfy Javascript's
precedence rules. Notice that variable assignments are replaced by function calls, where each variable that was
being assigned to, is now the argument of a new function within which that variable has scope.

For three statements,

```x = 3;
y = 11;
2*x + y;
=>
17```

the equivalent nested functional expression looks like:

```(function(x){
return function(y){
return 2*x+y;
}(11);
})(3);
=>
17```

the 2*x+y expression has meaning because it's within the scope of both the surrounding functions, just like it
has meaning in the sequence of statements because it's within the same code block that consecutive statements are
implied to be within.

This same transformation can be applied to assignment statements with other types such as strings:

```x = "abra ";
y = "ca ";
z = "dabra";
x + y + z;
=>
"abra ca dabra"```
```(function(x){
return function(y){
return function(z){
return x + y + z;
}(" dabra");
}("ca ");
})("abra ");
=>
"abra ca  dabra"```

We can't get rid of non-assignment statements however:

```x = 3;
console.log(x);  //a non-assignment statement
2*x;
=>
6```

can be re-written as:

```(function(x){
console.log(x);       //it's still there!
return function(){
return 2*x;
}();
})(3);
=>
6```

But as long as our sequence of instructions just uses assignment statements and returns a value at the end, (i.e. it
has no "side-effects"), we can convert it to pure expression form. Many things we can write a piece of code
for, have no need to have side-effects, and we can transform them into this form.

```x = 3;
x = 2;
2*x;
=>
4```

can be re-written as:

```(function(x){
return function(x){
return 2*x;
}(2);
})(3);
=>
4```

That seems to work too because the inner function argument shadows the outer function argument.

Now that we can see the generality of functional expressions and nested functional expressions,
what can we do with them? Look at the following expression. It uses the map function defined on Javascript arrays
to apply a function to every element of an array, and returns a new array with elements equal to the
corresponding transformed elements. In this case, each element is doubled.

```[1, 2, 3].map(function(x){return 2*x})
=>
[2, 4, 6]```

This is how we might code the previous expression using statements instead of expressions:

```var a = [1, 2, 3];
var f = function(x){return 2*x};
var b=[]
for(var i = 0, l = a.length; i < l; i++){
b[i]=f(a[i]);
}
b;
=>
[2, 4, 6]```

Notice how much clearer the functional version is and how the map function defined on Javascript arrays,
avoids the use of for loops. For loops contain a body which
is a statement. They also contain statements for initialization, termination, and loop update (which is easy to see,
if you transform the loop into its equivalent while statement form).
The use of map means we can use an expression in
lieu of several statements that appear in a for loop statement. We therefore avoid having to keep track of a loop variable
and having to specify the starting and stopping conditions for the iteration and how to update the
loop variable. That is almost always the same. Why should we have to repeat ourselves every time?

Put another way, the expression form avoids having to keep track of the plumbing and lets us focus on the logic
we want to convey. It lets us specify the 'what' without worrying too much about the 'how'. It also lets us
focus on an individual element, the function needed to transform it, and it worries about the problem of getting the
transformation inputs from the original array and putting the transformation outputs into a new array of equal size.

Now, let's add a method called 'bind' to all Javascript arrays:

Bind will be a method on the array class that takes a function as input. When you call bind on an array, it expects you to
pass it a function that takes something of one type A and returns an array of things of a possibly different type B.
All the things in the output array should be of single type B. B can be same same as A of course.
Functions that bind would expect might include:

• `function f(x){return [x+"1",x+"2"];}`, which takes anything that can be cast to a string and returns an array of two strings.
• `function f(x){return [x-1,x,x+1];}`, which takes a number and returns an array of three numbers.
• `function f(x){return [x-1,x,x+1,x+2];}`, which takes a number and returns an array of four numbers.

What bind does is: it applies the function you pass into it, to every single element of the array you call bind on.
This results in a list of arrays. Bind doesn't return that list of arrays. It concatenate the contained arrays and returns a single array
with all the concatenated values.

For example, `[1, 2, 3, 4].bind(function(x){return [x*x,-x];})`
would first apply `function(x){return [x*x,-x];}` to each element of `[1, 2, 3, 4]`, resulting in:
`[ [1, -1] [4, -2] [9, -3] [16, -4] ]`, which after concatenation, gives `[1, -1, 4, -2, 9, -3, 16, -4]`.
So `[1, 2, 3, 4].bind(function(x){return [x*x,-x];})` = `[1, -1, 4, -2, 9, -3, 16, -4]`.

We could implement bind this way:

```Array.prototype.bind = function(f) {
var arrays = [];  //an array that will contain arrays
for(var i = 0, l = this.length; i < l; i++){
//apply f to each element of this and put the resulting array in 'arrays'
arrays[i] = f(this[i]);
}
var result = [];
for(var i = 0, l = this.length; i < l; i++){
//append the i_th array in arrays to result
result = result.concat(arrays[i]);
}
return result;
}```

But let's do it more functionally:

```Array.prototype.bind = function(f) {
var arrays = this.map(f);
return Array.prototype.concat.apply([], arrays);
}```

map and concat are standard ECMA_Script(Javascript) functions added in recent editions of the standard.

To understand the above implementation, you need to understand the concat function defined on Javascript arrays.
Concat works like this: `[1, 2].concat([3, 4], [5, 6, 7])` gives
`[1, 2, 3, 4 , 5, 6, 7]`. However arrays is an array of arrays. Doing
`[].concat([[1,2],[3,4],[5,6,7]])` gives `[[1,2],[3,4],[5,6,7]]`, which is not what
we want. The concat function will concatenate arrays passed as arguments, not arrays within arguments.
So we use 'apply', which takes an array of arguments and passes them to a function without the
array wrapper outside. 'apply' is called on the method we want to apply. We pass the object to use as
`this`in the method call, and then the arguments to be passed to that method, in a single array.
In our case, we are starting with an empty array, so `this` equals `[]`.

```[1, 2, -1].bind(function(x){return [-x, x];})
=>
[-1, 1, -2, 2, 1, -1]```

So, what does bind do? It allows us to express multiplicity or non-determinism. Bind is great for calculating
all the next legal positions in a checkers or chess game for example, starting from the current set of possible positions.
The things in the array don't have to be integers. They can be anything, maybe tuples that represent the position of a
queen on a chess board. In the example above, we can interpret the integer values in the array as integer positions along
the x-axis, and the function passed to bind as an x-coordinate update function, where the next position can have two values.
If you start on the x-axis at one of the integer x positions of
[1, 2, 3] and you make one move where you can either stay where you are or go to the negative value of your current position,
then you'll be in one of the following x-values along the x-axis: [-1, 1, -2, 2, 1, -1]. Notice that there are
duplicate values in this array, but that's good. Each value represents one way of having gotten there. Starting at 1 and being at -1
the next step is different from starting at -1 and being at -1 the next step.

Now let's define one more method on arrays, which we'll call return. The return method just puts a single
value into an array of size 1.

```Array.prototype.return = function(x) {
return [x];
}```

It does not have anything to do with the 'return' keyword which returns a value
from a function. I'm still calling it 'return' though because that's what such a function is usually called.
You can tell which one is which because the 'return' keyword that returns from a function or returns a value
from a function, is not called as
a method on an object, while the 'return' method I just defined is defined on the Array prototype and called
on array instances, or on the Array prototype itself where the actual code resides.

```Array.prototype.return(3)
=>
```
```[].return(3)
=>
```
```[100, 1000, "aaaa"].return(3)
=>
```

The array on the left doesn't matter. It's just a way to get our hands on the return method. That's why I prefer the
Array.prototype.return way of referencing the method. The fact that we don't use this within the definition of return
signals that we don't care what we call return on, only what its argument is.

Let's look at another example. In the following case, we actually ignore the function input. That's ok too.
We've decided that all our functions should take one input, so in cases where we don't need it, we just ignore it.

```[1, 2, 3].bind(function(x){
return [100,200,300];
});
=>
[100, 200, 300, 100, 200, 300, 100, 200, 300]```

However, since Javascript will ignore extra arguments passed to a function, we can rewrite the invocation of bind
this way:

```[1, 2, 3].bind(function(){   //no arguments!
return [100,200,300];
});
=>
[100, 200, 300, 100, 200, 300, 100, 200, 300]```

Now, let's look at something more complicated:

```[1, 2, 3].bind(function(x){
return [100,200].bind(function(y){
return [-x+y];
});
});
=>
[99, 199, 98, 198, 97, 197]```

This is a nested bind invocation and it uses both function variables in its innermost return value. How do we
know this expression makes any sense and that it should return the array below it? Well, the outer bind expects to be
called on an array, which it is in this case(the array [1, 2, 3]), and to be passed a function that takes a value and
returns an array of values. Let's check that this second condition is actually satisfied. Once x has a value, which it will
when we are inside the outer function, the expression:

```  return [100,200].bind(function(y){
return [-x+y];
});```

will return an array of values by the definition of bind and the fact that we are calling bind on an array, just as bind expects
(the array [100, 200]), and we are passing bind a function that takes a single value and returns an array of values(in this case
an array of size 1).
This tells us that the function containing the inner bind will return an array of values, and that the outer bind will
be happy since it expects to be passed a function that returns an array of values. The only other complication is the
fact that the innermost return expression has both the x and y variables, but that's ok since any time we are evaluating
the inner function, both x and y are defined. This is similar to when we have a nested for loop such as:

```for(var x = 0; x < 10; x++){
for(var y = 0; y < 10; y++){
console.log(-x+y)
}
}```

What's really happening in the nested bind expression above, is that the outer bind gets 1 from
[1, 2, 3], and passes that 1 to the outer function. Then, the outer function evaluates its body with x bound to 1:
it therefore calls bind on [100,200] passing it the function

```function(y){
return [-1+y];
});```

Notice how there is no more x in the return expression. Instead of being `return [-x+y]`, it is now
`return [-1+y]`. When we are executing inside the outer function, x is no longer a variable but a value.
The inner function thus evaluates and returns:

```  [100,200].bind(function(y){
return [-1+y];
});```

We can easily see that the expression above evaluates to `[99, 199]`

The outer bind does this for each value of [1, 2, 3] and end up with an array of arrays:

`[[99, 199], a-2nd-array-of-size-2, a-3rd-array-of-size-2]`

When it concatenate them, we get `[99, 199, 98, 198, 97, 197]`. Notice that the elements
of [99, 199] are the first two elements of [99, 199, 98, 198, 97, 197].

Ok, let's define a few functions that we can pass to bind (ie functions that take a value and return
an array of values):

```function f(x){return [x-1,x,x+1]};
f(3)
=>
[2, 3, 4]```
```function g(x){return [x+10,x-10]};
g(4)
=>
[14, -6]```

Now we can chain calls to bind:

```.bind(f).bind(g).bind(f)
=>
[9, 10, 11, -11, -10, -9, 10, 11, 12, -10, -9, -8, 11, 12, 13, -9, -8, -7]```

We can chain calls to bind as many times as we like. The above expression would represent 3 non-deterministic moves,
the first land last according to function f and the second according to function g.

```.bind(f).bind(g).bind(f).bind(g)
=>
[19, -1, 20, 0, 21, 1, -1, -21, 0, -20, 1, -19, 20, 0, 21, 1, 22, 2, 0, -20, 1, -19, 2, -18, 21, 1, 22, 2, 23, 3, 1, -19, 2, -18, 3, -17]```

Wouldn't it be nice if we could write

```[1, 2, 3].bind(function(x){
return [100,200].bind(function(y){
return [-x+y];
});
});```

as:

```do
x <-  [1, 2, 3]    `bind`   y <- [100,200]     `bind`   [-x+y]```

Can you see the correspondence?

`[1, 2, 3].bind(function(x){           //x <-  [1, 2, 3]    `bind`   return [100,200].bind(function(y){  //y <- [100,200]  `bind`     return [-x+y];                    //[-x+y]   }); });`

There are languages that can do this. Two of them are Haskell and Scala. Haskell has a 'do' notation as shown above,
and Scala has 'for' notation. This is why bind is sometimes referred to as a 'programmable semicolon'.

What we'd developed here with the 'bind' and 'return' methods on Array is what's know as the 'list monad'. By adding
these two methods to Array, we have made Array into a list monad. All the other stuff was just buildup and context.

However, for something to be a monad, it has to satisfy three rules:

#### The associativity law.

The first law states that we should be able to call bind(f) on an array m, and then call bind(g) on the result of that,
and get the same result as if we had called bind(h) on m, where h represents calling bind(f) followed by bind(g).

More precisely, given the two function definitions:

```function f(x){return [x-1,x+1]};
function g(x){return [x+10,x-10]};```

Notice that we can chain f and then g:

```[1, 2].bind(f).bind(g)
=>
[10, -10, 12, -8, 11, -9, 13, -7]```

or g and then f:

```[1, 2].bind(g).bind(f)
=>
[10, 12, -10, -8, 11, 13, -9, -7]```

and we get different results. So order of chaining does matter. Chaining is not commutative.

But, it is associative. This:

```[1, 2].bind(f).bind(g)
=>
[10, -10, 12, -8, 11, -9, 13, -7]```

and this:

```[1, 2].bind(function(x){return f(x).bind(g);})
=>
[10, -10, 12, -8, 11, -9, 13, -7]```

give the same result! That's an example of the associativity law for monads. It's not a proof, just an example
that shows the proof holds in a specific case.

Formally, the law is stated as:

`m.bind(function(x){return f(x).bind(g);}) = m.bind(f).bind(g)`

where m is a monad. In the case of a list monad, m is any array instance (i.e. [1, 2, 3], or []).

#### The left identity law:

This law says that wrapping a value a in an array, and then calling bind(f) on that array, is the same
as just calling f on the value a.

This law formally says that:

`Array.prototype.return(a).bind(f) = f(a)`

Let's say that `f = function(x){return [x-1,x+1]}` and `a = 7`.
Then we can see that the left side of the above expression evaluates to:

```Array.prototype.return(7).bind(f)
=>
[6, 8]```

while the right side evaluates to:

```f(7)
[6, 8]```

The result is the same so the left identity law is satisfied.

#### The right identity law

This law relies on the observation that the return method is actually the same type of method that
bind can take as its argument: it takes a value and returns an array. So calling
bind(Array.prototype.return) on an array [1, 2, 3, 4] will result in the intermediate
value of [, , , ] ‐ look at the implementation of bind to see why ‐
and the bind will concatenate those inner arrays to give [1, 2, 3, 4],
which is what we started with.

This law formally states that:

`m.bind(Array.prototype.return) = m`

And in fact, using the function f as defined above, and m = [1,2], the left side evaluates to:

```[1, 2, 3, 4].bind(Array.prototype.return)
[1, 2, 3, 4]```

which is the same as the right side.

The two identity laws say that Array.prototype.return is a left and right identity with respect to the bind
method, just like 1 is a left and right identity under multiplication and 0 is a left and right identity
under addition. It's not enough that `a + 0 = a`, which is the right identity law for zero
under addition. We also need that `0 + a = a`, which is the left identity law for zero under addition.

Because the three laws are satisfied, the Javascript Array class, with the bind and return method added to it,
is a monad. I haven't shown a proof here. The proof that an array equipped with bind and return methods, is a list monad,
can be found online. The functions I've been referring to above that are ok to pass to bind are known as "monadic functions".
They take a value and return a monad. In the case of the list monad, they take a vale and return an array.

Views: 127

Comment