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

我们先来分析一下这个功能.有两种情况:

• 在这种情况下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