Functional Memoization in Javascript

January 22, 2017 0 Comments

Functional Memoization in Javascript

 

 

Functional Memoization is a technique which makes a function call faster by trading space for time. Memoize caches the return values of the function, so if the function is called again with the same arguments, Memoize jumps in and returns the cached value, instead of letting the function compute the value all over again.

The term was first coined by the scientist Donald Mitchie in 1968. He proposed using Memoized Functions to improve performance of Machine Learning and it’s became more popular in recent years with the rise of Functional Programming.

A Pure Function is the one that

  • Returns same output for the same input, every time.
  • Doesn’t depend on and doesn’t modify the state of the variables out of its scope. This includes having no side-effects like logging(console.log) or any DOM manipulation.

A Pure Function

Slice function returns same output for same input and does not mutate(change) any external variable like ‘arr’ in this case.

An Impure Function

Splice function mutates(changes) the original array, hence the same input does not produce same output every time.

Slice and Splice do the same thing to the array but in a different way, slice returns a new array according to the input, guaranteeing the same output per input every time. Splice on the other hand modifies the original array and the same output per input is not guaranteed.

Slice(without a ‘p’) is pure and can be memoized but Splice(with a ‘p’) is impure and cannot be memoized.

So, it makes sense that memoization does not works for Impure Functions, because if the function does not return same value for the same input the returned cached value will not be the required result. It’ll make more sense when we memoize some stuff.

Memoization works great with recursive functions, as the Recursive functions are called again and again. So let’s memoize the famous recursion of the classic factorial function. But first, we have to define a memoize function which takes another function and caches its calls.

A General purpose memoize function

Okay, now we are prepared, let’s start memoizing…

Logging to console is not a property of Pure Function but its added in factorial function for explaining purposes.

Okay okay, This is what happened

When factorial(3) is called, functions factorial(2) and factorial(1) are also called because of recursion. But when factorial(3) is called again the memoize function simply retuned the cached result, so no recursion happened.
In case of factorial(4), the function returned the calculated value from cached result of factorial(3), stopping the further recursion. 

Memoization can potentially increase performance by caching the results of previous function calls but they are not ideal for fast executing functions.

I hope this helps you in easy memoizing of your pure javascript functions. Thanks for reading.


Tag cloud