更新：原来我无意间James窃了詹姆斯·科佩尔（James Koppel）的演讲“您从未听说过的最佳重构”。请认为这是一种真诚的奉承。
今天，我将带您再次走遍程序转换的整个领域。让我们从一个简单的二叉树开始，在叶子中使用未知类型的值以及规范的map函数：
数据T a = L a | B（T a）（T a）映射1 ::（a-> b）-＆gt; T a-＆gt; T bmap1 f（L x）= L（f x）map1 f（B t1 t2）= B（map1 f t1）（map1 f t2）
如您所见，此映射函数在遍历树时正在使用程序堆栈。现在我们的目标是提出一个不使用堆栈的map函数！
为什么？好问题！在Haskell中，对此的需求不大，因为Haskell堆栈与常规数据一样分配在堆上，因此有足够的堆栈空间。但是在其他语言或环境中，堆栈空间可能有硬限制，建议不要使用无限制的堆栈空间。
除此之外，这是一个有趣的练习，这对我来说是足够的理由。
（在下文中，我假设尾部调用（即那些以另一个函数调用结尾但未修改其结果的函数）实际上并未使用堆栈空间。一旦所有递归函数调用均为尾部调用，则代码等效于我们将看到一个命令式循环。）
现在，我们可以只盯着问题（而不是代码），并尝试直接提出解决方案。我们可能会想：“好吧，当我穿过树时，我必须记住我上面的所有节点……所以我需要这些节点的列表……并且对于每个这些节点，我还需要记住我当前是否在处理左孩子，但又要看右边的孩子，或者我是否已经对左孩子做完了……那么关于当前节点，我要记住些什么……？”
……啊，我的大脑已经旋转了。也许最终我会弄清楚，但是为什么要思考何时可以得出解决方案呢？因此，让我们从map1之上开始，然后通过多个机械步骤将其重写为无堆栈的尾递归解决方案。
在开始之前，让我使用本地go帮助器重写map函数，如下所示：
map2 ::全部a b。 （a-＆gt; b）-＆gt; T a-＆gt; T bmap2 f t = go t哪里去:: :: a-> T b go（L x）= L（f x）go（B t1 t2）= B（go t1）（go t2）
这种转换（实际上是“静态参数转换”）具有很大的优势，我们不必一直传递f，并且在复制函数时，我只需要更改顶级名称，而不必更改顶级名称。内部函数的名称。
使用直通传递样式可以将尚未使用尾调用的代码转换为仅使用尾调用的代码，这是一种简单有效的工具。如果我们具有类型...的功能-> t，我们将其转换为类型...->的函数。 （t-> r）-＆gt; r，其中r是我们最后想要的结果类型。这意味着该函数现在会收到一个额外的参数，通常将其命名为k以表示连续，并且该函数调用k x而不是返回某些x。
我们可以将其应用于go函数。在这里，t和r都恰好是T b；成品树的类型：
map3 ::全部a b。 （a-＆gt; b）-＆gt; T a-＆gt; T bmap3 f t = go t（\ r-> r）其中go :: T a-＆gt; （T b-＞ T b）-＆gt; T b go（L x）k = k（L（f x））go（B t1 t2）k = go t1（\ r1-> go t2（\ r2-> k（B r1 r2））））
注意，当最初调用go时，我们将标识函数（\ r-> r）作为初始延续。
las，突然所有函数调用都位于尾部位置，并且此代码不占用堆栈空间！从技术上讲，我们已经完成了，尽管还不能令人满意。所有这些随处可见的lambda会使代码的含义模糊不清，执行起来可能会有点慢，而且，我们还没有真正学到很多东西。当然，这不是我们在“认真思考”之后编写的代码。
因此，让我们继续将代码重写为更漂亮，更简单的代码。像这样不使用lambda的东西。
同样，有一种机械技术可以提供帮助。它可能不会使代码更漂亮，但是它将摆脱lambda，因此请稍后进行清理。
该技术称为去功能化（因为它用纯数据值替换了功能值），并且可以看作是一种改进形式。
请注意，我们绕过类型（T b-> T b）的值，但我们当然不是指完整类型（T b-> T b）。取而代之的是，在我们的程序中仅出现该类型的非常具体的值，因此让我们用仅包含我们实际使用的值的代表的数据类型替换（T b-> T b）。
我们引入了一个解释函数，它将K转换回a（T b-> T b）： 在函数go中，我们取一个K，而不是取类型（T b-> T b）的参数。当我们实际使用延续时，我们必须使用eval将K返回到该函数： 去:: T a-＆gt; K a b-＆gt; T bgo（L x）k =估计值k（L（f x））go（B t1 t2）k = go t1 K1 我们还对第一步中确定的代码片段执行此操作。 这些变成： 现在，我们完成eval函数：对于每个构造函数，我们只需将其映射到步骤1中对应的lambda： 评估:: K-＆gt; （Tb-＆gt; T b）eval I =（\ r-> r）eval K1 =（\ r1-> go t2 K2）eval K2 =（\ r2-> eval k（B r1 r2）） 尚不完全有效：我们在右侧有未绑定的变量（t2，r1，k）。 因此，根据需要将它们添加到构造函数K1和K2中。 这也改变了类型K本身。 现在需要使用类型参数。
数据K a b = I | K1（T a）（K a b）| K2（T b）（K a b）map4 ::全部a b。 （a-＆gt; b）-＆gt; T a-＆gt; T bmap4 f t = go t我在哪里:: :: a-> K a b-＆gt; T b go（L x）k ＝ eval k（L（f x））go（B t1 t2）k ＝ go t1（K1 t2 k）eval :: K a b-> （Tb-> T b）eval I =（\ r-> r）eval（K1 t2 k）=（\ r1-> go t2（K2 r1 k））eval（K2 r1 k）=（\ r2-> eval k（B r1 r2））
并不是真的更干净或更漂亮，但是所有内容仍然是尾递归的，并且我们现在正在使用纯数据。
为了稍微清理一下，我们可以注意到K数据类型实际上只是一个值列表，其中值是T a或T b。为此，我们不需要自定义数据类型！除了使用K之外，我们还可以使用根据标准数据类型构建的以下内容：
现在我用[]替换I，用Left t2：k替换K1 t2 k并用Right r1：k替换K2 r1 k。我也非常有启发性地重命名了go down和eval up
map5 ::全部a b。 （a-＆gt; b）-＆gt; T a-＆gt; T bmap5 f t = down t []其中down :: T a-> K＆＃39; a b-＆gt; T b向下（L x）k =向上k（L（f x））向下（B t1 t2）k =向下t1（左t2：k）向上:: K＆＃39; a b-＆gt; b T b向上[] r = r向上（左t2：k）r1 =向下t2（右r1：k）向上（右r1：k）r2 =向上k（B r1 r2）
此时，代码突然变得更加有意义。实际上，我可以尝试将其表达出来：
遍历树时，我们必须记住所有父节点，返回树时是否还有剩下要做的事情（因此我们记得一个T a），或者是否已经完成了（所以我们有一个T b）。这是列表K＆＃39;一个b。
我们开始沿着树的左边走（注意右边的兄弟姐妹仍然要做），直到碰到叶子为止。我们将叶子变形，然后上升。
如果我们上升并扎根，那就完成了。否则，如果我们向上走，还有一些事情要做，我们会记住刚刚处理过的子树（因为它已经是Right形式了），然后走下另一个子树。但是，如果我们向上走，没有什么可做的，则将两个子树放在一起，然后继续向上走。
在这一点上，我们可以停止：代码很漂亮，很有意义并且具有我们想要的属性。但是，让我们将拨盘再转一点，尝试使其成为必要的循环。
我们知道，如果只有一个尾递归函数，则相当于一个循环，该函数的参数变为可变变量。但是我们有两个功能！
事实证明，如果您有两个功能，则-> r和b-＆gt; r具有相同的返回类型（它们在这里必须具有，因为我们将CPS进一步转换了它们），则这两个函数等效于带有“ a或b”的单个函数，即a b->河实际上，除了Ra a⋅level r b = r a + b的高中代数规则外，别无其他。
因此（在将down的参数重新排序以将T b首先放置之后），我们可以将代码重写为
map6 ::全部a b。 （a-＆gt; b）-＆gt; T a-＆gt; T bmap6 f t = go（左t）[]其中go ::任一（T a）（T b）-> K＆＃39; a b-＆gt; T b去（左（L x））k =去（右（L（fx）））k去（左（B t1 t2））k =去（左t1）（左t2：k）去（右r） [] = r go（右r1）（左t2：k）= go（左t2）（右r1：k）go（右r2）（右r1：k）= go（右（B r1 r2））k
你看到循环了吗？如果不是这样，将其与以下等效的命令式伪代码进行比较可能会有所帮助：
mapLoop ::全部a b。 （a-＆gt; b）-＆gt; T a-＆gt; T bmapLoop f t {var node = Left t; var parents = []; while（true）{开关（节点）{左（L x）->节点：=右（L（f x））左（B t1 t2）->节点：=左t1; parent.push（左t2）右r1-> {如果（parents.len（）== 0）{返回r1; } else {切换（parents.pop（））{左t2->节点：=左t2; parent.push（右r1）;右r2->节点：=右（B r1 r2）}}}}}}
我发现看到一系列非常机械的转换如何将非常不同的方法（递归，惰性函数和命令式循环）联系起来，这很有启发性。重构代码时，查看是否可以将重构概念化为那些机械步骤之一（细化，类型等效，去功能化，cps转换等）会很有帮助。
如果您喜欢这篇文章，那么您可能会喜欢我的演讲《 isOrderedTree的许多面孔》，我已在MuniHac 2019和Haskell Love 2020上发表过。
您可能已经对此很熟悉，但是这个想法可以追溯到Reynolds的“高阶语言的定义解释器”。他的目的是避免依赖于定义的解释器，具体取决于它所定义的语言的详细信息。评估顺序。
然后，在双重论文“评估者和抽象机之间的功能对应”和“从解释器到编译器和虚拟机：功能派生”中，重点关注了Olivier Danvy和Darius Biernacki等人。
此后的几年中，有几篇论文在不同的背景下使用了相同的想法，我在这里收集了这些文章：http://lambda-the-ultimate.org/node/2423#comment-38384
我以类似的方式使用此技术来解释GCC优化，出于相同的原因，在这里我经历了与您几乎相同的推导。 Danvy（和Nielsen）的“工作中的去功能化”也显示了类似的示例以及其他示例，包括这些转换的双向性。
最后，结果不是“无堆栈”。只是我们已使堆栈显式化，即K＆＃39;是堆栈。当然，众所周知，可以通过显式堆栈消除递归，而CPS转换后再进行去功能化是显示此问题的较好方法之一。对CPSed代码进行反功能化将始终产生与列表同形的类型，即堆栈（如果没有递归，则更简单）。如果原始代码具有诸如callCC之类的控制运算符，则这将是不正确的。
无论如何，这种将控制结构转换为显式数据结构的转换通常确实非常具有启发性。它还具有合理的可逆性，使您能够以高级方式理解和/或重新实现低级代码。