Think in a functional way, usually in an imperative way

When we first learn functions, functions are usually described as units that can complete a function independently, and they usually appear in an imperative manner:

function fact(n: number):  number {  
    let result = 1;
    for (let i = 0; i <= n; i += 1) {
        result *= i;
    }
    return result;
}
1234567

Code is to manipulate data and program one form of data into another. Abstract data is a kind of data, and the bitmap displayed on the screen is also a kind of data. Of course, we can also treat functions as data when necessary. We can get a mapping relationship between data and interface, just as React advocates:

Model -> View  
1

Or in the form of a function

View = f(Model)  
1

Now we won't discuss React, just the function itself. We can regard functions, especially pure functions, as specific forms of data mapping relationships.

For example, according to the recurrence formula of power a[n] = a * a[n -1], we can easily get a function to find the power:

function exp(a: number, n: number) {  
    return a * exp(a, n - 1);
}
123

This function is very concise, but it will cause concern. First, it makes n function calls, which will have a lot of function call overhead; Second, it has the risk of exploding.

So we go back to the recursive formula. First, we get a mapping relationship: a * a[n - 1] - > a[n]. Obviously, the implementation of power should be such a function, where prev is a[n - 1]:

function expImpl(a: number, prev: number): number;  
1

A recursive termination condition is also missing here. We add it:

function expImpl(a: number, prev: number, i: number, n: number): number;  
1

Of course, the implementation is simple:

function expImpl(a: number, prev: number, i: number, n: number): number {  
    if (i >= n) {
        return prev;        
    }
    return expImpl(a, a * prev, i + 1, n);
}

function exp(a: number, n: number) {  
    return expImpl(a, 1, 0, n);
}
12345678910

We can also do a simple optimization by removing a variable:

function expImpl(a: number, prev: number, i: number) {  
    if (i <= 0) {
        return prev;
    }
    return expImpl(a, a * prev, i - 1);
}

function exp(a: number, n: number) {  
    return expImpl(a, 1, n);
}
12345678910

These two functions directly return the execution result of the other function, which is called tail call. expImpl happens to be a recursive function, which constitutes a tail recursion. Modern compilers are smart enough to optimize them into equivalent loop forms:

function exp(a: number, n: number) {  
    let i = n;
    let ret = 1;
    while (i > 0) {
        ret = ret * a;
        i--;
    }
    return ret;
}
123456789

Thus, our recursive version can be regarded as having a space complexity of O(1) and a time complexity of O(n). Unfortunately, only Safari in modern browsers implements this optimization. We assume that the execution environment supports tail recursive optimization. According to the definition of power in mathematics, when n is an even number, we have (a^(n / 2))^2 =(a ^ 2) ^ (n / 2). According to this equation, we can get the logarithmic time version of computing power recursion (and its equivalent cyclic version, of course):

function fastExpImpl(a: number, prev: number, i: number) {  
    if (i <= 0) {
        return prev;
    }
    if (i % 2 === 0) {
        return expImpl(a * a, prev, i / 2);
    }
    // Here you can also make a small optimization expImpl(a * a, a * prev, (i - 1) / 2);
    return expImpl(a, a * prev, i - 1);
}

function fastExp(a: number, n: number) {  
    return expImpl(a, 1, n);
}
1234567891011121314

Using the thinking of mapping, let's discuss the old friend, Fibonacci sequence. Beginners can write such a simple recursive version:

function fib(n: number): number {  
    if (n <= 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}
123456

Obviously, this is not a good implementation. There are a lot of repeated calculations here, and there is a risk of stack explosion. According to the recurrence formula of Fibonacci sequence, we can get such a relationship:

a[n - 2] + a[n - 1] -> a[n]  
1

So this function should be like this, where a represents a[n - 1] and b represents a[n - 2]:

function fibImpl(a: number, b: number): number;  
1

The termination condition of recursion is also missing:

function fibImpl(a: number, b: number, i: number, n: number): number;  
1

Of course, as in power calculation, we can optimize a parameter, so we get a simple recursive version with space complexity of O(1) and time complexity of O(n):

function fibImpl(a: number, b: number, i: number): number {  
    if (i <= 1) {
        return a;
    }
    return fibImpl(a + b, a, i - 1);
}

function fib(n: number): number {  
    return fibImpl(1, 0, n);
}
12345678910

And the equivalent circular version:

function fib(n: number): number {  
    let a = 1;
    let b = 0;
    let i = n;
    while (i > 1) {
        a = a + b;
        b = a;
        i--;
    }
    return a;
}
1234567891011

In this version, we have a set of transformation rules:

a <- a + b  
b <- a  
12

We call it the t-transform. Through observation, it can be found that repeated application of T for N times starting from 1 and 0 will produce a logarithmic Fib(n+1) and Fib(n). In other words, Fibonacci numbers can be generated by applying T(n) (the nth power of transformation T) to Duality (1,0). Now consider t as a special case of p = 0 and q = 1 in the transformation family T(p, q), where T(p, q) is a transformation according to the rules of a < - BQ + AQ + AP and B < - BP + AQ for Duality (a, b). Please prove that if we apply transformation T(p, q) twice, the effect is equivalent to applying the same form of transformation T(p', q'), where p'and q' can be calculated by P and Q. In this way, just like fastExp, we can get a Fibonacci sequence function with a spatial complexity of O(1) and a time complexity of O(log n). This is exercise 1.19 of the construction and interpretation of computer programs. You can complete this process by yourself.

By thinking about the Fibonacci sequence of old friends, we found that thinking in a functional way can effectively simplify the problem and get a simple recursive version. When our execution environment does not have the ability to automatically optimize the tail call, we can easily manually optimize it into an equivalent loop form if necessary. This is the advantage of functional thinking.

Posted by adamwhiles on Tue, 31 May 2022 14:58:11 +0530