haskell - Haskell 中的可变变量？

Question

我开始专注于 Haskell 并做一些令人兴奋的实验。有一件事情我似乎无法理解(也许是以前的“命令式”经验谈话)。最近，我渴望实现整数除法函数，就好像没有乘法/除法运算一样。一个非常有趣的脑筋急转弯，导致了极大的困惑。

divide x y =
    if x < y then 0
    else 1 + divide (x - y) y

我编译了它并且它..有效(!)。这真是令人兴奋。然而，我被告知，我确信变量在 Haskell 中是不可变的。每个递归步骤变量 x 如何保持上一步的值？还是我辉煌的编译器在骗我？为什么它有效？

Answer 1

这里的 x 在一次函数调用期间(即创建后)不会改变 - 这正是immutable方法。发生变化的是多次(递归)调用期间 x 的值。在单个堆栈帧(函数调用)中，x 的值是常量。

一个简单案例的代码执行示例

call divide 8 3 -- (x = 8, y = 3), stack: divide 8 3
step 1: x < y ? NO
step 2: 1 + divide 5 3 
    call: divide 5 3 -- (x = 5, y = 3), stack: divide 8 3, divide 5 3
    step 1: x < y ? NO
    step 2: 1 + divide 2 3
        call divide 2 3 -- (x = 2, y = 3), stack: divide 8 3, divide 5 3, divide 2 3
        step 1: x < y ? YES
        return: 0 -- unwinding bottom call
    return 1 + 0 -- stack: divide 8 3, divide 5 3, unwinding middle call
return 1 + 1 + 0 -- stack: divide 8 3

我知道上面的符号无论如何都没有正式化，但我希望它有助于理解递归是什么，以及 x 在不同的调用中可能有不同的值，因为它只是一个不同的实例整个调用，因此也是 x 的不同实例。