什么是表示红黑树的最有效方法？

Question

冈崎使用(基本上)

data Color = R | B
data RB a = L | T {-# UNPACK #-}!Color !(RB a) !a !(RB a)

我知道在C中,颜色通常以更加繁琐的方式处理以节省空间,做一些事情,比如使指针的低位代表颜色(我想通常指向节点的指针会编码它的颜色,但它也会可以通过使左或右指针来模拟Okasaki的结构从一个节点代表它颜色).

显然,在Haskell中这种小小的变化是不可能的.那么,如何在Haskell中最有效地表示节点？

data RB' a = L | B !(RB a) !a !(RB a) | R !(RB a) !a !(RB a)

似乎可能是合理的内存效率,但它似乎也可能使模式匹配相当冗长.

Answer 1

只能解包单个构造函数数据类型，并且无法对多态构造函数进行“通用解包”。下面的单类型树结构实际上将使用指针标记来存储。它有 3 个构造函数，其中之一是空的，不会包含任何取消引用。顺便说一句，GHC 似乎有优化的机会，但我认为没有。理论上data Foo = A | B | C | ... Z可以表示为 26 个不同的保留指针值。然而我离题了。

data RB' a = L | B !(RB a) !a !(RB a) | R !(RB a) !a !(RB a)

上面的类型将被表示为标记指针，并且模式匹配将非常有效。我想这就是你提到记忆时所指的。如果您知道 的值a，则可以使用关联的数据类型（数据族）来编写更高效的构造函数。Don Stewart 的文章《自我优化数据结构：使用类型使列表更快》是这方面的绝佳资源。

数据族可以让你表达类似这样的东西：

class AdaptRedBlackTree a where
  data RBTree a

  empty :: a
  insert :: a -> Tree a -> Tree a
  ...

instance RedBlackTree Int where
  data RBTree Int = RBEmptyInt 
                  | LInt (RBTree Int)
                         {-# UNPACK #-} Int
                         (RBTree Int) 
                  | RInt (RBTree Int)
                         {-# UNPACK #-} Int
                         (RBTree Int)

不幸的是，进一步拆包将很困难，但至少您可以避免对Int值的取消引用。