我是否正确追踪了延续？

Question

我正在学习延续的概念。我认为一个好主意是在用延续形式编写时跟踪典型的阶乘代码。我想知道我的理解是否正确。

代码：

fact :: Integer -> (Integer -> Integer) -> Integer
fact 0 k = k 1
fact n k = fact $ n-1 (\v -> k (n*v))

-- call: fact 5 id
-- answer: 120

这就是我跟踪代码的方式（我认为能够跟踪它是理解延续如何工作的基础）：

fact 5 id --> 
fact 4 (\v -> id (5*v)) --> 
fact 3 (\v -> (\v -> id (5*v)) (4*v)) --> 
fact 2 (\v -> (\v -> (\v -> id (5*v)) (4*v)) (3*v)) --> 
fact 1 (\v -> (\v -> (\v -> (\v -> id (5*v)) (4*v)) (3*v))) (2*v)) --> 
fact 0 (\v -> (\v -> (\v -> (\v -> (\v -> id (5*v)) (4*v)) (3*v))) (2*v)) (1*v)) --> 
(\v -> (\v -> (\v -> (\v -> (\v -> id (5*v)) (4*v)) (3*v))) (2*v)) (1*v)) 1

这是应该如何追踪的还是我的基本原理错误？

PS：我知道

v

有点令人困惑，但我假设内部

v

遮蔽了外部

v

？

Answer 1

是的，你的基本原理是正确的。唯一有点不正确的是你开始使用的函数。内部

v

确实遮盖了外部

v

，您可以通过打开所有 GHC 警告来发现这一点。为了使事情更容易理解，您可能需要为变量指定唯一的名称。这是我如何编写它，并使用更正后的初始函数：

fact :: Integer -> (Integer -> Integer) -> Integer
fact 0 k = k 1
fact n k = fact (n-1) (\v -> k (n*v))

-- call: fact 5 id
main :: IO ()
main = do
    print $ fact 5 id
    print $ fact 4 (\v0 -> id (5*v0))
    print $ fact 4 (\v0 -> 5*v0)
    print $ fact 4 (\v0 -> 5*v0)
    print $ fact 3 (\v1 -> (\v0 -> 5*v0) (4*v1))
    print $ fact 2 (\v2 -> (\v1 -> (\v0 -> 5*v0) (4*v1)) (3*v2))
    print $ fact 1 (\v3 -> (\v2 -> (\v1 -> (\v0 -> 5*v0) (4*v1)) (3*v2)) (2*v3))
    print $ fact 0 (\v4 -> (\v3 -> (\v2 -> (\v1 -> (\v0 -> 5*v0) (4*v1)) (3*v2)) (2*v3)) (1*v4))
    print $ (\v4 -> (\v3 -> (\v2 -> (\v1 -> (\v0 -> 5*v0) (4*v1)) (3*v2)) (2*v3)) (1*v4)) 1