Infinite sequences in javascript: ES6 & Clojurescript approach

Comparing Javascript generators vs Clojurescript lazy-seq by solving a Fibonnaci problem

This year I wanted to learn more Clojurescript and to do so I started some side projects using reagent and re-frame. The experience has been very interesting so far but I have had problems trying to get some inspiration on what to code to get a better knowledge of the fundamentals of the language. Looking for creative challenges I found Project Euler.

Project Euler (named after Leonhard Euler) is a website dedicated to a series of computational problems intended to be solved with computer programs — Wikipedia

That sounded great. So I started solving the first problems and then noticed that I should write about the process too. Of course, if you’re already trying to solve a Project Euler problem please do not use this as a quick guide to cheating.

As my main experience is with Javascript, I found that starting with a functional implementation allowed me to think in the problem and solve it later with Clojurescript. That way I would do some comparisons between both languages while leaving my comfort zone step by step.

Solving the sum of all even numbers below 4M in the Fibonacci sequence (1, 2)

Basically you want to generate an infinite sequence of values and check if the next one is above 4mil to stop asking for more. Then filtering the even ones and sum them. Solving it in a functional way would be like:

takeWhile(n => n < 4000000, fib(1,2)).filter(isEven).reduce(sum)

For now just remember fib() is going to return an iterable, and we are creating fib using a generator function.

Generating a lazy infinite Fibonacci sequence

The first trick in the problem is that it does not ask for the nᵗʰ element of the sequence but a condition of an element (n < 4000000). We cannot generate all the sequence and then strip the portion we need as it is infinite and we cannot know a reasonable limit to stop if we want a general solution.

We need some way to get the next number in the sequence and check if the number is below or not our threshold.

Luckily ES6 introduced generators, which allow us to generate infinite sequences on demand.

A generator is a function that returns a generator object, which is a special type of iterator object. Calling the .next method on the iterator will execute the body of the generator function until it finds a yield statement, returning the yield expression as the iterator value. Execution of the function will be “paused” and the stack saved until we call again the .next method on the iterator, which will return the next yield statement and so on.

At the same time, the generator object returned by the generator function is an iterable too, as it exposes an iterator property that other APIs can use to iterate over the object.

Example

You can create a naturalNumbers object by calling its generator function and it will implement a .next method and also a [Symbol.iterator]. Let’s have a look:

As you see n.next() and n[Symbol.iterator]().next() are the same thing in a generator object.

In the backstage the generator is storing its own state allowing us to write functions that keep track of their own state between yields without us having to imperatively store it and mutate it outside the function.

For complete information about iterables and iterators check MDN article about the iteration protocol

Fibonacci generator

Nice! Now we can start fetching values from the collection. As we want to be clojure-ish we’ll implement our own naïve take function. It takes n values from an iterable:

Great, now we can extract some values from the iterable in a declarative way:

That would do if we wanted to know the nᵗʰ element’s value, but we also have to check for the condition ( n < 4000000). Following the same process we will create a function that takes a condition and an iterable and returns values until the condition is no longer met, takeWhile:

Now is just a matter of adding a couple helper functions to check for even numbers and a sum and we can get the solution to our problem with the one-liner introduced in the article:

takeWhile(n => n < 4000000, fib(1,2)).filter(isEven).reduce(sum)

Done! You can check the entire code for the solution, of course it is not production ready and goes the happy path, but it is enough to solve this particular problem.

The Clojure way

Now that we know how to do it in JS we have to solve it in Clojure. We have been approximating our reasoning to a Clojure solution but Clojure does not uses generators. As far as I know the recommended way of solving this problem in Clojure is using lazy sequences.

A quick glance at the documentation already reveals a Fibonacci solution for our problem:

(defn fib [a b] (lazy-seq (cons a (fib b (+ b a)))))

Ok, step by step.

(defn fn [params] body)
;defn defines a function with fn name params between [] and then the body of the function (returns automatically) which is:
(lazy-seq (cons a (fib b (+ b a))))
;creates a lazy sequence of evaluating:
(cons a (fib b (+ b a)))
;which appends a to the list of calling fib again with b and (+ a b)

This is what happens when we call fib n times:

  • You call (fib 1 2) which evaluates to (cons 1 (fib 2 (+ 1 2))
  • The lazy sequence would hold now (1) and (fib 2 (+ 1 2) gets evaluated to (fib 2 3)
  • (fib 2 3) gets called and evaluates to (cons 2 (fib 3 (+ 2 3))
  • The lazy sequence would hold now (1 2) and so on…

Actually this is not what happens but a simplified version that illustrates the recursion example. This is what actually happens

Lazy-seq internally patches the cons function with a lazy version that will be executed each time we ask for an element of the sequence. So we can now use take-while as in our previous Javascript solution waiting for a (n < 4000000) element.

So in comparison:

Javascript version

takeWhile(n => n < 4000000, fib(1,2)).filter(isEven).reduce(sum)

Clojure version

(reduce + (filter even? (take-while #(< % 4000000) (fib 1 2))))

We can also use the thread-last reader macro (->>) that basically turns the expression inside out:

(->>
(fib 1 2)
(take-while #(< % 4000000))
(filter even?)
(reduce +))

That feels more comfortable, right?

Conclusion

Both generators and lazy-seq work by transforming a run to completion function into an iterator, thus creating a data structure from a calculation. While generators introduce another new syntax in the language, lazy-seq does so by patching clojure.core common functions. This is not possible in javascript due the lack of a standard library.

Both solutions look elegant and idiomatic to their own realms and going back and forth from Javascript to Clojurescript allows me to understand both languages better.

I’ll continue solving Project Euler problems with this approach and hopefully writing about it again.

Caveats

My take and takeWhile functions only work with iterators, if you wanted to use the fib generator function with lodash _.take or _.takeWhile you wouldn’t be able to do so as lodash does not support generators neither is on the scope.