recursion - 使用尾递归从树到有序列表

Question

我实际上花了一个多小时来解决一个问题，但没有找到解决方案。我有这个数据类型:输入“一棵树=空|” 'a * '一棵树 * '一棵树的节点

我必须找到一个函数来转换有序列表中的给定树。也不存在像左 child 必须小于右 child 这样的不变量。我已经找到了“正常”递归解决方案，但没有找到尾递归解决方案。我已经考虑过构建一个无序列表并使用 List.sort 对其进行排序，但这使用了非尾递归的合并排序。也许有人有好的建议。

谢谢!

Answer 1

如果你想按顺序遍历这棵树并返回一个列表，那就意味着我们的函数 inorder必须具有类型 'a tree -> 'a list .

let rec inorder t =
    match t with
      | Empty -> []
      | Node (v, l, r) -> List.append (inorder l) (v :: (inorder r)) (* ! *)

但是List.append位于尾部位置，而不是 inorder 。另一个问题是我们有两次调用inorder 。如果我们输入 inorder l在尾部位置，inorder r不可能处于尾部位置 - 反之亦然。

解决这个问题的一个巧妙方法是连续传递风格。我们将上面的函数转换为一个辅助函数，并为我们的延续添加一个额外的参数 return

(* convert to helper function, add an extra parameter *)
let rec loop t return =
    match t with
        | Empty -> ...
        | Node (v, l, r) -> ...

延续代表“下一步做什么”，因此我们必须将它们传递给延续，而不是直接从函数中发送值。这意味着 Empty案例，我们会 return [] - 而不是简单地[]

let rec loop t return =
    match t with
        | Empty -> return []
        | Node (v, l, r) -> ...

对于Node (v, l, r)在这种情况下，现在我们有了一个额外的参数，我们可以编写自己的延续来通知 loop接下来做什么。因此，要构建我们的排序列表，我们需要 loop l ，然后loop r (反之亦然)，那么我们可以append他们。我们将像这样编写我们的程序。

let rec loop t return =
    match t with
        | Empty -> return []
        | Node (v, l, r) ->
            loop l ... (* build the left_result *)
            loop r ... (* build the right_result *)
            return (List.append left_result (v :: right_result))

在下一步中，我们将填写延续的实际 lambda 语法。

let rec loop t return =
    match t with
        | Empty -> return []
        | Node (v, l, r) ->
            loop l (fun left ->
            loop r (fun right ->
            return (List.append left (v :: right))))

最后，我们定义inorder这是对 loop 的调用默认延续 identity .

let identity x =
    x

let inorder t =
    let rec loop t return =
        match t with
            | Empty -> return []
            | Node (v, l, r) ->
                loop r (fun right ->
                loop l (fun left ->
                return (List.append left (v :: right))))
    in
    loop t identity

如您所见 loop r (fun right -> ...)位于 Node 的尾部位置分支。 loop l (fun left -> ...)位于第一个延续的尾部位置。和List.append ...位于第二个延续的尾部位置。提供List.append是一个尾递归过程，inorder不会增加堆栈。

---

使用 List.append 进行注释对于大树来说可能是一个代价高昂的选择。我们的函数每 Node 调用一次它。你能想办法避免吗？这个练习留给读者。