1

假设我们在 Haskell 中有一个简单的树创建算法：

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

makeTree :: Tree Int -> Tree Int
makeTree (Node 0 l r) = Node 0 EmptyTree EmptyTree
makeTree (Node n l r) = Node n (makeTree $ newTree (n - 1))
                               (makeTree $ newTree (n - 1))
  where
    newTree n = Node n EmptyTree EmptyTree

对于非常大的数字，我们预计该算法会因“堆栈大小溢出”错误而失败。这是因为该算法是二进制递归的，而不是尾递归的。我可以使用 bang 模式（在生成的左子树“！（makeTree $ newTree (n - 1))”上）将二进制递归引导为尾递归，因为由于严格性，现在应该指导递归？

编辑：

事实证明，真正的问题不是树的创建，而是消耗树的函数。还有一个函数是用来展平树的，其中的实例如下：

import qualified Data.Foldable as F

instance F.Foldable Tree where
    foldMap f EmptyTree = mempty
    foldMap f (Node x l r) = F.foldMap f l `mappend`
                             f x           `mappend`
                             F.foldMap f r

flatten = F.foldMap (:[])

因此调用了树的展平，并且可能在这里发生溢出。如果是这样，解决方案是否像假设将 foldl 转换为 foldl' 一样简单？还是二进制折叠会增加额外的问题？

4

1 回答 1

6

我假设您打算创建一棵非常深的树，例如

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

makeTree :: Int -> Tree Int
makeTree 0 = EmptyTree
makeTree n = Node n (makeTree (n - 1)) (makeTree (n - 1))

关键是 Haskell 是懒惰的。因此，在调用该函数之后，实际上并没有创建任何内容，除了在需要时评估的thunk 。堆栈上没有分配任何内容，因为调用makeTree不涉及递归调用。在检查根节点之后，调用递归调用，但同样只有一层。这意味着检查每个节点只需要一些有限的时间和内存（在这种情况下是常数），而不取决于树的深度。重要的属性是每个递归调用都在构造函数中。这有时称为核心递归或保护递归。

在使用树的函数中可能会发生堆栈溢出，但这是另一回事。

于 2013-07-28T15:54:51.480 回答