does this Elm Fibonacci example need to be memoized?

Question

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.

Haskell How is this fibonacci-function memoized?
Python What is memoization and how can I use it in Python?

"does lazy evaluation take care of it" <- Elm doesn't have lazy evaluation — robertjlooby, Jan 06 '17 at 19:35

score 5 · Accepted Answer · answered Jan 06 '17 at 16:56

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.

ah! thank you! As usual Elm maps to JavaScript which as none of this nice optimizations other languages have. — john mangual, Jan 06 '17 at 17:07

does this Elm Fibonacci example need to be memoized?

1 Answers1