# Introduction

Recently I went through this fascinating article Professor Frisby’s mostly adequate guide to Functional Programming and would like to summarise my understanding in this post.

# f(x)

In *imperative programming*, you get things done by giving the computer a sequence of tasks and then it executes them. While executing them, it can change state. In *purely functional programming* you don’t tell the computer what to do as such but rather you tell it what stuff *is*.

// Imperative var original = [1,2,3,4,5] var squared = [] for(var i = 0; i < original.length; i++) { var squaredNumber = original[i] * original[i] squared.push(squaredNumber) } console.log(squared) //=> [1, 4, 9, 16, 25]

// Functional var original = [1,2,3,4,5] var squared = original.map(n => n * n); console.log(squared) //=> [1, 4, 9, 16, 25]

## Functions are first-class

In Javascript, functions are “first class”, we mean they are just like everyone else for example, like a Number, String etc.,

## Functions are better if they are pure

A pure function is a function that, given the same input, will always return the same output and does not have any observable side effect.

Side effects may include but not limited to,

Changing the file system Inserting/Updating/Deleting a record into a database Making a http call Mutations Printing to the screen/logging Obtaining User Input Querying the DOM Accessing system state

## 8th grade math

From mathisfun.com:

A function is a special relationship between values: Each of its input values gives back exactly one output value.

Take a function which calculates `square`

function square(x) { return x * x; }

If function is just a special relationship between values as mentioned above, we can visualize the function as a simple table:

There’s no need for implementation details if the input dictates the output. **Pure functions are mathematical functions and they’re what functional programming is all about.**

A pure function is:

- Cacheable
- Self Documenting
- Testable
- Reasonable (Referential transparent: A spot of code is referentially transparent when it can be substituted for its evaluated value without changing the behavior of the program.)
- Can be made to execute in
*parallel*

# Curried Functions

The concept of curried functions is, you can call a function with fewer arguments than it expects. It returns a function that takes the remaining arguments.

For eg., a curried add function can be,

function add = a => b => { return a+b; } add(1)(2) // Result: 3

As explained earlier, a function is a special relationship between values: **Each of its input values gives back exactly one output value. **Using curried functions, we can make new, useful functions on the fly simply by passing in a few arguments and as a bonus, we’ve retained the ** mathematical function definition of each input mapping to exactly one output despite multiple arguments**. This is the reason, why every function in Haskell officially only takes only one parameter. All the functions that accepted

*several parameters*will be

*curried functions*.

# Composition – Holy Grail

compose function can be defined as:

```
``````
var compose = function(f, g) {
return function(x) {
return f(g(x));
};
};
```

`f`

and `g`

are functions and `x`

is the value being piped through them.

The most important building block in FP is functions. Composition allows us to combine these smaller building blocks to build larger programs. If you look at the function definition, `compose`

function takes 2 functions `f`

and `g`

and creates a * brand new function *which takes a value

`x`

calls `g`

and then passes the result to function `f`

and returns the result.Functional composition is **associative**.

```
``````
// associativity
var associative =
compose(f, compose(g, h)) == compose(compose(f, g), h);
// true
```

This means that it doesn’t matter how we group our calls to `compose`

, the result will be the same. This allows us to write a variadic compose (which is implemented in libraries like `lodash`

, `ramda`

etc.,).

The best analogy to think about the power of composition is **UNIX pipes**. 2 of the important points in Unix philosophy are:

- Write programs that do one thing and do it well.
- Write programs to work together.

For eg;

find - walk a file hierarchy cat - concatenate and print files grep - file pattern searcher xargs - construct argument list(s) and execute utility Each program mentioned above exactly does one job very well. But when we combine/compose them together you get powerful programs. find . -name "fp.txt" | xargs cat | grep "FP" Find a file called "fp.txt" searching from the current directory and pipe the contents to cat through xargs and then pipe the contents to grep to search for the text "FP"

In FP, we write pure functions that do one thing and do it well. We use composition to combine/compose functions so that they work together.

# Hindley-Milner

In functional world, it won’t be long before we find ourself knee deep in type signatures. Types are the meta language that enables people from all different backgrounds to communicate succinctly and effectively. For the most part, they’re written with a system called “Hindley-Milner”.

```
``````
Type signatures for the below functions are as follows:
:t capitalize
capitalize :: String -> String
:t strLength
strLength :: String -> Number
:t head
head :: [a] -> a
:t reverse
reverse :: [a] -> [a]
:t sort
``````
sort :: Ord a => [a] -> [a]
```

:t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Once a type variable is introduced, there emerges a curious property called ** parametricity**. This property states that a function will

*act on all types in a uniform manner which makes*the

*possible behavior of the function massively narrowed due to its polymorphic type.*

# Container/Box/Computational Context

We have seen how to apply functions to a value.

function addOne(x) { return x + 1; } var r = addOne(10) // r = 11

We will extend this idea by saying that any value can be in a context. For now we can think of this as a **CONTAINER** or **BOX** or **COMPUTATIONAL CONTEXT. **

You can create this type with the following definition:

```
``````
var Container = function(x) {
this.__value = x;
}
Container.of = function(x) { return new Container(x); };
```

We will take a simple type called `Maybe`

which can be in 2 different states: One state containing a value and the other `Nothing`

. In Haskell, this type is represented as

data Maybe a = Nothing | Just a

In Scala, this type is called `Option`

, which will be in 2 different states: `Some`

and `None.`

In Javascript, in the below example we will just define a `Maybe`

class which encapsulates both the states. In practice, we should mirror the Haskell or Scala or some other language have separate type constructors for each of the states.

```
``````
var Maybe = function(x) {
this.__value = x;
};
Maybe.of = function(x) {
return new Maybe(x);
};
Maybe.prototype.isNothing = function() {
return (this.__value === null || this.__value === undefined);
};
Maybe.of("JS rocks!!"); // State containing a value
Maybe.of(null); // State containing null
```

## Functor

The definition of functor:

```
````map :: Functor f => (a -> b) -> f a -> f b`

From the signature, we can clearly see that Functor defines a map method and its implementors must provide an implementation to the `map`

function. From the signature, we can see that map method allows us to do a ** data transformation**of the value that is contained in the computational context. Another very important property of

`map`

function is it **preserves structure**.

A Functor is a type that implements

`map`

and obeys some laws

`Maybe`

is a `Functor`

and it provides a `map`

implementation.

`Maybe.prototype.map = function(f) { return this.isNothing() ? Maybe.of(null) : Maybe.of(f(this.__value)); }; Maybe.of('Mayakumar').map(match(/a/ig)); // => Maybe['a', 'a', 'a']`

### Functor Laws

```
``````
// identity
map(id) === id;
// composition
compose(map(f), map(g)) === map(compose(f, g));
```

Diagrammatically, what happens under the hood of `Functor's map`

method can be shown as below:

## Monad

### Pointy Functor Factory

`of`

method is to place values in what’s called a ** default minimal context **part of an important interface called

**.**

*Pointed*Apointed functoris a functor with an`of`

method

```
``````
Maybe.of(100).map(add(1));
// Maybe(101)
```

When the `map`

function has a signature `a => M[B]`

we will get nested container types. If we had to get to the value, we have to map as many times as the wrapped container types which is not great from the caller perspective.

We somehow need to remove the extra container/box/computation context, `M[M[a]`

to `M[a]`

```
``````
var mmo = Maybe.of(Maybe.of('value'));
// Maybe(Maybe('value'))
mmo.join();
// Maybe('value')
```

Monads are pointed functors that can flatten

Any functor which defines a `join`

method, has an `of`

method, and obeys a few laws is a monad. Defining `join`

is not too difficult so let’s do so for `Maybe`

:

```
``````
Maybe.prototype.join = function() {
return this.isNothing() ? Maybe.of(null) : this.__value;
}
```

We can call `join`

right after `map`

which can be abstracted in a function called `chain`

.

```
``````
// chain :: Monad m => (a -> m b) -> m a -> m b
var chain = curry(function(f, m){
return m.map(f).join(); // or compose(join, map(f))(m)
});
```

For `Maybe`

:

```
``````
Maybe.prototype.chain = function(f) {
return this.isNothing() ? Maybe.of(null) : this.map(f).join();
}
```

`chain`

nests effects and we can capture both ** sequence** and

**in a purely functional way.**

*variable assignment*For eg:

var result = Maybe.of(3).chain(a => { return Maybe.of(30).chain(b => { return Maybe.of(300).chain(c => { return Maybe.of(3000).map(d => a + b + c + d); }); }) }); // => 3333

### Monad Laws

```
``````
// associativity
compose(join, map(join)) == compose(join, join);
// identity for all (M a)
compose(join, of) === compose(join, map(of)) === id
```

```
var mcompose = function(f, g) {
return compose(chain(f), g);
};
// left identity
mcompose(M, f) == f;
// right identity
mcompose(f, M) == f;
// associativity
mcompose(mcompose(f, g), h) === mcompose(f, mcompose(g, h));
```

Diagrammatically, what happens under the hood of `Monad's chain`

method can be shown as below:

function even(x) { if(x % 2 === 0) { return Maybe.of(x/2); } else { return Maybe.of(null); } }

## Applicatives

*Applicatives provide the ability to apply functors to each other*. We will take an example to understand better:

var add = a => b => { return a + b; } add(Maybe.of(2), Maybe.of(3)); // Not possible var maybe_of_add_2 = map(add, Maybe.of(2)); // Maybe(add(2))

We have ourselves a `Maybe`

with a partially applied function inside. More specifically, we have a `Maybe(add(2))`

and we’d like to apply its `add(2)`

to the `3`

in `Maybe(3)`

to complete the call. In other words, we’d like to apply one functor to another. We can achieve this using `chain`

and `map`

functions as defined below:

Maybe.of(2).chain(function(two) { return Maybe.of(3).map(add(two)); });

The issue here is that we are stuck in the sequential world of monads. * We have ourselves two strong, independent values and we should think it unnecessary to delay the creation of *So applicatives provides the functionality where we need to apply functions within a computational context to values in a computational context but the values are independent and hence there is no need to sequence them. A good example to think of the use of

`Maybe(3)`

merely to satisfy the monad’s sequential demands. `Applicatives`

is when we do parallel independent asynchronous computations and apply the results of each to a function contained in a functor.```
``````
Maybe.prototype.ap = function(other_container) {
return this.isNothing() ? this : other_container.map(this.__value);
}
``````
Maybe.of(add).ap(Maybe.of(2)).ap(Maybe.of(3));
// Maybe 5
```

Anapplicative functoris a pointed functor with an`ap`

method

### Applicative Laws

```
``````
// identity
A.of(id).ap(v) == v
```

```
// homomorphism
A.of(f).ap(A.of(x)) == A.of(f(x))
```

```
// interchange
v.ap(A.of(x)) == A.of(function(f) { return f(x) }).ap(v)
```

```
// composition
A.of(compose).ap(u).ap(v).ap(w) == u.ap(v.ap(w));
```

So a good use case for applicatives is when one has multiple functor arguments. They give us the ability to apply functions to arguments all within the functor world. Though we could already do so with monads, we should prefer applicative functors when we aren’t in need of monadic specific functionality.

Diagrammatically, what happens under the hood of `Applicative's ap`

method can be shown as below:

# map/of/chain/ap

We have explained the concepts behind Functor, Monad, Applicatives. There are so many structures that obey/satisfy the properties of being a functor, monad and applicative. From the above example we can see that **Maybe** is a Functor, Monad and Applicative. There are many structures that satisfy functor, monad, applicatives which include:

List Maybe IO Task (https://github.com/folktale/data.task) etc.,

If a type is a `Monad`

it has to be both an `Appliacative`

and a `Functor`

. If a type is an `Applicative`

it has to be a `Functor`

.

# Summary

Professor Frisby’s mostly adequate guide to Functional Programming is one of the best articles that I have read recently. From the article, the author wonderfully shows how powerful and deep functional programming constructs are and also explains how they can all be implemented with Javascript language.

# References

- https://www.gitbook.com/book/drboolean/mostly-adequate-guide/details
- http://learnyouahaskell.com/
- http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html (The diagrammatic representation for Functor, Monad, Applicatives are inspired from this post).

Pingback: Parallel Programming and Applicative in Scala - 지락문화예술공작단