McCarthy 91 函数的工作原理

Question

我根据 McCarthy 91 原则有以下功能：

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

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

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

Answer 1

让我们扩展您的代码：

mc91 85
mc91 (mc91 96)
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... --It is a pattern here
...
mc91 101
91

如果你看到递归调用，你会意识到一旦它达到 100 或更高，它就会减少它，以 (mc91 101) 调用结束，这将为我们带来最后的 91 结果。

Answer 2

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

如果n > 100，那么我们returnn-10；和
在 n <= 100 的情况下，我们计算 n+11，然后我们执行两个额外的步骤。

因此有两种可能 "steps"：一种是我们递减 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 部分，它由两个黑色边缘组成。

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

因此，如果我们从循环中的某个节点开始，我们立即进行红色跳跃，无论我们还需要进行多少次递归调用，我们最终都会在 91 处停止：每次我们做一个完整的循环，我们 "lose" 一个递归调用，所以最终我们将运行剩余的递归调用并在 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

McCarthy 91 函数的工作原理

How McCarthy 91 function works

recursion

haskell

fixpoint-combinators