Haskell：二叉树深度的尾递归版本

Question

Haskell：二叉树深度的尾递归版本

haskellrecursiontreebinary-treetail-recursion

11

首先，我有两种不同的实现方法，我认为它们都是正确的，并对它们进行了性能分析，发现它们的性能大致相同：

depth::Tree a -> Int
depth Empty        = 0
depth (Branch b l r) = 1 + max (depth l) (depth r)


depthTailRec::Tree a -> Int
depthTailRec = depthTR 0 where
           depthTR d Empty          = d 
           depthTR d (Branch b l r) = let dl = depthTR (d+1) l; dr = depthTR (d+1) r in max dl dr

我在想，人们不是一直在谈论如何通过尾递归来提高性能吗？这让我产生了很多问题：

如何使深度函数更快？
我读到有关Haskell的惰性如何减少对尾递归的需求的内容，这是真的吗？
每个递归都可以转换成尾递归，这是真的吗？
最后，我的理解是尾递归可以更快、更节省空间，因为它可以转换成循环，从而减少推入和弹出堆栈的需要，这是正确的吗？

- Bob Fang

3

你的函数不是尾递归的。但在这种情况下你不需要担心它。因为需要调用自身两次才能得到结果的函数并不容易变成尾递归函数。 - Ingo

@lngo您能详细说明为什么这不是尾递归吗？有关于尾递归的好资料吗？谢谢。 - Bob Fang

因为在depthTailRec中必须进行的最后一个函数调用以获得结果不是depthTailRec而是max。 - Ingo

关于第二点“懒惰”，有什么评论吗？也想听听您的看法。 - Yogesh Sajanikar

如果有一个无栈实现的Haskell，那么通常情况下对树进行递归迭代就不会成为问题，因为你无论如何都无法保持恒定的空间。这里的一些评论谈到了这种情况：http://lambda-the-ultimate.org/node/2673 - CMCDragonkai

3个回答

5

一个部分尾递归版本如下：

depth d Empty = d
depth d (Branch _ l Empty) = depth (d+1) l
depth d (Branch _ Empty r) = depth (d+1) r
depth d (Branch _ l r)     = max (depth (d+1) l) (depth (d+1) r)

请注意，这里的尾递归（与Chris答案中更复杂的完整情况相反）仅用于跳过不完整的分支。

但是，在假设您的树的深度最多为双位数的情况下，这应该已经足够了。实际上，如果您的树被正确平衡，那么这应该是可以的。如果您的树倾向于退化成列表，则这已经有助于避免堆栈溢出（我没有证明这个假设，但对于一个没有2个非空子节点的分支的完全退化的树而言，这肯定是正确的）。

尾递归本身并不是一种美德。它只在我们不想通过在命令式编程语言中使用简单循环来扩大堆栈时才显得重要。

- Ingo

2

针对您的第3点，是的，例如通过使用CPS技术（如Chris的答案中所示）；

针对您的第4点，正确。

针对您的第2点，使用懒惰的核心递归广度优先树遍历，我们自然地得到了与Chris最后一个解决方案类似的解决方案（即他的＃5，使用显式堆栈的深度优先遍历），甚至不需要调用max：

treedepth :: Tree a -> Int
treedepth tree = fst $ last queue
  where
    queue = (0,tree) : gen 1 queue

    gen  0   p                     = []
    gen len ((d,Empty)        : p) =                     gen (len-1) p 
    gen len ((d,Branch _ l r) : p) = (d+1,l) : (d+1,r) : gen (len+1) p

尽管这两种变体在最坏情况下的空间复杂度都是O(n)，但最坏情况本身是不同的，而且互为相反：最退化的树对于深度优先遍历（DFT）而言是最坏情况，对于广度优先遍历（BFT）而言是最好的情况（从空间角度来看）；同样地，最平衡的树对于DFT而言是最好的情况，对于BFT而言则是最坏的情况。

- Will Ness

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris Taylor · Accepted Answer

1. 为什么你的函数不是尾递归的？

一个递归函数要是尾递归，所有的递归调用都必须在尾位置。如果一个函数是在返回前被调用的最后一个函数，则它处于尾位置。在你的第一个例子中：

depth (Branch _ l r) = 1 + max (depth l) (depth r)

这相当于

depth (Branch _ l r) = (+) 1 (max (depth l) (depth r))

在该函数返回前调用的最后一个函数是 (+)，因此这不是尾递归。在您的第二个示例中，您有：

depthTR d (Branch _ l r) = let dl = depthTR (d+1) l
                               dr = depthTR (d+1) r
                            in max dl dr

这相当于（一旦您重新将所有的let语句转换为lambda表达式并稍作调整）。

depthTR d (Branch _ l r) = max (depthTR (d+1) r) (depthTR (d+1) l)

现在，在返回之前调用的最后一个函数是max，这意味着它也不是尾递归。

2. 如何使其成为尾递归？

您可以使用传递风格使函数成为尾递归。与其重新编写函数以接受状态或累加器，不如传递一个函数（称为continuation），该函数是对计算值执行的指令 - 即，而不是立即返回给调用者，将计算出的任何值传递给续集。这是将任何函数转换为尾递归函数的简单技巧，即使需要多次调用自身的函数（如depth）也可以。它看起来像这样。

depth t = go t id
 where
   go  Empty         k = k 0
   go (Branch _ l r) k = go l $ \dl ->
                           go r $ \dr ->
                             k (1 + max dl dr)

现在您可以看到，在go返回之前调用的最后一个函数是它自己的go函数，因此此函数是尾递归的。

3. 就这样了吗？

（注意，本节内容摘自这个先前的问题的答案。）

不！这个“技巧”只是把问题推到别的地方。我们现在有了一个吃掉thunks（未应用函数）的尾递归函数，而这些thunks可能会占用大量空间。幸运的是，我们不需要使用任意函数——实际上，只有三种类型：

1. \dl -> go r (\dr -> k (1 + max dl dr))（使用自由变量r和k） 2. \dr -> k (1 + max dl dr)（使用自由变量k和dl） 3. id（没有自由变量）

由于只有有限数量的函数，我们可以将它们表示为数据。

data Fun a = FunL (Tree a) (Fun a)  -- the fields are 'r' and 'k'
           | FunR  Int     (Fun a)  -- the fields are 'dl' and 'k'
           | FunId

我们需要编写一个名为eval的函数，以告诉我们如何在特定参数下评估这些“函数”。现在，您可以将函数重新编写为：

depth t = go t FunId
 where
  go  Empty         k = eval k 0
  go (Branch _ l r) k = go l (FunL r k)

  eval (FunL r  k) d = go r (FunR d k)
  eval (FunR dl k) d = eval k (1 + max dl d)
  eval (FunId)     d = d

请注意，go和eval都调用了go或eval，处于尾位置 - 因此它们是一对相互尾递归的函数。因此，我们将使用延续传递样式的函数版本转换为使用数据表示延续，并使用一对相互递归的函数来解释该数据。

2. 这听起来真的很复杂

嗯，我想确实如此。但等等！我们可以简化它！如果您查看Fun a数据类型，您会发现它实际上只是一个列表，其中每个元素都是要计算深度的Tree a，或者是表示我们已经计算出的深度的Int。

注意到这一点的好处是什么？嗯，这个列表实际上代表了前一节中连续的延续链的调用堆栈。将新项目推送到列表上就是将新参数推送到调用堆栈上！因此，您可以写：

depth t = go t []
 where
  go  Empty         k = eval k 0
  go (Branch _ l r) k = go l (Left r : k)

  eval (Left r   : k) d = go   r (Right d : k)
  eval (Right dl : k) d = eval k (1 + max dl d)
  eval  []            d = d

每个新的参数都被推到调用栈上，类型为Either (Tree a) Int。随着函数递归，它们不断地将新的参数推到栈上，这些参数要么是要探索的新树（每次调用go时），要么是迄今为止找到的最大深度（每次调用eval时）。

这种调用策略表示树的深度优先遍历，因为你可以看到左树总是首先被go探索，而右树总是被推到调用栈中以稍后探索。只有在到达Empty分支并且可以丢弃时，才会从调用栈中弹出参数（在eval中）。

5. 好的...还有什么别的吗？

嗯，一旦你注意到可以将传递续延算法转化为模拟调用栈并深度优先遍历树的版本，你可能会想知道是否有一种更简单的算法，它可以深度优先遍历树，并跟踪迄今为止遇到的最大深度。

实际上，是有的。诀窍是保持一个尚未探索的分支列表，以及它们的深度，并跟踪到目前为止看到的最大深度。它看起来像这样

depth t = go 0 [(0,t)]
 where
  go depth  []    = depth
  go depth (t:ts) = case t of
    (d, Empty)        -> go (max depth d)  ts
    (d, Branch _ l r) -> go (max depth d) ((d+1,l):(d+1,r):ts)

我认为在保证其尾递归的限制下，这个函数已经足够简单了。

6. 那么我应该使用它吗？

老实说，你原来的非尾递归版本可能已经很好了。新版本并没有更加节省空间（它们总是需要存储下一个要处理的树的列表），但它们有一个优点，就是将要处理的树存储在堆上，而不是在栈上，堆上有更多的空间。

你可能想看一下Ingo答案中的部分尾递归函数，它可以在树极不平衡的情况下提供帮助。