在 Haskell 中使用尾递归拆分 BinTree

Question

所以这周我们在 Haskell 中学习了联合类型、尾递归和二叉树。我们这样定义树数据类型：

data BinTree a = Empty
           | Node (BinTree a) a (BinTree a)
           deriving (Eq, Show)

leaf :: a -> BinTree a
leaf x = Node Empty x Empty

现在我们被要求编写一个函数来找到最左边的节点，return它，将其剪掉，然后 return 没有我们刚刚剪掉的节点的剩余树。

我们做了类似的事情，效果很好：

splitleftmost :: BinTree a -> Maybe (a, BinTree a)
splitleftmost Empty = Nothing
splitleftmost (Node l a r) = case splitleftmost l of
                                 Nothing -> Just (a, r)
                                 Just (a',l') -> Just (a', Node l' a r)

现在我需要使这个函数尾递归。我想我了解尾递归是什么，但发现很难将它应用于这个问题。有人告诉我写一个函数，用合适的参数调用主函数，但仍然无法解决这个问题。

Answer 1

由于节点没有父节点link，一种方法是在列表中维护根到叶的路径。最后可以使用左折叠构造修改后的树：

slm :: BinTree a -> Maybe (a, BinTree a)
slm = run []
    where
    run _ Empty = Nothing
    run t (Node Empty x r) = Just (x, foldl go r t)
        where go l (Node _ x r) = Node l x r

    run t n@(Node l _ _) = run (n:t) l

Answer 2

在这里，为了不破坏任何东西，这里有一些 "tail recursive" 用于沿左右分支求和的函数定义，至少据我所知 "tail recursion":

sumLeftBranch tree = loop 0 tree where
  loop n Empty        = n
  loop n (Node l a r) = loop (n+a) l

sumRightBranch tree = loop 0 tree where
  loop n Empty        = n
  loop n (Node l a r) = loop (n+a) r

你可以看到循环的所有递归使用都将得到与第一次调用相同的答案 loop 0 tree - 参数不断地变得越来越好，直到它们处于理想状态， loop n Empty，也就是 n，想要的总和。

如果这是想要的东西，splitleftmost 的设置将是

splitLeftMost tree = loop Nothing tree 
  where
  loop m              Empty        = m
  loop Nothing        (Node l a r) = loop ? ? 
  loop (Just (a',r')) (Node l a r) = loop ? ?

这里，第一次使用loop的形式是loop Nothing tree，但是和loop result Empty是一样的——到了时候，就是result .我尝试了几次才使 loop ? ? 缺少的参数正确，但是，像往常一样，一旦我得到它们，它们就很明显了。

Answer 3

正如其他人所暗示的那样，在 Haskell 中没有理由使该函数成为尾递归函数。事实上，尾递归解决方案几乎肯定会比您设计的解决方案慢！您提供的代码中潜在的主要低效问题涉及对和Just 构造函数的分配。我相信 GHC（启用优化）将能够弄清楚如何避免这些。我的猜测是它的最终代码可能看起来像这样：

splitleftmost :: BinTree a -> Maybe (a, BinTree a)
splitleftmost Empty = Nothing
splitleftmost (Node l a r) =
  case slm l a r of
    (# hd, tl #) -> Just (hd, tl)

slm :: BinTree a -> a -> BinTree a
    -> (# a, BinTree a #)
slm Empty a r = (# a, r #)
slm (Node ll la lr) a r =
  case slm ll la lr of
    (# hd, tl' #) -> (# hd, Node tl' a r #)

那些看起来很有趣的 (# ..., ... #) 东西是 未装箱的对 ，它们的处理方式与多个 return 值非常相似。特别是，直到最后才分配实际的元组构造函数。通过认识到每次使用非空树调用 splitleftmost 都会产生 Just 结果，我们（因此几乎可以肯定 GHC）可以将空情况与其余情况分开以避免分配中间 Just 构造函数。所以这个最终代码只分配堆栈帧来处理递归结果。由于一些这种堆栈的表示对于解决这个问题本质上是必要的，使用 GHC 的内置的似乎很可能会给出最好的结果。

在 Haskell 中使用尾递归拆分 BinTree

Splitting a BinTree with tail recursion in Haskell

recursion

binary-tree

haskell

tail-recursion