Introduction
leisure
is a TypeScript library for creating and manipulating lazy sequences of data. The API surface resembles the ES6 map
/filter
/reduce
API, but also adds many useful helpers often seen in Lodash or Ramda.
The difference between leisure
and those non-lazy libraries is the guarantee that no computations will happen unless the result is actually used. Here's an example:
The above example will run map
across the entire list of users. The code will parse 100 addresses. In this trivial example, that computation is likely very fast, but imagine if it were more intensive (say, using computer vision in the browser to detect a landmark). The filter
will then also run 100 times to find the subset of addresses we are looking for. Then the second map
will run 100 more times (admittedly convoluted). The total time of the computation is O(3N)
.
At the end of the computation we discover that we only need the first matching result. If we were to operate on this data in a lazy fashion, the best case scenario is that the user we are looking for is first in this list. Utilizing lazy execution the first map
would one once on the first user, that resulting address would run once through the filter
and pass, then that address would run once more through the second map
. The total computation would be O(3)
. The worst case computation, where there is only 1 match and it is at the very end would be as slow as the original, but every single other permutation would be faster using the lazy approach.
Here is that same example using leisure
:
As you can see, the API is nearly identical, with the exception of the first
helper method.
Infinite sequences
One of the very interesting side-effects of being lazy is the ability to interact with infinite sequences and perform the smallest number of possible computations to search over all the possibilities. For a very contrived example, find me the first number in the Fibonacci sequence that contains my birthday (let's say I was born at the beginning of the millennium: 2000_01_01
).
Maybe it will run forever? Maybe it will find one very fast :)
Realization
Most methods in the library ask for one value from the previous computation at a time. However, some require the entire sequence of values. The process of converting a lazy sequence into a non-lazy version is called "realization." The .first
and .find
methods we've been using are examples. They take a Sequence and return a normal JavaScript value.
Here's an example which discards the first 10 numbers of an infinite sequence, then grabs the next five and uses them.
There are a handful of methods which require the entire sequence, which means they will run infinitely if given an infinite sequence. They are: toArray
, forEach
, sum
, sumBy
, average
, averageBy
, frequencies
and groupBy
.
If logging and debugging in a chain of lazy processing is not running when you expect it to, remember to realize the sequence with a .toArray()
to flush the results.
To avoid infinite loops, leisure
caps the maximum number of infinite values to 1_000_000
. This number is configurable by setting Seq.MAX_YIELDS
to whatever you want your max loop size to be.
Integration with non-lazy JavaScript
leisure
implements the Iterator protocol which means you can use it to lazily pull values using a normal for
loop.
Common usage
leisure
can be used as a drop-in replacement for the ES6 map
/filter
/reduce
API. If that's all you need, you can still benefit from the reduction in operations in the non-worst-case scenarios.
However, if you dig into leisure
's helper methods, you'll be able to write more expressive data computations. With the ES6 API, developers often drop into reduce
for more complex data transformations. These reducer bodies can be difficult to read and understand how they are actually transforming the data. leisure
provides methods which do these common transformations and names them so your code is more readable. Dropping all the way down into a reducer is quite rare in leisure
code.
Take a look at the full leisure
API.
Benchmarks
Lazy data structures should be used knowing what type of data you have and how to make the most of laziness. In general, you want to be searching large sets and either expect to find your result in the process.
Please take these benchmarks with a grain of salt. Nobody is actually searching massive spaces on the web. Even the worst performance is still far faster than you'd need or notice unless you're doing graphics or crypto.
These benchmarks search from a random array of 10,000 items.
Run yarn perf
from the repository to reproduce these numbers.
Best case (first item is all we need).
When we find what we are looking for early, our performance is outstanding.
middle case (we need to search half the space).
When the result is in the middle, we are comperable in speed to lodash.
Worst Case (we search the entire space)
In the absolute worst case, we are 3x as slow as lodash.
Prior Art
This library takes inspiration from Lazy Sequences in Clojure, Kotlin and F#.
Lazy.js is a popular lazy sequence library for JavaScript, but it was not written in TypeScript and I prefer to use libraries that think about types and transformations from the beginning.
There is some overlap between Lazy Sequences and the Functional Reactive Programming libraries. In my opinion, FRP is more concerned about event systems and Lazy Sequences are more useful for data processing.
License
Leisure is licensed under the the Hippocratic License. It is an Ethical Source license derived from the MIT License, amended to limit the impact of the unethical use of open source software.
Last updated