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

Question

我实际上在一个问题上坐了一个多小时，但没有\xc2\xb4找到解决方案。\n我有这个数据类型：\ntype \'a tree = Empty | Node of \'a * \'a tree * \'a tree

\n\n

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

\n\n

谢谢你！

\n

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, then 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调用。loopidentity

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。你能想办法避免吗？这个练习留给读者。