CODEWITHSUNDEEP
dynamic-programmingelmmemoization
john mangual
john mangual

Reputation: 8172

does this Elm Fibonacci example need to be memoized?

Here is the Fibonacci code on the Elm syntax page. Just curious does recursion need to be memoized or does lazy evaluation take care of it?

fib n = case n of
  0 -> 1
  1 -> 1
  _ -> fib (n-1) + fib (n-2)

In other languages (such as Python) the number of function calls would grow exponentially in n so that in if f(30) would compute f(10) like 4000 times or someting.

Upvotes: 4

Views: 357

Answers (1)

Chad Gilbert
Chad Gilbert

Reputation: 36375

Viewing the compiled source (as of Elm 0.18), you'll see that the Elm code gets transpiled down to the following javascript code (the variable names may differ).

var _user$project$Temp1483721371847322$fib = function (n) {
    var _p0 = n;
    switch (_p0) {
        case 0:
            return 1;
        case 1:
            return 1;
        default:
            return _user$project$Temp1483721371847322$fib(n - 1) + _user$project$Temp1483721371847322$fib(n - 2);
    }
};

Javascript does no automatic memoization since function calls are not guaranteed to be deterministic. If you require memoization, you will have to roll your own.

Upvotes: 5

Related Questions