A Lazy person that List

Those of you who know Haskell will be familiar with the following expressions

repeat 1 -- => [1, 1, 1, 1...
cycle "abc" -- => "abcabcabc..."
[1.3..] -- => [1, 3, 5, 7...]
Copy the code

Each of the above expressions produces an infinite list. Friends who are used to mainstream programming speech may feel confused about how to express infinite concepts in limited memory. The main reason is that Haskell is a language that uses lazy evaluation by default. The unused part of the language is just an expression in memory and doesn’t actually do any computation.

If only look at the above several expressions, many friends may say, also did not feel what magical place, seems to have no effect. Let’s look at the code below.

Fibonacci sequence in Haskell:

fibonacci = 1 : 1 : zipWith (+) fibonacci (tail fibonacci)
Copy the code

Fibonacci is itself an inert structure, so it computes the first two 1’s in the list, resulting in 1:1… Fibonacci fib of n = fib of n-1 + fib of n-2. Notice that n-1 and n-2 are exactly one place apart in the sequence, so n can be viewed as the result of the addition of the misaligned sequence.

Let’s look at another sieve for prime numbers. If you are not familiar with the sifting method, you can click on Wiki to see the idea of the algorithm. The following code is a simple implementation of Haskell.

primes = 2 : filter isPrime [3.5..]
  where
    isPrime x = all (\p -> x `mod` p > 0) (takeWhile (\p -> p * p <= x) primes)
Copy the code

So, Why Lazy?

Lazy lists make code and structure more flexible for some indeterminate length list operations. Using the primes list above as an example, in a traditional C or Java implementation, we would first declare a maximum length or a maximum range of values, such as primes up to 10,000. If we need to use more than that, we’ll have to call the generator function again to make a longer list. The problem with this is that the factory function has to be called proactively, and that maintaining a cache list manually by reusing calculated data increases code complexity. Another possibility is that we generate a very long list in advance and use only a drop of data at the head of the list in subsequent calculations, which is also extremely wasteful.

The use of lazy lists increases the expressive power of our programming, allowing us to focus on the nature of the data structure itself, rather than wasting time on how to manage the stack. Because lazy evaluation ensures that we don’t compute until we need a value, it automatically minimizes our computation and saves resources.

For example, we can read and write files using lazy byteString, which does not load the entire file itself into our memory, but reads it on demand. Sometimes when we read a large file, we may only filter out the first dozens of data we need, but we have to put hundreds of megabytes or even gigabytes of large files into memory.

How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation, if you’re interested, click on it.

Implement Lazy List in JavaScript

Is there any lazy structure in JavaScript? Let’s look at this example.

let fetchSomething = fetch('/some/thing');
if (condition) {
  fetchSomething = fetch('/some/thing/condition');
}
fetchSomething.then((a)= > {
  // TODO
});
Copy the code

The FETCH method itself is executed immediately, and the fetch method here is executed twice if the conditions are met. This is not the expected behavior, we need to make the fetch when we want it to be executed, rather than when it is declared, the usual practice is to change it to something like this.

let fetchSomething = (a)= > fetch('/some/thing');
if (condition) {
  fetchSomething = () = fetch('/some/thing/condition');
}
fetchSomething.then((a)= > {
  // TODO
});
Copy the code

Inspired by this, we can roughly achieve the following structure.

class List<T> { head: T | () => T tail: List<T> | () => List<T> constructor(head: T, tail: () => List<T>) { this.head = () => head; this.tail = tail; }}Copy the code

List

is essentially a single linked List, and tail passed in the constructor is a factory function that builds new List nodes. We evaluate head only when we reach a node and tail only when we reach its next node, otherwise head and tail are just expressions to be evaluated.

This seems to solve my problem, but there is a lot of unnecessary overhead when converting to and from regular arrays.

Is there a more natural structure in JavaScript that would save us from having to construct such a complex object, simplify our code, and make our code more universal?

I met Iterable

A new feature in ES6 gave me the answer I was looking for, Iteration Protocols. If the description of MDN is too long, you can look directly at the following equivalent type declaration.

interface Iterable<T> {
  [Symbol.iterator](): Iterator<T>;
}

interface Iterator<T> {
  next(): IteratorResult<T>;
}

interface IteratorResult<T> {
  done: Boolean; value? : T; }interface IterableIterator<T> {
  [Symbol.iterator](): Iterator<T>;
  next(): IteratorResult<T>;
}
Copy the code

All objects that implement an Iterable interface can be passed by such methods as for… of… And… Itor and array. from, and the iteration ends when done is true in the next method. And only when we access the next method will we proceed to the next iteration, which is the ideal Lazy structure.

Now let’s look at our Fibonacci how do we write it?

class Fibonacci implements IterableIterator<number> {
  private prev = 1;
  private next = 1;

  public next() {
    let current = this.prev;
    this.prev = this.next;
    this.next = current + this.prev;
    return {
      done: false,
      value: current
    }
  }

  [Symbol.iterator]() {
    return this; }}const fib = new Fibonacci();
fib.next() // => { done: false, value: 1 }
fib.next() // => { done: false, value: 1 }
fib.next() // => { done: false, value: 2 }
// etc
Copy the code

At this point, we can express an inert infinite sequence. ES6 also provides a Generator to write iterableItorators easily. In a sense, the Generator is the syntactic sugar for the code above.

Using Generator, the above code can be simplified as follows.

export function* fibonacci() {
  let prev = 1;
  let next = 1;

  while (true) {
    yield prev;
    consttemp = prev; prev = next; next = temp + prev; }}const fib = fibonacci();
// etc
Copy the code

Generators A Simple Guide to Javascript (ES6) Generators

Define the Infinite List

The code below implements the repeat, cycle, iterate, range, and other methods at the beginning of the article.

export function* repeat<T>(item: T) { while (true) { yield item; } } export function* cycle<T>(items: Iterable<T>) { while (true) { yield* [...items]; } } export function* iterate<T>(fn: (value: T) => T, initial: T) { let val = initial; while (true) { yield val; val = fn(val); } } export function* range(start: number, end = Infinity, step = 1) { while (start <= end) { yield start; start += step; }}Copy the code

As you can see, the code is very intuitive and easy to understand.

Define the Operator

After a list, we need in the list above, the following code respectively the map/filter/take/takeWhile method.

export function* map<T, U>(fn: (value: T) => U, items: Iterable<T>) { for (let item of items) { yield fn(item); } } export function* filter<T>( predicate: (value: T) => boolean, items: Iterable<T> ) { for (let item of items) { if (predicate(item)) { yield item; } } } export function* take<T>(n: number, items: Iterable<T>) { let i = 0; if (n < 1) return; for (let item of items) { yield item; i++; if (i >= n) { return; } } } function* takeWhile<T>( predicate: (value: T) => boolean, items: Iterable<T> ) { for (let item of items) { if (predicate(item)) { yield item; } else { return; }}}Copy the code

The above code is relatively simple. The harder part is implementing the ZIP method: how do you merge two lists into one?

The difficulty is that to receive an Iterable object, you don’t have to implement the next method itself (Array, String, etc.), and not all Iterable objects can be accessed through index. In addition, if we want to change from array. from to an Array and then operate on the Array, we have a situation where we pass in an Iterable that is infinite, as in Fibonacci, we cannot use array. from.

One idea I had was to find a way to upgrade an Iterable object to an IterableItorator and then iterate through it using the next method.

How? Fortunately, the Generator provides us with a yield* operator that makes it easy to define a lift method.

export function* lift<T> (items: Iterable<T>) :IterableIterator<T> {
  yield* items;
}
Copy the code

With the lift method, it’s easy to write zip and zipWith methods.

export function* zip<T, G>( seqA: Iterable<T>, seqB: Iterable<G> ): IterableIterator<[T, G]> { const itorA = lift(seqA); const itorB = lift(seqB); let valA = itorA.next(); let valB = itorB.next(); while (! valA.done || ! valB.done) { yield [valA.value, valB.value]; valA = itorA.next(); valB = itorB.next(); } } export function* zipWith<T, G, R>( fn: (a: T, b: G) => R, seqA: Iterable<T>, seqB: Iterable<G> ): IterableIterator<R> { const itorA = lift(seqA); const itorB = lift(seqB); let valA = itorA.next(); let valB = itorB.next(); while (! valA.done || ! valB.done) { yield fn(valA.value, valB.value); valA = itorA.next(); valB = itorB.next(); }}Copy the code

There are more ways to open my REPo at the bottom, but I won’t list them here.

conclusion

Generator and Iterator are very powerful language-level capabilities that ES6 brings to us, and their own evaluation can be considered lazy.

When TJ’s CO first came out in 13 years or so, the short and concise code could be said to be quite amazing. However, in our use, due to browser compatibility and our usage scenarios, I think we haven’t developed enough features. Combining IO, Network, Generator, and Iterator can do a lot more.

In addition, it is important to note that lazy lists are not silver bullets, although this article is all about lazy lists. Instead, the abuse of lazy lists can cache a lot of thunk during program execution, increasing memory overhead.

Finally, interest related – please send your resume to [email protected].

  • Making lazyList.
  • Slide Lazy List With Generator and Iterator

This article was originally posted on The Uptech blog.