树遍历中序尾递归

Question

我是否正确地使用尾递归实现了中序层序树遍历？

inorder (Leaf n) temp = n:temp
inorder (Node (n, left, right)) temp = inorder left (n:inorder right temp)
inorder :: Tree a -> [a] -> [a]

树被声明为

data Tree a = Leaf a | Node (a, Tree a, Tree a) deriving Show

和returns [2,1,3] 待命 inorder three [] 其中 three = Node (1, Leaf 2, Leaf 3)

Answer 1

从技术上讲，这不是尾递归，因为您在非尾位置进行了递归调用 inorder right temp。解决这个问题的一种方法是使用延续。你写了一个函数，它像以前一样接受一个累加器，但累加器不仅仅是一个列表，它实际上是一个函数，代表计算中剩下的工作。这意味着我们可以始终进行尾调用，而不是进行非尾调用并返回，因为我们需要的上下文已保存到延续中。

  inorder = go id
    where go :: ([a] -> r) -> Tree a -> r
          go k Leaf = k []
          go k (Node a l r) = go l (\ls -> go r (\rs -> k $ ls ++ n : rs))

这里的每个调用都是按要求进行的尾调用，但效率很低，因为它需要在每个级别进行 ++ 操作，将我们推向二次成本。更高效的算法会避免构建显式列表，而是构建差异列表，延迟具体结构的构建并给出更高效的算法

type Diff a = [a] -> [a] -- A difference list is just a function

nil :: Diff a
nil xs = xs

cons :: a -> Diff a -> Diff a
cons a d = (:) a . d

append :: Diff a -> Diff a -> Diff a
append xs ys = xs . ys

toList :: Diff a -> a
toList xs = xs []

请注意，所有这些操作都是 O(1) 除了 toList，它的条目数是 O(n)。这里的重点是 diff 列表便宜且易于附加，因此我们将在我们的算法中构建这些列表并在最后构建具体列表

 inorder = go toList
    where go :: (Diff a -> r) -> Tree a -> r
          go k Leaf = k nil
          go k (Node a l r) = 
             go l (\ls -> go r (\rs -> k $ ls `append` cons n rs))

现在，通过无偿应用函数，我们得到了一个完全不惯用的 Haskell 程序。您在 Haskell 中看到我们并不真正关心尾调用，因为我们通常希望正确处理无限结构，如果我们要求一切都是尾递归，那实际上是不可能的。事实上，我会说虽然不是尾递归，但您最初拥有的代码是最惯用的，甚至在 Data.Set 中也是如此实现的！它有属性，我们可以懒惰地使用 toList 的结果，它会与我们一起工作并懒惰地处理树。所以在你的实现中，像

min :: Tree a -> a
min = listToMaybe . toList

将非常接近您手动实现它的效率！它不会像我的版本那样首先构造遍历整棵树。这些惰性的组合效应在实际 Haskell 代码中比在语法上使我们的代码仅使用尾调用（无论如何实际上无法保证 space 使用）带来更多好处。

树遍历中序尾递归

Tree traversal inorder tail recursion

haskell

tail-recursion