这个 Elm 斐波那契数列的例子需要进行记忆化吗？

Question

这是Elm语法页面上的斐波那契代码。我很好奇，递归需要进行备忘录处理吗，还是由惰性求值来处理?

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

在其他语言（如Python）中，函数调用的次数会呈指数级增长，因此如果 f(30) 计算类似于 4000 次或者其他次数的 f(10)。

• Haskell 如何对这个斐波那契函数进行备忘录化？

• Python 什么是备忘录化以及如何在Python中使用它？

- john mangual

---

「懒惰求值是否会处理这个问题」<- Elm 没有懒惰求值 - robertjlooby

Answer 1

浏览编译后的源代码（截至Elm 0.18版本），您将看到Elm代码被转译为以下JavaScript代码（变量名称可能不同）。

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不会自动进行记忆化，因为函数调用不能保证是确定性的。如果您需要记忆化，您将不得不自行实现。

- Chad Gilbert

---

啊！谢谢！像往常一样，Elm 映射到 JavaScript，但它没有其他语言所拥有的这些优化。 - john mangual