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

Question

我刚刚开始研究Okasaki的Purely Functional Data Structures,但是我一直在用Haskell而不是Standard ML做事.但是,我遇到了一个早期练习(2.5),让我对如何在Haskell中做事情感到有点困惑:

将现有元素插入二叉搜索树会复制整个搜索路径,即使复制的节点与原始节点无法区分.使用异常重写插入以避免此复制.每次插入只建立一个处理程序,而不是每次迭代一个处理程序.

现在,我的理解是,作为一种不纯洁的语言,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实现,所以这在语法方面可能不太正确.

我的问题是,我不知道这是如何在Haskell做,在做的一切之外IO单子,这似乎是作弊,即使它不是作弊,将严重限制其真正的功能的用处并不做任何突变.我可以使用Maybemonad:

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

在这种情况下,GHC通常不能避免路径复制.但是,有一种方法可以手动完成,而不会产生任何间接/分配成本Maybe.这里是:

{-# LANGUAGE MagicHash #-}

import GHC.Prim (reallyUnsafePtrEquality#)

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

insert :: (Ord a) => a -> Tree a -> Tree a
insert x Empty = Fork Empty x Empty
insert x node@(Fork l y r)
    | x < y = let l' = insert x l in 
        case reallyUnsafePtrEquality# l l' of
            1# -> node
            _  -> Fork l' y r
    | x > y = let r' = insert x r in
        case reallyUnsafePtrEquality# r r' of
            1# -> node
            _  -> Fork l y r'
    | otherwise = node

指针等式函数完全符合名称中的内容.这里是安全的,因为即使相等性返回假阴性,我们只进行一些额外的复制,没有更糟糕的事情发生.

它不是最惯用或最漂亮的Haskell,但性能优势可能非常显着.事实上,这个技巧经常被使用unordered-containers.

Answer 2

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

ML版本中的每个递归调用都会产生堆栈帧.Haskell版本也是如此.这将与您在树中遍历的路径大小成比例.此外,如果实际执行插入,两个版本当然将为整个路径分配新节点.

在您的Haskell版本中,每个递归调用最终也可能导致Just节点的分配.这将进入次要堆,这只是一个带有凹凸指针的内存块.出于所有实际目的,GHC的次要堆与堆栈的成本大致相当.由于这些是短期分配,它们通常不会最终被移动到主堆.