Haskell中如何使用续体传递风格(CPS)实现二叉树镜像函数

你给出的cpsadd、mult示例都只包含单次递归，因此仅需构造一层lambda续体接住递归返回值即可。但二叉树镜像需要对左右子树做两次独立递归，必须通过嵌套续体串行执行两次递归：第一次递归拿到返回结果后，在它的续体里发起第二次递归，等第二次递归也拿到结果后，再把两个结果组装成新节点，传给最外层传入的续体。
之前两版实现的问题非常明确：

• 第一版没有实际调用mirror处理子树，直接把lambda函数当成左右子树传入Node构造器，完全没有走递归逻辑。
• 第二版传给mirror的参数顺序、内容都不合法，没有明确先处理哪个子树、拿到结果后下一步做什么，自然无法递归触达基例。

和你给出的示例代码风格保持一致，采用类Haskell语法实现：

-- 基例：空树直接将Void传入当前续体
mirror Void k = k Void
-- 非空节点分支
mirror (Node x left right) k =
  -- 第一步：先递归处理原树的右子树（它的镜像会成为新节点的左子树）
  mirror right (\mirroredRight ->
    -- 拿到右子树的镜像结果后，第二步：递归处理原树的左子树（它的镜像会成为新节点的右子树）
    mirror left (\mirroredLeft ->
      -- 两个子树的镜像都计算完成后，组装成新节点，传给外层传入的续体k
      k (Node x mirroredRight mirroredLeft)
    )
  )

调用时只需要传入恒等函数id作为最外层续体（即拿到最终结果后直接返回），比如mirror sampleTree id就能得到sampleTree的镜像。

以两层节点的树Node 1 (Node 2 Void Void) Void为例，调用mirror (Node 1 (Node 2 Void Void) Void) id的执行流程：

1. 进入非空节点分支，首先递归调用mirror Void处理原树的右子树，传入续体为(\mirroredRight -> ...)
2. 命中空树基例，将Void传入上述续体，此时mirroredRight = Void
3. 接着递归调用mirror (Node 2 Void Void)处理原树的左子树，传入续体为(\mirroredLeft -> id (Node 1 Void mirroredLeft))
4. 处理Node 2 Void Void时再次进入非空分支，先递归处理它的右子树Void，拿到mirroredRight = Void，再递归处理它的左子树Void，拿到mirroredLeft = Void，组装成Node 2 Void Void传入续体
5. 此时外层的mirroredLeft = Node 2 Void Void，组装出最终节点Node 1 Void (Node 2 Void Void)，传给最外层的id返回，完全符合镜像的预期结果。

内容的提问来源于stack exchange，提问作者Márquez