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

Question

冈崎使用(基本上)

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

我知道在 C 中，颜色通常以更复杂的方式处理以节省空间，例如使指针的低位代表颜色(我认为通常指向节点的指针对其颜色进行编码，但它也将是可以通过使节点的左指针或右指针代表其颜色来模仿冈崎的结构)。

显然，在 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 的文章 Self-optimizing data structures: using types to make lists faster 是这方面的一个很好的资源。 .

数据系列将允许您表达类似于以下内容的内容:

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 的取消引用。值。