可以严格指导递归吗？

Question

假设我们在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

对于非常大的数字,我们希望此算法失败并出现"堆栈大小溢出"错误.这是因为算法是二进制递归,而不是尾递归.我可以用爆炸模式(对得到的左子树"(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'一样简单吗？或者二进制折叠是否会增加额外的问题？

Answer 1

我假设你打算创建一个非常深的树,比如

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不涉及递归调用.检查根节点后,将调用递归调用,但同样只调用一个级别.这意味着检查每个节点仅花费一些有限的时间和内存(在这种情况下是常量),而不依赖于树的深度.重要的属性是每个递归调用都在构造函数中.这有时称为corecursion或guarded递归.

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