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

Question

首先,我有两个不同的实现,我认为是正确的,并且已经对它们进行了描述并认为它们具有相同的性能:

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 

我只是想知道是不是人们都在谈论尾部递归如何有利于性能？很多问题都在我脑海中浮现:

1. 如何让深度功能更快？
2. 我读到了关于Haskell的懒惰如何减少尾递归的需要,是真的吗？
3. 事实是每个递归都可以转换成尾递归吗？
4. 最后,尾递归可以更快,更节省空间,因为它可以转换为循环,从而减少了推送和弹出堆栈的需要,我的理解是正确的吗？

Answer 1

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陈述进行了贬义)并重新安排了一下

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

所以你看到在返回之前调用的最后一个函数是max,这意味着它也不是尾递归的.

你怎么能让它尾递归？

您可以使用延续传递样式创建尾递归函数.你不是重写你的函数来获取状态或累加器,而是传入一个函数(称为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,所以这个函数是尾递归的.

那是吗？

(注意本节从前一个问题的答案中得出.)

没有!这个"技巧"只会将问题推回到其他地方.我们现在有一个尾递归函数来代替使用大量堆栈空间的非尾递归函数,它会吞噬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在末尾位置-因此它们是一对相互尾递归函数.因此,我们将使用延续传递样式的函数的版本转换为使用数据表示延续的函数,并使用一对相互递归的函数来解释该数据.

那听起来真的很复杂

好吧,我想是的.可是等等!我们可以简化它!如果你看一下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,而右侧树总是被推到调用堆栈以便稍后进行探索.eval当Empty到达分支并且可以丢弃时,参数仅从调用堆栈(in )中弹出.

好吧......别的什么？

好吧,一旦你注意到你可以将延续传递算法变成一个模仿调用堆栈并首先遍历树深度的版本,你可能会开始怀疑是否有一个更简单的算法首先遍历树深度,保持跟踪到目前为止遇到的最大深度.

确实有.诀窍是保留一个尚未探索的分支列表及其深度,并跟踪到目前为止您已经看到的最大深度.看起来像这样

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答案中的部分尾递归函数,这将有助于树木非常不平衡的情况.

Answer 2

部分尾递归版本是这样的：

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 答案中更复杂的完整情况相反）只是为了跳过不完整的分支。

但是，假设您的树的深度最多为两位数，这应该就足够了。事实上，如果你适当地平衡你的树，这应该没问题。如果您的树，OTOH，用于退化为列表，那么这已经有助于避免堆栈溢出（这是我尚未证明的假设，但对于没有分支且 2 个非空的完全退化的树来说，这当然是正确的孩子们。）。

尾递归本身并不是一种美德。只有当我们不想用命令式编程语言中的简单循环来爆炸堆栈时，这才是重要的。