class - 在haskell中定义多类型容器类，麻烦绑定(bind)变量

Question

我在使用 haskell 中的类时遇到问题。

基本上，我有一个算法(一种奇怪的图形遍历算法)作为输入，除其他外，一个容器来存储已经看到的节点(我热衷于避免 monad，所以让我们继续.:))。问题是，该函数将容器作为参数，并且只调用一个函数:“set_contains”，它询问容器是否...包含节点 v。(如果你很好奇，作为参数传入的另一个函数确实实际的节点添加)。

基本上就是想尝试各种数据结构作为参数。然而，由于没有重载，我不能让超过一个数据结构与最重要的 contains 函数一起工作!

所以，我想创建一个“Set”类(我不应该自己动手，我知道)。感谢 Chris Okasaki 的书，我已经设置了一个非常漂亮的红黑树，现在剩下的就是简单地创建 Set 类并声明 RBT 等作为它的实例。

下面是代码:

(注意:代码已大量更新——例如，contains 现在不调用辅助函数，而是调用类函数本身!)

data Color = Red | Black
data (Ord a) => RBT a = Leaf | Tree Color (RBT a) a (RBT a)

instance Show Color where
    show Red = "r"
    show Black = "b"

class Set t where
    contains :: (Ord a) => t-> a-> Bool

-- I know this is nonesense, just showing it can compile.
instance (Ord a) => Eq (RBT a) where
    Leaf == Leaf = True
    (Tree _ _ x _) == (Tree _ _ y _) = x == y

instance (Ord a) => Set (RBT a) where
    contains Leaf b = False
    contains t@(Tree c l x r) b
        | b == x    = True
        | b < x     = contains l b
        | otherwise = contains r b

请注意我如何有一个相当愚蠢定义的 RBT Eq 实例。这是故意的——我从 the gentle tutorial 复制了它(但偷工减料) .

基本上，我的问题归结为:如果我注释掉 Set (RBT a) 的实例化语句，所有内容都会编译。如果我重新添加它，我会收到以下错误:

RBTree.hs:21:15:
    Couldn't match expected type `a' against inferred type `a1'
      `a' is a rigid type variable bound by
          the type signature for `contains' at RBTree.hs:11:21
      `a1' is a rigid type variable bound by
           the instance declaration at RBTree.hs:18:14
    In the second argument of `(==)', namely `x'
    In a pattern guard for
       the definition of `contains':
          b == x
    In the definition of `contains':
        contains (t@(Tree c l x r)) b
                   | b == x = True
                   | b < x = contains l b
                   | otherwise = contains r b

而且我根本无法弄清楚为什么这不起作用。 (附带说明，“包含”函数在别处定义，基本上具有 RBT 数据类型的实际 set_contains 逻辑。)

谢谢! - 阿戈尔

第三次编辑:删除了之前的编辑，合并在上面。

Answer 1

你也可以使用 higher-kinded polyphormism .您的类定义方式有点期望类型 t 具有 kind *。您可能想要的是您的 Set 类采用容器类型，例如您的 RBT 具有类型 * -> *。

您可以轻松修改您的类，通过将 t 应用于类型变量，为您的类型 t 提供一种 * -> * ，如下所示:

class Set t where
    contains :: (Ord a) => t a -> a -> Bool

然后修改您的实例声明以删除类型变量a:

instance Set RBT where
    contains Leaf b = False
    contains t@(Tree c l x r) b
        | b == x    = True
        | b < x     = contains l b
        | otherwise = contains r b

所以，这里是完整的修改后的代码，最后有一个小例子:

data Color = Red | Black
data (Ord a) => RBT a = Leaf | Tree Color (RBT a) a (RBT a)

instance Show Color where
    show Red = "r"
    show Black = "b"

class Set t where
    contains :: (Ord a) => t a -> a -> Bool

-- I know this is nonesense, just showing it can compile.
instance (Ord a) => Eq (RBT a) where
    Leaf == Leaf = True
    (Tree _ _ x _) == (Tree _ _ y _) = x == y

instance Set RBT where
    contains Leaf b = False
    contains t@(Tree c l x r) b
        | b == x    = True
        | b < x     = contains l b
        | otherwise = contains r b

tree = Tree Black (Tree Red Leaf 3 Leaf) 5 (Tree Red Leaf 8 (Tree Black Leaf 12 Leaf))

main =
    putStrLn ("tree contains 3: " ++ test1) >>
    putStrLn ("tree contains 12: " ++ test2) >>
    putStrLn ("tree contains 7: " ++ test3)
    where test1 = f 3
          test2 = f 12
          test3 = f 7
          f = show . contains tree

如果你编译它，输出是

tree contains 3: Truetree contains 12: Truetree contains 7: False