My friend edA-qa was recently doing some programming live using the Rust language on twitch. An interesting bit of code came up:
(1..).filter(|num| num%2 == 0).take(n).sum()
We can see that some operations are taking place on an unbounded range of numbers: (1..)
, in other words, starting at 1 and going on forever. This kind of code is part of the functional programming paradigm, and takes advantage of 'lazy evaluation', where an expression is only actually calculated on an as-needed basis.
I have been doing some programming in JavaScript lately, and I became curious if this would work in JavaScript too. I knew JavaScript had functions like filter, map, and reduce that worked with arrays, but I wondered if they would work with generators too.
It turns out they don't right now, at least not out of the box. Let's say we have a generator that just produces integers starting at 1:
const numbers = function* () {
let i = 1
while (true) {
yield i++
}
}
Can we use this directly to do operations like filter and map?
let result = numbers.map(num=>num**2).slice(0,3) //doesn't work :(
console.log('result = ' + result)
This produces:
let result = numbers.map(num=>num**2).slice(0,3) //doesn't work :(
^
TypeError: numbers.map is not a function
at Object.<anonymous> (C:\dev\lazy.js:66:18)
Trying to start the generator first also doesn't work:
let result = numbers().map(num=>num**2).slice(0,3) //doesn't work :(
console.log('result = ' + result)
This produces:
TypeError: numbers(...).map is not a function
at Object.<anonymous> (C:\dev\lazy.js:66:20)
I decided to write a simple class wrapper in JavaScript to make functionality similar to the Rust example possible.
The Lazy
class below acts as a base class for the desired behaviour.
class Lazy {
constructor(iterable, callback) {
this.iterable = iterable
this.callback = callback
}
filter(callback) {
return new LazyFilter(this, callback)
}
map(callback) {
return new LazyMap(this, callback)
}
next() {
return this.iterable.next()
}
take(n) {
const values = []
for (let i=0; i<n; i++) {
values.push(this.next().value)
}
return values
}
}
The Lazy
class just wraps a simple JavaScript iterable (see iteration protocol ). By default, if you call its next
method, it will just delegate that call to the iterable that it's wrapped around.
Notice that by themselves, calls to filter
and map
won't do much: They'll just instantiate an object. Below are the implementations of LazyFilter
and LazyMap
:
class LazyFilter extends Lazy {
next() {
while (true) {
const item = this.iterable.next()
if (this.callback(item.value)) {
return item
}
}
}
}
class LazyMap extends Lazy {
next() {
const item = this.iterable.next()
const mappedValue = this.callback(item.value)
return { value: mappedValue, done: item.done }
}
}
Both of these subclasses also just implement JavaScript's next
method.
Now let's see this code in action! Below are some simple examples that run this code:
let result = new Lazy(numbers()).map(num=>num*3).take(4).reduce((a,v) => a + v)
console.log('result = ' + result)
result = new Lazy(numbers()).filter(n=>n%2==0).take(4).reduce((a,v) => a + v)
console.log('result = ' + result)
result = new Lazy(numbers()).filter(n=>n%2==0).map(num=>num**2).take(4).reduce((a,v) => a + v)
console.log('result = ' + result)
result = new Lazy(numbers()).map(num=>num**2).filter(n=>n%2==0).take(4).reduce((a,v) => a + v)
console.log('result = ' + result)
Here are the results of running this example in node:
C:\dev>node lazy.js
result = 30
result = 20
result = 120
result = 120
In case you're unfamiliar with this type of code, I'll try to clarify how it works. Let's look at the first example:
let result = new Lazy(numbers()).map(num=>num*3).take(4).reduce((a,v) => a + v)
console.log('result = ' + result)
First, let's look at the take
function. This function starts everything off. Prior to take
being called, nothing will happen other than some objects getting created.
The take
function will call next
4 times on the LazyMap
object returned by map(num=>num*3)
. This in turn will call next
4 times on the generator returned by numbers()
. map
will pass each of those numbers from the generator to the num=>num*3
callback, which will multiply each number by 3 before, in turn, passing the result back to take
. Take returns a normal JavaScript array. In this case it will contain [3,6,9,12]
. Now we can call the Array.reduce
method, which collapses the array to a single value using the supplied callback. In this case all the numbers are added together to produce the final result of '30'.
There are a few potential 'gotchas' to be aware of: First, trying to call
reduce
on a generator that doesn't stop would not work, since thereduce
function would never run out of values to process. However, we could write a version of reduce that iteratively collapses values. Also, it's important to be careful when usingfilter
.filter
won't stop until it reaches a value that matches its callback. If we try to callfilter
on a generator that runs forever, and it doesn't find any matches, thenfilter
will just run forever too, causing our program to hang.
I think it would be more elegant for JavaScript to support any iterable as a target for functions like map
and filter
, and possibly even reduce
, not just arrays. Maybe Mozilla will do that in a subsequent release, along with nice syntactic sugar like the Rust (1..)
syntax for unbounded lazy ranges.
Related:
Top comments (5)
Well done! But wouldn't it make even more sense when the whole statement would be executed one item by one. So next() wouldn't gather all the responses of the iteration into an array, but would have the ability to evaluate an expression defining how many times to call it. So, for instance a sum could stop while reached some value.
Thanks for your comment! While this code is lazy, it's still completely synchronous. So once
take
is called, it has to run to completion - callingnext
only processes one item, but I think you meant to saytake
. I wonder if you mean that this code could be implemented asynchronously. I did implement a simple asynchronous reduce for another article:Playing with infinite lists is fun! :)
Very interesting post. A lot of new stuffs which I didn't know. Good job.
Fun Fact of The Day: Carlos Ray Norris iterated over (1..), twice.