haskell - McCarthy 91 函数的工作原理

Question

我有以下基于麦卡锡 91 原则的功能:

mc91 :: Integer -> Integer
mc91 n
    | n > 100 = n - 10
    | otherwise = mc91 (mc91 (n + 11))

当我输入序曲 mc91 85 时，我得到了 91。

我无法配置它，它是如何扩展的以及为什么我有 91。

Answer 1

我们先来分析一下函数。有两种情况:

• 案例n > 100 , 然后我们返回 n-10 ;和
• 案例n <= 100 , 然后我们计算 n+11 ，然后我们执行两个额外的步骤。

因此有两个可能的“步骤”:一个是我们递减 10，另一个是我们递增 11。我们可以用图表将其可视化，例如:

第一种情况的边缘用黑色表示，后一种情况的边缘用红色表示。

我们注意到这里有一个循环:92 -> 103 -> 93 -> 104 -> 94 -> 105 -> 95 -> 106 -> 96 -> 107 -> 97 -> 108 -> 98 -> 109 -> 99 -> 110 -> 100 -> 111 -> 101 -> 91 -> ...

让我们现在假设 - 无论原始值如何 - 我们将始终以该循环结束。现在循环总是交织黑色边缘和红色边缘，除了111 -> 101 -> 91。部分，由两条黑边组成。

由于红色边缘引入了两个额外的递归调用，这意味着，如果我们进行红色跳跃，我们将免费获得下一个黑色和红色跳跃。下一个红色跃点将再次向“待办事项列表”添加两个递归调用。因此，如果我们从循环开始，首先进行红色跳跃，我们将继续运行循环。只要我们不采用 111 -> 101 -> 91，这就成立。循环的一部分。由于那是两条黑边，我们可以退出执行的递归调用，从而在 91 处停止。 (因为我们总是在每个红色跃点上获得两个额外的跃点)。

因此，如果我们从循环中的某个节点开始，我们立即进行红色跳跃，无论我们还需要进行多少次递归调用，我们最终都会在 91 处停止:每次我们完成一次完整的跳跃循环，我们“失去”了一个递归调用，所以最终我们将用完剩余的递归调用并在 91 处停止。所以现在我们知道如果我们开始，例如在 94使用任意数量的递归调用，我们将在 91 处停止。

现在我们仍然需要证明 - 给定数字小于 100 - 我们将在循环中结束，并且我们在循环中遇到的第一个节点是红色边缘开始的节点。我们知道 91..100 范围内的所有数字都在循环中。任何小于 91 的数字都会导致红色跳变并增加 11。因此 - 如图中部分所示 - 所有小于 91 的数字最终都会在 [91..100] 范围内结束始终使用红色边缘。

基于上述推理，该函数的更高效版本是:

mc91' n | n > 100 = n-10
        | otherwise = 91

现在对于您给定的示例输入 (85)，我们看到该程序将评估为:

   mc91 85
-> mc91 (mc91 96) -- we are in the loop now
-> mc91 (mc91 (mc91 107))
-> mc91 (mc91 97)
-> mc91 (mc91 (mc91 108))
-> mc91 (mc91 98)
-> mc91 (mc91 (mc91 109))
-> mc91 (mc91 99)
-> mc91 (mc91 (mc91 110))
-> mc91 (mc91 100)
-> mc91 (mc91 (mc91 111))
-> mc91 (mc91 101)
-> mc91 91 -- we reached 91, and thus removed one recursive call
-> mc91 (mc91 102)
-> mc91 92
-> mc91 (mc91 103)
-> mc91 93
-> mc91 (mc91 104)
-> mc91 94
-> mc91 (mc91 105)
-> mc91 95
-> mc91 (mc91 106)
-> mc91 96
-> mc91 (mc91 107)
-> mc91 97
-> mc91 (mc91 108)
-> mc91 98
-> mc91 (mc91 109)
-> mc91 99
-> mc91 (mc91 110)
-> mc91 100
-> mc91 (mc91 111)
-> mc91 101
-> 91 -- we hit 91 a second time, and now the last recursive call is gone