Haskell’s infinite array

Haskell is a standardized, general-purpose, purely functional programming language with lazy evaluation and strong static typing. Because of lazy evaluation, in Haskell you can create an infinite array. For example,

• [0..] Create a 0, 1, 2… An increasing array
• Repeat 0, create an array of all zeros with an infinite length
• let a = 1:2:a
  • Create an array a, the first element is 1, the second element is 2, and the rest is A (yes, you can recursively define it)
  • Get a [1, 2, 1, 2, 1, 2…] An array that repeats indefinitely

Solving sequence problems with infinite arrays

An infinite array is very powerful for describing sequences. Define the symbol “++” to stand for linking two sequences, so

An arithmetic sequence can be described like this

The general description of the Fibonacci sequence is

But we can also express it this way by recursive infinite arrays

• 
  $f(a, b) = [a] ++ f(b, a +b)$
• Fibonacci sequence = f(1,1)f(1, 1)f(1,1)

The following problem can also be described recursively

The original link

Just to keep things in suspense, let’s see what a common solution might look like.

General solution (TypeScript)

Through linked lists.

Haskell solution

Looks a lot easier there!

Understand the Haskell solution

To make it easier to understand, we can generalize the definition of the sequence u to f(n).

Under this definition, the sequence u we want is equal to the sorted f(1).

Note that f(n) conforms to the following property:

Haskell’s solution can be understood as describing the properties of this recursion through an infinite array.

Because Haskell’s syntax is quite unusual, here’s what it looks like when translated into JS for ease of understanding

Next corresponds to f(n), f(n), f(n). Recursion in Next has no boundary conditions, and in JS without lazy evaluation it would loop forever. In Haskell, an array is defined and its value is not evaluated. It is evaluated only when the value is fetched by the outermost IO.

Do we have any language features in JS that allow lazy evaluation? There are also! That’s the Generator. So we can construct a similar solution using the Generator

Mimics infinite arrays in JS with Generator

Through an infinite array we can f the properties of f (n) (n) = {n} ∪ f (2 n + 1) ∪ f (3 n + 1) (n) = f \ {n \} \ cup (2 n + 1) f \ cup f (3 n + 1) f (n) = {n} ∪ f (2 n + 1) ∪ f (3 n + 1) :

The performance comparison

The performance of the Generator must be compromised. The following is the time comparison when index = 1e6.

Performance is still better than Haskell!

Implement an inert array in JavaScript

Specification

Is it possible to encapsulate an inert array in JS as we just mimicked the Haskell solution with Generator? It needs to meet the following specifications

• The value is evaluated lazily
• Values that have been computed are cached
• The length could be infinite
• The contents of the array cannot be changed
• Available length
• You can concatenate several lazy arrays to produce a new lazy array
• Can be traversed
• Gets the element with the specified subscript
• Definitions can be recursive

So we can use it like this

Where v0. Recursive Generator

Naive LazyArray implementation (stack-prone) LazyArray@v0

This is done directly by recursively calling the self Generator function

There is a problem with this implementation: it is too prone to stack bursting, and the code below, for example, directly causes an overflow.

Because in a recursive way the call stack looks like this

The depth of the stack is limited, ranging from thousands to tens of thousands, depending on the host environment.

V1. Optimization of explosion-proof stack (with bugs)

So what’s the solution to this stack bursting problem? Turn recursion into iteration.

But LazyArray is defined to support recursion. Is there any way to express a recursive definition iteratively? We can replace the function ~ used in recursion

At this point, our call process is shown in the figure below, and the call stack is always only one layer.

How can this not overflow ~

Emmmmmm, but this version is buggy. Because this optimization assumes that the yield value in every self function will be yield to the outermost layer. For example, after this optimization, the map in the following example does not work

Because we masked the Generator for self(n), the map got the empty sequence.

So in this optimization we also need to determine whether the Generator returned by the next self function is directly consumed by the Generator of the self function at the next level. Only then can we optimize.

V2. recursion is iteration only when the conditions are met

It is also possible to use it to re-solve Twice Linear (😅 is written with the same complexity)

import { LazyArray } from "https://raw.githubusercontent.com/zxch3n/lab/master/lazy-array/lazy-array.ts";

function* merge(a: Iterator<number>, b: Iterator<number>) {
  letva = a.next().value! ;letvb = b.next().value! ;while (true) {
    if (va < vb) {
      yield va;
      va = a.next().value;
    } else if (va > vb) {
      yield vb;
      vb = b.next().value;
    } else {
      yieldvb; va = a.next().value; vb = b.next().value; }}}const f = LazyArray.createFactory<number.number> ((n: number, self) = > {
  return LazyArray.concat([n], merge(self(2 * n + 1), self(3 * n + 1)));
});

const ans = f(1);
export function solve(i: number) {
  return ans.get(i);
}
Copy the code

LazyArray implementation: ZXCH3n/LAB

TwiceLinear code: zxch3n/blog