haskell - 有没有办法避免在插入时复制二叉树的整个搜索路径？

Question

我刚刚开始通过冈崎的 Purely Functional Data Structures 工作。 ，但一直在 Haskell 而不是标准 ML 中做事。但是，我遇到了一个早期练习(2.5)，这让我对如何在 Haskell 中做事感到有些困惑:

Inserting an existing element into a binary search tree copies the entire search path even though the copied nodes are indistinguishable from the originals. Rewrite insert using exceptions to avoid this copying. Establish only one handler per insertion rather than one handler per iteration.

现在，我的理解是，作为一种不纯的语言，ML 使用传统的异常处理方法与 Java 没有太大区别，因此您可以像这样完成它:

type Tree = E | T of Tree * int * Tree

exception ElementPresent

fun insert (x, t) = 
  let fun go E = T (E, x, E)
      fun go T(l, y, r) = 
             if      x < y then T(go (l), x, r)
             else if y < x then T(l, x, go (r))
             else    raise ElementPresent
  in go t
  end 
  handle ElementPresent => t

我没有 ML 实现，所以这在语法方面可能不太正确。

我的问题是，除了在 IO 中做所有事情之外，我不知道如何在 Haskell 中做到这一点。 monad，看起来像是作弊，即使它不是作弊，也会严重限制真正 的函数的有用性不 做任何突变。我可以使用 Maybe单子(monad):

data Tree a = Empty | Fork (Tree a) a (Tree a)
        deriving (Show)

insert     :: (Ord a) => a -> Tree a -> Tree a
insert x t = maybe t id (go t)
  where go Empty   = return (Fork Empty x Empty)
    go (Fork l y r)
      | x < y     = do l' <- go l; return (Fork l' y r)
      | x > y     = do r' <- go r; return (Fork l y r')
      | otherwise = Nothing

这意味着一切都被包裹在 Just 中。在找不到元素时返回的路上，这需要更多的堆分配，并且有点违背了目的。这种分配仅仅是纯度的代价吗？

编辑 补充:很多为什么我想知道 Maybe 的适用性解决方案是，所描述的优化似乎只为您节省了在元素已经存在的情况下所需的所有构造函数调用，这意味着堆分配与搜索路径的长度成正比。 Maybe当元素已经存在时也避免了那些构造函数调用，但是你会得到一个 Just构造函数调用等于搜索路径的长度。我知道足够聪明的编译器可以忽略所有 Just分配，但我不知道当前版本的 GHC 是否真的那么聪明。

Answer 1

在成本方面，ML 版本实际上与您的 Haskell 版本非常相似。

ML 版本中的每个递归调用都会产生一个堆栈帧。在
haskell 版本。这将与您穿越的路径成正比
那个树。此外，如果实际执行插入，两个版本当然会为整个路径分配新节点。

在您的 Haskell 版本中，每个递归调用也可能最终导致
分配一个Just节点。这将在小堆上进行，这只是一个 block
带有凹凸指针的内存。出于所有实际目的，GHC 的次要堆大致等价于
堆栈的成本。由于这些是短暂的分配，它们通常不会结束
完全被移到主堆。