Functional Programming in Javascript (Part 2)

This article is the sequel of this.

Trampoline and Thunk

In the recursion section of part 1, there was stack size problem. To solve this, I would like to introduce a method called trampoline.

Before getting into what trampoline is, the concept of a thunk needs to be explained.

A thunk is a function call that is wrapped in an anonymous function. Its main use is to delay the execution.

const f = (x, y) => x * y;
const f_thunk = () => f(2, 3); // f function is wrapped
// in an anonymous function
const val = f_thunk(); // f function is executed
// by calling f_thunk function
console.log(val); // 6

thunk function can be defined as:

// thunk function takes a function and the arguments
// for the function, and returns a function that
// will call the passed function with the arguments.
const thunk = (f, ...args) => () => f(...args);

In part 1, factorial function was defined as:

const factorial = n => {
const _factorial = (n, accum) =>
n < 2 ? accum : _factorial(n - 1, n * accum);

return _factorial(n, 1);
};

With thunk the above can be rewritten:

const factorial = n => {
const _factorial = (n, accum) =>
n < 2 ? accum : thunk(_factorial, n - 1, n * accum);
    return _factorial(n, 1);
};
let val = factorial(3); // () => _factorial(2, 3)
val = val(); // () => _factorial(1, 6)
val = val(); // 6

Each time val is called, it returns a thunk that will execute the next recursive step. This step manages to detach the recursive functions from the call stack.

But it would be better if we have a way to call the thunk functions automatically instead of calling them manually one by one.

Here trampoline function comes to our rescue. The mechanic of it is very simple. It's basically calling each thunk until something other than function is returned.

const trampoline = f => {
let result = f();
    while(result && result instanceof Function) {
result = result();
}
    return result;
};

With trampoline, factorial now can be rewritten as:

const factorial = n => {
const _factorial = (n, accum) =>
n < 2 ? accum : thunk(_factorial, n - 1, n * accum);
    return trampoline(_factorial(n, 1));
};
console.log(factorial(10));      // 3628800
console.log(factorial(3628800)); // Infinity

Also, to output the stack trace, console.trace() can be added in factorial function:

// first attempt
const factorial = n => {
console.trace();
    return n < 2 ? 1 : n * factorial(n - 1);
};
console.log(factorial(3628800));
// Uncaught RangeError: Maximum call stack size exceeded

// tail optimized
const factorial = n => {
console.trace();

const _factorial = (n, accum) =>
n < 2 ? accum : _factorial(n - 1, n * accum);
    return _factorial(n, 1);
};
console.log(factorial(3628800));
// Uncaught RangeError: Maximum call stack size exceeded

// with trampoline and thunk
const factorial = n => {
console.trace();

const _factorial = (n, accum) =>
n < 2 ? accum : thunk(_factorial, n - 1, n * accum);

return trampoline(_factorial(n, 1));
};
console.log(factorial(3628800)); // Infinity

It adds more steps to create a recursive function, but once we have thunk and trampoline functions, they're reusable and their addition only requires a bit of extra typing.

Global states

Another topic I want to cover in this article is a way to manage global states.

In part 1, mutation was introduced as a side effect. However, sometimes global states are necessary and they need to be mutated for updates. One way to solve this issue is to create an object that manages all the states like what Redux does.

In a simplified explanation, Redux creates an object, which acts as a global store, with three functions: getState, subscribe, and dispatch.

dispatch function is used to call reducer functions that update the state in the store.

When the state is updated, subscribe function is called to notify the update to the registered listener functions.

Lastly, getState is used to obtain the state in the store.

The reducer functions are expected to be pure functions, and the state gained from getState function should not be mutated.

const createStore = (reducer, initialState = {}) => {
let listeners = [];
let state = initialState;
let isDispatching = false;
    function getState() {
return state;
}
    function subscribe(listener) {
let isSubscribed = true;
listeners.push(listener);
        return function unsubscribe() {
if(!isSubscribed) {
return;
}
            isSubscribed = false;
const index = listeners.indexOf(listener);
listeners.splice(index, 1);
};
}
    function dispatch(action) {
if(isDispatching) {
throw new Error('action may not be dispatched');
}
        try {
isDispatching = true;
state = reducer(state, action);
} finally {
isDispatching = false;
}
        for(let i = 0, len = listeners.length; i < len; i++) {
const listener = listeners[i];
listener();
}
        return action;
}

return { dispatch, subscribe, getState };
};

Note: the above code is simplified from the original.

createStore function above takes reducer and initialState and returns a store object. initialState is, as the name suggests, used to set the initial state of the state in the store. reducer is a function that is called by dispatch function. reducer function takes state object and action object and returns a new state object. reducer can be created with combineReducers function that takes reducers, which is an object with methods that will update the state in the store. The methods' name should also correspond to the keys of the state.

const combineReducers = reducers => {
const reducerKeys = Object.keys(reducers);
let finalReducers = {};
    reducerKeys.forEach(key => {
if(typeof reducers[key] === 'function') {
finalReducers[key] = reducers[key];
}
});
    const finalReducerKeys = Object.keys(finalReducers);
    return (state = {}, action) => {
let hasChanged = false;
const nextState = {};
        for(let i = 0, len = finalReducerKeys.length; i < len; i++) {
const key = finalReducerKeys[i];
const reducer = finalReducers[key];

const previousStateForKey = state[key];

const nextStateForKey = reducer(previousStateForKey, action);
            nextState[key] = nextStateForKey;
            hasChanged = hasChanged || nextStateForKey !== previousStateForKey;
        }
        return hasChanged ? nextState : state;
};
};

Note: the above code is simplified from the original.

For example, setting the state as:

const initialState = { name: '', age: null };

The reducers would be:

const reducers = {
name: function(state = '', action) {
switch(action.type) {
case 'UPDATE_NAME':
return action.name;
            default:
return state;
}
},
age: function(state = 0, action) {
switch(action.type) {
case 'UPDATE_AGE':
return action.age;
            default:
return state;
}
}
};

The methods in reducers take state as argument that corresponds to the value in the state whose key is the same as the method's name. So in the above case, name state is passed to name method.

The other argument the methods take is action object. It is passed from dispatch function and must have type to suggest the type of action the method should proceed. Other keys in the action object are the values to update the state.

dispatch function is used to call reducer function from outside.

In the above case:

// update state.name with the value 'John'
dispatch({ type: 'UPDATE_NAME', name: 'John' });
// update state.age with the value 22
dispatch({ type: 'UPDATE_AGE', age: 22 });

And altogether it can be used as:

const initialState = {
name: '',
age: null
};
const reducers = {
name: function(state = '', action) {
switch(action.type) {
case 'UPDATE_NAME':
return action.name;
            default: return state;
}
},
age: function(state = null, action) {
switch(action.type) {
case 'UPDATE_AGE':
return action.age;
            default:
return state;
}
}
};
const store = createStore(combineReducers(reducers), initialState); 
// to get notification when the state is updated
store.subscribe(() => {
console.log(store.getState());
});
// update state.name
store.dispatch({ type: 'UPDATE_NAME', name: 'John' });
// now the state should be { name: 'John', age: null }
// update state.age
store.dispatch({ type: 'UPDATE_AGE', age: 22 });
// now the state should be { name: 'John', age: 22 }

That’s it!

The original Redux has error checking and many more capabilities. It’s also short and concise, so it’s easy to read the code and understand what it does (it uses closures in a smart way). I learned many things from reading the code.