在haskell中定义多类型容器类，解决了绑定变量的问题

I'm having trouble with classes in haskell.

我在haskell的课上遇到麻烦。

Basically, I have an algorithm (a weird sort of graph-traversal algorithm) that takes as input, among other things, a container to store the already-seen nodes (I'm keen on avoiding monads, so let's move on. :)). The thing is, the function takes the container as a parameter, and calls just one function: "set_contains", which asks if the container... contains node v. (If you're curious, another function passed in as a parameter does the actual node-adding).

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

Basically, I want to try a variety of data structures as parameters. Yet, as there is no overloading, I cannot have more than one data structure work with the all-important contains function!

基本上,我想尝试各种数据结构作为参数。然而,由于没有重载,我不能使用多个包含函数的多个数据结构!

So, I wanted to make a "Set" class (I shouldn't roll my own, I know). I already have a pretty nifty Red-Black tree set up, thanks to Chris Okasaki's book, and now all that's left is simply making the Set class and declaring RBT, among others, as instances of it.

所以,我想做一个“Set”课(我不应该自己动手,我知道)。由于Chris Okasaki的书,我已经设置了一个非常漂亮的红黑树,现在剩下的就是制作Set类并宣布RBT等等。

Here is the following code:

这是以下代码:

(Note: code heavily updated -- e.g., contains now does not call a helper function, but is the class function itself!)

(注意:代码经过大量更新 - 例如,包含现在不调用辅助函数,但是类函数本身!)

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

Note how I have a pretty stupidly-defined Eq instance of RBT. That is intentional --- I copied it (but cut corners) from the gentle tutorial.

请注意我是如何拥有一个非常愚蠢定义的RBT Eq实例。这是故意的 - 我从温柔的教程中复制了它(但是偷工减料)。

Basically, my question boils down to this: If I comment out the instantiation statement for Set (RBT a), everything compiles. If I add it back in, I get the following error:

基本上,我的问题归结为:如果我注释掉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

And I simply cannot, for the life of me, figure out why that isn't working. (As a side note, the "contains" function is defined elsewhere, and basically has the actual set_contains logic for the RBT data type.)

我根本不能,为了我的生活,弄清楚为什么那不起作用。 (作为旁注,“包含”函数在别处定义,并且基本上具有RBT数据类型的实际set_contains逻辑。)

Thanks! - Agor

谢谢! - Agor

Third edit: removed the previous edits, consolidated above.

第三次修改:删除之前合并的上述修改。

5 个解决方案

#1

You could also use higher-kinded polyphormism. The way your class is defined it sort of expects a type t which has kind *. What you probably want is that your Set class takes a container type, like your RBT which has kind * -> *.

你也可以使用更高级的多形态。你的类被定义的方式,它需要一个有类型*的类型t。你可能想要的是你的Set类采用容器类型,就像你的RBT有类型* - > *。

You can easily modify your class to give your type t a kind * -> * by applying t to a type variable, like this:

通过将t应用于类型变量,您可以轻松修改类以使类型为* - > *,如下所示:

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

and then modify your instance declaration to remove the type variable a:

然后修改您的实例声明以删除类型变量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

So, here is the full modified code with a small example at the end:

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

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

If you compile this, the output is

如果你编译它,输出是

tree contains 3: True
tree contains 12: True
tree contains 7: False

#2

You need a multi-parameter type class. Your current definition of Set t doesn't mention the contained type in the class definition, so the member contains has to work for any a. Try this:

您需要一个多参数类型类。您对Set t的当前定义未提及类定义中包含的类型,因此该成员包含必须适用于任何a。试试这个:

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


instance (Ord a) => Set (RBT a) 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

The | t -> a bit of the definition is a functional dependency, saying that for any given t there is only one possible a. It's useful to have (when it makes sense) since it helps the compiler figure out types and reduces the number of ambiguous type problems you often otherwise get with multi-parameter type classes.

| t - >一些定义是一个函数依赖,说任何给定的t只有一个可能的a。拥有(当它有意义时)是有用的,因为它有助于编译器找出类型并减少多参数类型类通常会遇到的模糊类型问题的数量。

You'll also need to enable the language extensions MultiParamTypeClasses and FunctionalDependencies at the top of your source file:

您还需要在源文件的顶部启用语言扩展MultiParamTypeClasses和FunctionalDependencies:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

#3

The error means that the types don't match. What is the type of contains? (If its type is not something like t -> a -> Bool as set_contains is, something is wrong.)

该错误意味着类型不匹配。包含的类型是什么? (如果它的类型不是t - > a - > Bool as set_contains,那就错了。)

#4

Why do you think you shouldn't roll your own classes?

为什么你认为你不应该自己上课?

When you write the instance for Set (RBT a), you define contains for the specific type a only. I.e. RBT Int is a set of Ints, RBT Bool is a set of Bools, etc.

为Set(RBT a)编写实例时,只为特定类型定义包含a。即RBT Int是一组Ints,RBT Bool是一组Bools等。

But your definition of Set t requires that t be a set of all ordered a's at the same time!

但是你对Set t的定义要求t是所有有序a的集合!

That is, this should typecheck, given the type of contains:

也就是说,鉴于包含的类型,这应该是类型检查:

tree :: RBT Bool
tree = ...

foo = contains tree 1

and it obviously won't.

它显然不会。

There are three solutions:

有三种解决方案:

1. Make t a type constructor variable:

   创建一个类型的构造函数变量:

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

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

   instance Set RBT where ...

   实例设置RBT在哪里......

This will work for RBT, but not for many other cases (for example, you may want to use a bitset as a set of Ints.

这适用于RBT,但不适用于许多其他情况(例如,您可能希望将bitset用作一组Int。

2. Functional dependency:

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

   class(Ord a)=>设置t a | t - > a where contains :: t - > a - > Bool

   instance (Ord a) => Set (RBT a) a where ...

   实例(Ord a)=>设置(RBT a)a ...

See GHC User's Guide for details.

有关详细信息,请参阅GHC用户指南。

3. Associated types:

   class Set t where type Element t :: * contains :: t -> Element t -> Bool

   class设置t其中类型为Element t :: * contains :: t - > Element t - > Bool

   instance (Ord a) => Set (RBT a) where type Element (RBT a) = a ...

   实例(Ord a)=>设置(RBT a)其中类型元素(RBT a)= a ...

See GHC User's Guide for details.

有关详细信息,请参阅GHC用户指南。

#5

To expand on Ganesh's answer, you can use Type Families instead of Functional Dependencies. Imho they are nicer. And they also change your code less.

要扩展Ganesh的答案,您可以使用Type Families而不是Functional Dependencies。 Imho他们更好。而且他们也减少了你的代码。

{-# LANGUAGE FlexibleContexts, TypeFamilies #-}

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

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