Functional.js part 1

Introduction

This blog series I will cover the how and why functional in js. This part is about how to compose functions. The next parts will cover Type Classes, fmap, map, fold, monoids, functors, moands and more goodies.

I will not cover higher order function in this series. If you do not know what they are or how they work take a look at this post. Nor will I cover basic array manipulation like map, reduce and filter.

The first thing to understand functional programming is to understand types. When I say types I don’t mean the traditional types of C static languages. I mean a inferred type system like Haskell. The types make easier to understand the functions and analyzes them. (For a more detaild explonation).

We want typechecking so we don’t accidentally try to shove a square peg into a round hole and create bugs in the process.

I will be using es6 arrow functions in this article to make the code examples less verbose. Use the Traceur repl to make the examples work in your browser / node.js. If not your from the future and ES6 have allready been released, then ignore this message.

Type syntax

I will write the syntax of the type annotations in haskell style. Inside a special form of js comment that begins with a “+” in the code. Like:

1
2
//+ a :: Number
var a = 5;

List will be written like:

1
2
//+ b :: [Number]
var b = [1, 2, 3];

And type annotations for function will be:

1
2
// add :: Number -> Number -> Number
var add = (a, b) => a + b;

Where the last type is the return type of the functions. And the first to the next to last types are the parameter types of the function.
Why write the type annotations like this? Because of function application!

Type variables (Called generics in some languages).

1
2
//+ fetch :: [T] -> Number -> T
var fetch = (arr, n) => arr[n];

Type variables can be of any valid type. As long the same variable (T in this example) is of same type everywhere in the type expression.

Pure functions

When we talk about functions in a functional manner we usually mean pure functions. A pure function is a function that exactly produces the same output over and over again if you feed it the same input value.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//A pure function
//+ pureFn :: Number -> Number
var pureFn = function (x) {
return x + x;
};
//Unpure functions
//+ rand :: Number -> Number
var rand = function (x) {
return x * Math.random();
};
//+ timestamp :: Number -> Number
var timestamp = function (x) {
return x * Date.now();
};

A pure function can be written as a table with the input and output values of the function. In matematics a function is a mapping between the input set and the output set of a function. This view of a function greatly simplifies the complexity. And the biggest bonus is that the functions are side effect free! The functions are easier to test, and easier to debug when they missbehave. This is because of they are side effect free, so you don’t have to look outside the function for side effecting logic.

Memoization

Another posibility if you have pure functions is memoization. It is the process where you turn a function into a table dynamicly. Where you cache function values inside some cache object. And becouse the functions can’t change their values for the input parameters. You don’t have to worry about cacheing errors.
The canonical example is fibonacci.

Example

1
2
3
var fib = function (n) {
return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
};

Try to run fib(35). It takes forever to finish.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var memoize = (fn) => {
var memmory = {};
return (...args) => {
var mVal = memmory[args];
return mVal ?
mVal :
memmory[args] = fn.call(null, args);
};
};
var memoFib = function (n) {
return n < 2 ? 1 : memoFib(n - 1) + memoFib(n - 2);
};
memoFib = memoize(memoFib);

This version finishes almost instantently if you run memoFib(35). This is becouse the memoized version does’t have to recompute every value for each recursive step. So it takes almost linerar time to run this.

Automatic parallelization

Another benefits to pure functions are automatic parallelization. If you know your functions can’t have any side effect you can run them on diffrent cores / cpus. A good example of this is Intel’s River trail project (a demo video). They use pure functions in their api.

Function application

Function application is when you take a function and partial applies its arguments with some values. But what does this even mean?!?

First take a chill-pill, and lets look at an example.
We have defined an add function above. Now we want to make a counter function that increments the value by something.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//+ curry2 :: (a -> b -> c) -> a -> (b -> c)
// a, b, c are type variables
//curry2 is a function that takes a function from ("a", "b") to "c".
//The second argument is a parameter of type "a".
//curry2 then returns a function of "b" to "c".
var curry2 = (fn, x) => {
return (y) => {
return fn.call(null, x, y);
};
};
//+ add1 :: Number -> Number
var add1 = curry2(add, 1);
//+ sub :: Number -> Number -> Number
var sub = (a, b) => a - b
//+ sub5 :: Number -> Number
var sub5 = curry2(sub, 5);
add1(5); // 6
sub5(100); // -95

We apply the currying value to the first argument of the add function. The remaining arguments can be feed through the function wrapper around the function call. So we can easily create arbitrary many counter functions from the add function.

So the answer to why do this, is code reuse and higher level of abstraction of the code.

But curry2 only works on functions with two parameters. What about currying any function?

1
2
3
4
5
var curry = (fn, ...values) => {
return (...args) => {
return fn.apply(null, values.concat(args));
};
};

But where is the type definition of the curry function? The answer is it can’t written as a concrete type because the curry function’s arity is variadic. Usually we don’t want to write functions that are variadic. But in some cases it can’t be avoided.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//+ mul :: Number -> Number -> Number
var mul = (a, b) => a * b;
//+ pow :: Number -> Number -> Number
var pow = (a, b) => Math.pow(a, b);
//+ primeList :: [Number]
var primeList = [2,3,5,7];
//+ primeFns :: [Number -> Number]
var primeFns = primeList.map(p => curry(pow, p));
//+ powPrimeList -> [Number] -> [Number]
var powPrimeList = (exponetials) => primeFns.map((fn, i) => fn(exponetials[i]));
//+ mulPrime :: [Number] -> Number
var mulPrime = (exponetials) => powPrimeList(exponetials).reduce(mul);
mulPrimeList([1,2,3,4]); // [2, 9, 125, 2401]
mulPrime([1,2,3,4]); // 5402250

The real use of function application comes when you combine it with function composition.

There are also right currying which applies the values from the right. And partial application which you can apply function with values at arbitrary positions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var rcurry = (fn, ...values) => {
return (...args) => {
return fn.apply(null, args.concat(values));
};
};
var __ = Object.create(null);
var partial = (fn, ...values) => {
return (...args) => {
//Replace the "__" holes
return fn.apply(null, values.map((el, i) => {
return (el === __) ? args.shift() : el;
}));
};
};
//+ div :: Number -> Number -> Number
var div = (a, b) => a / b;
//+ half :: Number -> Number
var half = rcurry(div, 2);
//+ mulPow :: Number -> Number -> Number -> Number
var mulPow = (a, b, c) => a * Math.pow(b, c);
//+ mulPowBase2 :: Number -> Number -> Number
var mulPowBase2 = partial(mulPow, __, 2, __);
half(8); // 4 === 8 / 2
mulPowBase2(1,3); // 8 === 1 * Math.pow(2,3)

where “__“ is a some “magic object” value the partial function scans after and ignores that value when it applies the arguments. Then the returned functions values replaces the “__“ values in order with it’s arguments.

Function composition

Function composition is when we take the output of a function g and shove it into a function f. This is the part when type safety is a big win. Because it guarantees that the functions types fits together.
Function composition is THE WAY to control complexity. It is the way complexity is controlled in mathematics. Small function (or logical rules, but it is the same thing) that you can compose to create a grant symphony of controllable complexity.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//+ compose :: (a -> b) -> (b -> c) -> (a -> c)
var compose = (f, g) => {
return x => f(g(x));
};
//+ add1 :: Number -> Number
var add1 = curry(add, 1);
//+ mul2 :: Number -> Number
var mul2 = curry(mul, 2);
// 2 * (x + 1)
//+ equation :: Number -> Number
var equation = compose(mul2, add1);
equation(8); //18

The only requirement is that the output type of g must be the same as the input type of f.

1
2
3
4
5
6
7
8
9
10
11
12
// (String is the same as a list of char)
//+ firstThreeChars :: String -> String
var firstThreeChars = (str) => str.substr(0, 3);
//+ numToSinStr :: Number => String
var numToSinStr = (x) => Math.sin(x) + '';
//+ firstSinStrNumber :: Number -> String
var firstSinStrNumber = compose(firstThreeChars, numToSinStr);
firstSinStrNumber(3.14159); // "0.0"

But you can’t do as the following example. I precent to you the batman function:

1
2
3
4
//+ TypeError
var batmanFn = compose(firstThreeChars, numToSinStr);
"haskellrocks".split('').map(batmanFn) + ' Batman !'; //NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN Batman !

This is because (String -> String) composed with (Number -> String). And String is not equal to Number. This error is amplified with javascript is loosley typed and we don’t have a type checker. So we don’t get an error until we run the wrong function at runtime.

If we had a typechecker we would have cought it.

Usefull code from this article

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var curry = (fn, ...values) => {
return (...args) => {
return fn.apply(null, values.concat(args));
};
};
var rcurry = (fn, ...values) => {
return (...args) => {
return fn.apply(null, args.concat(values));
};
};
var __ = Object.create(null);
var partial = (fn, ...values) => {
return (...args) => {
//Replace the "__" holes
return fn.apply(null, values.map((el, i) => {
return (el === __) ? args.shift() : el;
}));
};
};
var compose = (f, g) => {
return x => f(g(x));
};
var memoize = (fn) => {
var memmory = {};
return (...args) => {
var mVal = memmory[args];
return mVal ?
mVal :
memmory[args] = fn.call(null, args);
};
};

ES5 version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
var curry = function (fn) {
var values = Array.prototype.slice.call(arguments, 1);
return function () {
var args = Array.prototype.slice.call(arguments);
return fn.apply(null, values.concat(args));
};
};
var rcurry = function (fn) {
var values = Array.prototype.slice.call(arguments, 1);
return function () {
var args = Array.prototype.slice.call(arguments);
return fn.apply(null, args.concat(values));
};
};
var __ = Object.create(null);
var partial = function (fn) {
var values = Array.prototype.slice.call(arguments, 1);
return function () {
var args = Array.prototype.slice.call(arguments);
//Replace the "__" holes
return fn.apply(null, values.map(function (el, i) {
return (el === __) ? args.shift() : el;
}));
};
};
var compose = function (f, g) {
return function (x) {
return f(g(x));
};
};
var memoize = function (fn) {
var memmory = {};
return function () {
var args = Array.prototype.slice.call(arguments),
mVal = memmory[args];
return mVal ?
mVal :
memmory[args] = fn.call(null, args);
};
};