在结构上强制执行无红色 Children 红色节点

Question

在研究 Learn You A Haskell For Great Good and Purely Functional Data Structures, I thought to try to reimplement a Red Black tree 的同时尝试在结构上强制执行另一个树不变量。

解释 Okasaki 的代码，他的节点看起来像这样：

import Data.Maybe

data Color = Red | Black

data Node a = Node {
    value :: a,
    color :: Color,
    leftChild :: Maybe (Node a),
    rightChild :: Maybe (Node a)}

红黑树的一个属性是a red node cannot have a direct-child red node，所以我尝试将其编码如下：

import Data.Either

data BlackNode a = BlackNode {
    value :: a,
    leftChild :: Maybe (Either (BlackNode a) (RedNode a)),
    rightChild :: Maybe (Either (BlackNode a) (RedNode a))}
data RedNode a = RedNode {
    value :: a,
    leftChild :: Maybe (BlackNode a),
    rightChild :: Maybe (BlackNode a)}

这会输出错误：

Multiple declarations of `rightChild'
Declared at: :4:5
             :8:5


Multiple declarations of `leftChild'
Declared at: :3:5
             :7:5


Multiple declarations of `value'
Declared at: :2:5
             :6:5

我试过对之前的代码进行多次修改，但都编译失败。正确的做法是什么？

Answer 1

不同的记录类型必须有不同的字段名称。例如，这是不允许的：

data A = A { field :: Int }
data B = B { field :: Char }

虽然这没问题：

data A = A { aField :: Int }
data B = B { bField :: Char }

前者会尝试定义两个投影

field :: A -> Int
field :: B -> Char

但是，唉，我们不能有两种类型的名称。（至少，没那么容易……）这个问题在 OOP 语言中不存在，在 OOP 语言中，字段名称永远不能单独使用，但它们必须立即应用于某个对象，如 object.field ——这是明确的，前提是我们已经知道类型object。 Haskell 允许独立投影，使这里的事情变得更加复杂。

后一种方法反而定义了

aField :: A -> Int
bField :: B -> Char

并避免了这个问题。

正如@dfeuer 上面的评论，GHC 8.0 可能会放宽此限制。

在结构上强制执行无红色 Children 红色节点

Structurally Enforcing No Red Children Of Red Node

haskell

red-black-tree

recursive-datastructures