树遍历inorder尾递归

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

并[2,1,3]在电话inorder three []中返回 three = Node (1, Leaf 2, Leaf 3)

Answer 1

从技术上讲,这不是尾递归,因为你有一个非尾inorder right temp位置的递归调用.解决这个问题的一种方法是延续.你编写了一个像以前一样使用累加器的函数,但是累加器只是一个列表,它实际上是一个函数,表示在计算中要做的工作.这意味着我们总是可以尾调用而不是进行非尾调用而只是返回,因为我们需要的上下文被保存到continuation中.

  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)在条目的数量.这里重点是差异列表便宜且易于附加,因此我们将在算法中构造这些并在最后构建具体列表

 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代码中比在语法上使得我们的代码仅使用尾调用(这实际上无法保证空间使用无关).