Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does using functional languages help against computing values repeatedly?

Consider a function f(x,y):

f(x,0) = x*x;
f(0,y) = y*(y + 1);
f(x,y) = f(x,y-1) + f(x-1,y);

If one tries to implement that recursively in some language like C++ he will encounter a problem.

Suppose the function is first called with x = x0 and y = y0. Then for any pair (x,y) where 0 <= x < x0 and 0 <= y < y0 the intermediate values will be computed multiple times - recursive calls will form a huge tree in which multiple leaves will in fact contain the same pairs (x,y). For pairs (x,y) where x and y are both close to 0 values will be computed numerous times.

For instance, I tested a similar function implemented in C++ - for x=20 and y=20 its computation takes about 4 hours (yes, four Earth hours!).

Obviously the implementation can be rewritten in such way that repeated computation doesn't occur - either iteratively or with a cache table.

The question is: will functional languages perform any better and avoid repeated computations when implementing a function like above recursively?

like image 336
sharptooth Avatar asked Apr 23 '10 05:04

sharptooth


People also ask

What are functional programming languages good for?

Advantages Of Functional Programming It improves modularity. It allows us to implement lambda calculus in our program to solve complex problems. Some programming languages support nested functions which improve maintainability of the code. It reduces complex problems into simple pieces.

What are the reasons to use function in computer languages?

A function is simply a “chunk” of code that you can use over and over again, rather than writing it out multiple times. Functions enable programmers to break down or decompose a problem into smaller chunks, each of which performs a particular task.

Is functional programming more efficient?

Efficiency issuesFunctional programming languages are typically less efficient in their use of CPU and memory than imperative languages such as C and Pascal. This is related to the fact that some mutable data structures like arrays have a very straightforward implementation using present hardware.

Are functional languages better?

It all comes down to your needs. If your application is supposed to be stateless, then functional programming is the way to go. But if your solution is stateful and requires state management, applying a functional approach will look unnatural. In the end, it is another great tool for solving specific problems.


1 Answers

The term you're looking for here is Memoization:

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs.

No, functional language do not automatically implement memoization. You can implement it in them, but in C++ as well. It is true, however, that when you write purely functional code (i.e. with no side effects), then memoization is easier. Some dynamic languages (Perl, for instance) have auto-memoization modules that can easily memoize any function. There's a discussion of this subject in the Automatic memoization section of the Wikipedia article.

For example here's a naive C++ Fibonacci:

long fib_rec(long index)
{
    if (index < 2)
        return index;
    else
        return fib_rec(index - 1) + fib_rec(index - 2);
}

And here's a memoized version:

long fib_memoized_aux(vector<long>& cache, long index)
{
    if (cache[index] >= 0)
    return cache[index];

    cache[index] = fib_memoized_aux(cache, index - 1) + fib_memoized_aux(cache, index - 2);
    return cache[index];
}


long fib_memoized(long index)
{
    vector<long> cache(index + 1, -1);
    cache[0] = 0;
    cache[1] = 1;

    return fib_memoized_aux(cache, index);
}
like image 68
Eli Bendersky Avatar answered Nov 16 '22 08:11

Eli Bendersky