Defining multiple-type container classes in haskell, trouble binding variables

Question

I'm having trouble with classes in 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).

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.

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.

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:

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.)

Thanks! - Agor

Third edit: removed the previous edits, consolidated above.

Answer 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 * -> *.

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

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

and then modify your instance declaration to remove the type variable 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

Answer 2

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.

{-# 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

Answer 3

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:

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.

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

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

Answer 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.

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

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

   instance Set RBT where ...

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.

2. Functional dependency:

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

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

See GHC User's Guide for details.

3. Associated types:

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

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

See GHC User's Guide for details.

Answer 5

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.)