Stop Writing for-loops (lazy evaluation)
“I choose a lazy person to do a hard job. Because a lazy person will find an easy way to do it” — Bill Gates
This article is going to focus on what lazy evaluation is. After understanding the concept, we’re going to write a few functions to illustrate how lazy evaluation can be achieved with vanilla Javascript.
There have been a few libraries for Javascript that have implemented their functions to leverage affordances from lazy evaluation. The following are some of the tools available to you if you want to start using lazy evaluation to write more performant programs.
Overview
So what exactly is “lazy evaluation”? Lazy evaluation defers a code’s execution until the result of that code’s execution is requested. This request can either be implicit or explicit. By deferring a code’s execution, various performance enhancements can be achieved.
What is ironic about lazy evaluation is that its entire purpose is to make your code more efficient (read “faster”).
Imagine you made an HTTP request for some JSON data that contains 100 elements. You plan on filtering this array, mapping over the values and ultimately using 20 of these values within your application.
If you only need 20% of the data that you’re receiving, usually you can glean a quick performance enhancement by using Array.prototype.slice(..) before running any of the collection operations. This may work in some cases. But let’s imagine a scenario where you are agnostic about the results of your filtering operations.
You may be filtering a list of 100 movies for those produced after 1980. In this case, you only need the first twenty movies that pass the predicate of the filtering operation. This makes the situation slightly more difficult as the default filter(..) method does not allow you to filter until a certain condition has been met, which in this case would be…
collection.length === 20
Lazy evaluation makes this simple, allowing us to use the same syntax we would use ordinarily with Array.prototype.filter(..). Under the hood, however, the procedure differs. Instead of filtering all 100 elements and then using a subset of the resultant array, the code is executed until the exact number of elements being requested has been reached. The syntax would look something like this…
const results = _(movieJSON)
.filter(movie => movie.year >= 1980)
.map(movie => `${movie.year}: ${movie.name}`)
.take(20)
.value()
Pay close attention to the value(..) call that is chained onto the end of that statement. It causes the code to execute, which compared with normal, non-lazy evaluation should seem somewhat bizarre.
So if lazy evaluation defers code execution until values are requested, let’s then shift our attention to the idea of evaluation requests.
Evaluation Requests
Like many things in life, evaluation requests can either be implicit or explicit.
If the code is in a context in which a value is expected, we can call this an implicit evaluation request. The idea of request contexts in code is vaguely related to Object.prototype.valueOf(..).
If you’re unfamiliar with the purpose valueOf(..), I recommend consulting the Mozilla Developer Network’s (MDN) documentation on the topic as they can provide a much more comprehensive overview than I can. In short, however, the MDN writes:
JavaScript automatically invokes [valueOf] when encountering an object where a primitive value is expected
So what are these circumstances where primitive values are expected? Let’s create a simple constructor and augment its valueOf(..) method to illustrate this.
function BankAccount(initialDeposit = 0) {
this.balance = initialDeposit;
}BankAccount.prototype.valueOf = function() {
return `$${this.balance};
};Now with our class, BankAccount, we can demonstrate both implicit and explicit requests for our object’s “value”.
implicit evaluation request
const acct = new BankAccount(1000);
acct == "$1000"
// => true
'' + acct
// => "$1000"
In the example above, the context of our code implies that we are interested in the “value of” our object, acct. By design this context is clear enough to the Javascript engine to invoke acct’s valueOf(..) method without us explicitly instructing it to do so. Let’s contrast this with the explicit invocation, which is an easier topic to grasp.
explicit evaluation request
Here we’ll reuse our BankAccount(..) constructor from the previous example…
const acct = new BankAcct(1000);
obj.valueOf();
// => "$1000"
Simple enough! The explicit evaluation request most similarly relates to lazy evaluation. This is because most libraries that implement lazy evaluation are structured so that developers explicitly request the value of the collections on which they are operating.
Let’s look at lazy evaluation in practice using a couple of Javascript libraries.
A Look at some Libraries
Let’s take a look at lazy evaluation in practice using Lodash.
Lodash.js
const results = _([1, 2, 3, 4, 5])
.filter(x => x % 2)
.map(x => `odd: ${x}`);
It may seem strange, but in this example, neither the filter operation nor the map operation have executed…
Take a second to soak that in if this concept is new to you. Because without the creators of Lodash intentionally designing the library to defer execution, the provided array would have been both filtered and mapped.
Notice too that this pipeline we have constructed accepts an array of elements at its beginning and will return an array after the values have completed their journey through the pipeline. To illustrate…
[any] --> filter(predicate) --> map(iterator) --> [any]
So how can we be sure that filter(..) and map(..) have not executed? We can verify this by checking the type of value referenced by results.
Array.isArray(results); // false
The real operations won’t occur until we call value(..)…
Array.isArray(results.value()); // true
Let’s contrast this with the same code example as above. However, this time we won’t wrap our array, thereby foregoing lazy evaluation.
const results = [1, 2, 3, 4, 5]
.filter(x => x % 2)
.map(x => `odd: ${x}`);
And when we check if results is an array…
Array.isArray(results); // => true
Furthermore, we can see that results contains…well…our results.
results;
// => ["odd: 1", "odd: 3", "odd: 5"]
Now that we have seen the syntax of lazy evaluation using Lodash.js, let’s take a look at another library that implements lazy evaluation: Immutable.js.
Immutable.js
Let’s implement the same behavior from our previous example using Immutable.js. In Immutable, to create opportunities for lazy evaluation, we need to create a Sequence object.
const results = Immutable.Seq.of(1, 2, 3, 4, 5)
.filter(x => x % 2)
.map(x => `odd: ${x}`);
Need the value? Simple.
results.toJS();
// => ["odd: 1", "odd: 3", "odd: 5"]
Loop fusion
Lazy evaluation is efficient for a number of reasons, some of which we covered in this article’s introductory overview. Another reason lazy evaluation is efficient is because it often creates opportunities for loop fusion. Loop fusion can be illustrated by expanding our previous code block:
previous example
const results = [1, 2, 3, 4, 5]
.filter(x => x % 2)
.map(x => `odd: ${x}`);
previous example “expanded”
const results = [1, 2, 3, 4, 5];
/* -- filter -- */
let filterResults = [];
for (let i = 0, el; i < results.length; i += 1) {
el = results[i];
if (el % 2) {
filterResults.push(el);
}
}
/* -- map -- */
let mapResults = [];
for (let i = 0, el; i < filterResults.length; i += 1) {
el = filterResults[i];
mapResults.push(`odd: ${el}`);
}
console.log(mapResults);
// => ["odd: 1", "odd: 3", "odd: 5"]
Loop fusion allows us to condense these two for-loops into one for-loop, thus batching our operations.
previous example “fused”
const results = [1, 2, 3, 4, 5];
let filterMapResults = [];
for (let i = 0, el; i < results.length; i += 1) {
el = results[i];
if (el % 2) {
filterMapResults.push(`odd: ${el}`);
}
}
console.log(filterMapResults);
// => ["odd: 1", "odd: 3", "odd: 5"]
By fusing our for-loops, we’ve increased our efficiency two-fold by visiting each element of results only one time instead of two times. You can imagine that the efficiency gains are even greater when we fuse more than just two loops together.
Keep in mind, however, that loop fusion only accounts for a proportion of the efficiency gains afforded by lazy evaluation. Significant gains also arise when subsets of the originally provided array are requested using methods like take(..), drop(..), head(..), tail(..), et cetera.
Implementation
Let’s now attempt to demystify how these libraries are implementing lazy evaluation by creating a simple set of functions using the concepts of:
- loop fusion: reducing multiple loops into one
- deferred execution: executing our code only when it is requested
- short-circuiting evaluation: stopping our loop execution once we have all of the elements that we need
function createLazy(array) {
const obj = {};
let fns = [];
let takeCount = Infinity;
obj.filter = function(predicate) {
fns = fns.concat({filter: predicate});
return obj;
};
obj.map = function(iterator) {
fns = fns.concat({map: iterator});
return obj;
};
obj.take = function(x) {
if (x < takeCount) {
takeCount = x;
}
return obj;
};
obj.value = function() {
let results = [];
const hash = {
filter: function(predicate, value) {
return predicate(value);
},
map: function(iterator, value) {
return iterator(value);
}
};
let el, op, cb, result;
for (let i = 0; i < array.length && results.length < takeCount; i += 1) {
el = array[i];
for (let j = 0; j < fns.length; j += 1) {
op = Object.keys(fns[j])[0];
cb = fns[j][op];
if (op === 'filter') {
result = hash[op](cb, el);
if (result) {
continue;
}
break;
}
else if (op === 'map') {
result = hash[op](cb, el);
results = results.concat(result);
}
}
}
return results;
};
return obj;
}Using it in practice…
const array = [
1, 2, 3, 4, 5,
6, 7, 8, 9, 10,
11,12,13,14,15,
16,17,18,19,20
];
const results = createLazy(array)
.filter(x => x % 2 === 0)
.map(x => x * x)
.take(5);
If you learned nothing else from this article, I hope you learned that if you don’t ask for results’ value, the list operations will not execute…
results.value();
// => [4, 16, 36, 64, 100]
Closing Remarks
While the opening quote from Bill Gates is not directly related to the topic of lazy evaluation in programming, I chose it because it signifies that virtues can be attained through laziness. I find this counterintuitive idea to be quite provocative.
If you have not done so yet, play around with some of the aforementioned libraries. Write some tests. Use jsperf to quantify the performance gains that can be acquired with lazy evaluation.
If performance isn’t a big concern for you, try implementing some functions of your own that can be lazily evaluated. The intellectual appeal of lazy evaluation is fascinating by itself!
Check back for more articles related to functional programming concepts in Javascript.
