树到有尾递归的有序列表 [英] Tree to ordered list with tail recursion

问题描述

实际上，我在一个问题上坐了一个多小时，却没有找到解决方案. 我有这种数据类型: type 'a tree = Empty | Node of 'a * 'a tree * 'a tree

I am actually sitting over a hour on a problem and don´t find a solution for it. I have this data type: type 'a tree = Empty | Node of 'a * 'a tree * 'a tree

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

And i have to find a function which converts a given tree in a ordered list. There is also no invariant like that the left child has to be less then the right. I already found a "normal" recursion solution but not a tail recursive solution. I already thought about to build a unordered list and sort it with List.sort, but this uses a merge sort which is not tail recursive. Maybe someone has a good advice.

谢谢！

推荐答案

如果要按顺序遍历树 并返回 list ，则意味着我们的函数inorder必须为'a tree -> 'a list类型.

If you want to traverse the tree in order and return a list, that means our function inorder must have the type '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不可能处于尾部位置，反之亦然.

However List.append is in tail position, not inorder. Another problem is we have two calls to inorder. If we put inorder l in tail position, inorder r could not possibly be in tail position - and vice versa.

解决此问题的一种好方法是连续传递样式.我们将函数带到上方，然后将其转换为带有附加参数的辅助函数，用于我们的延续return

A neat way to work around this problem is continuation passing style. We take our function above and convert it into a helper function with an extra parameter for our continuation, return

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

延续表示下一步做什么" ，因此，与其直接从我们的函数中发送值，不如将其交给延续.这意味着对于Empty情况，我们将return []-而不是简单的[]

The continuation represents "what to do next", so instead of sending values directly out of our function, we must hand them to the continuation instead. That means for the Empty case, we'll return [] - instead of simply []

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

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

For the Node (v, l, r) case, now that we have an extra parameter we can write our own continuation that informs loop what to do next. So to construct our sorted list, we will need to loop l, then loop r (or vice versa), then we can append them. We'll write our program just like this.

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语法.

In this next step, we'll fill in the actual lambda syntax for the continuations.

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.

Last, we define inorder which is a call to loop with the default continuation, 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不会增加堆栈.

As you can see loop r (fun right -> ...) is in tail position for the Node branch. loop l (fun left -> ...) is in tail position of the first continuation. And List.append ... is in tail position of the second continuation. Provided List.append is a tail-recursive procedure, inorder will not grow the stack.

请注意，对于大树而言，使用List.append可能是一个昂贵的选择.我们的函数每个Node调用一次.您能想到一种避免的方法吗?本练习留给读者.

Note using List.append could be a costly choice for big trees. Our function calls it once per Node. Can you think of a way to avoid it? This exercise is left for the reader.

这篇关于树到有尾递归的有序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！