3

作为学习haskell的一部分，我决定写一棵二叉树。

据我了解，如果我对大量插入和删除进行排序，那么当我最终开始评估时，即使结果树相对较小，我也很容易达到堆栈溢出。

这是我的问题：

  1. 我可以通过对我的功能引入一些严格性来避免这种情况吗？（带有 seq / deepseq 的东西？）。

  2. 在哪些情况下，我希望将插入/删除保持在当前状态？

如果您觉得我的代码设计不当或不正确，请随时更正或改进我的代码。

相关代码：

import Data.List

data Tree a = Empty | Branch a (Tree a) (Tree a)
              deriving (Eq)

leaf x = Branch x Empty Empty

-- insert ------------------------------------
treeInsert :: (Eq a, Ord a) => Tree a -> a -> Tree a
treeInsert Empty x  = leaf x
treeInsert (Branch y l r) x | x<y = Branch y (treeInsert l x) r
                            | x>y = Branch y l (treeInsert r x)
                            | otherwise = Branch x l r  --edit


-- delete ------------------------------------
treeDelete :: (Eq a, Ord a) => Tree a -> a -> Tree a
treeDelete Empty _ = Empty
treeDelete (Branch y l r ) x    | y<x   = Branch y l (treeDelete r x)
                                | y>x   = Branch y (treeDelete l x) r
                                | y==x  = del' $ Branch y l r
    where
    -- if this Branch is a leaf dispose of it.
    -- if branch has only one child return the child (skip over).
    -- otherwise, replace this branch with its successor (the leftmost child of the right tree)
    --      successor will be extracted from its original location.
    del' ( Branch y Empty Empty )   = Empty
    del' ( Branch y Empty r )       = r
    del' ( Branch y l Empty )       = l
    del' ( Branch y l r )           = Branch ySucc l rWithout_ySucc

        where
        ( rWithout_ySucc, ySucc ) = leftmost r

            where
            leftmost ( Branch y Empty Empty )   = ( Empty, y )
            leftmost ( Branch y Empty r )       = ( r, y )
            leftmost ( Branch y l r )           = ( Branch y ll r, z ) where ( ll, z ) = leftmost l
4

1 回答 1

0

使结构更严格的典型方法不是使其上的函数更严格，而是改变类型本身。

在这种情况下，我们可以改变

data Tree a = Empty | Branch a (Tree a) (Tree a)

至

data Tree a = Empty | Branch a !(Tree a) !(Tree a)

这将意味着任何时候你有一个Branch，包含的两个Trees 也将被强制到他们的头上。由于a树内部的 s 并不严格，而只是结构本身，所以这被称为spine-strict并且是一个非常典型的模式。

有时您可能不想这样做的原因是，现在您一次为所有操作支付“全部成本”——从树中的五个层次中删除一个元素将强制重建一棵新树的所有五个层次立即执行，而如果您从不需要实际查看这些路径，则它们将永远不会被强迫。

所以有一些结构（冈崎描述得很好）为了获得正确的摊销渐近性能，你不想增加额外的严格性。

事实上，您通常可以通过在使用站点执行严格性来避免堆栈溢出。所以，想象一下你有fold一棵空树，它连续插入了无数个元素。如果您使用严格 foldl'的（即使使用惰性树），那么最终消耗的堆栈将比使用惰性折叠时少得多。

于 2016-03-20T06:39:55.873 回答