Haskell and typeclasses with multiple parameters

Question

I'm having a simple problem when it comes to writing up typeclasses that inherit from one another. I'm trying to create a hierarchy of typeclasses to achieve some level of representational abstraction. Let's say I want a collections typeclass:

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}

class Collection c a where
  isMember :: a -> c -> Bool

And I've defined a tree type:

data Tree a = Empty | Node a (Tree a) (Tree a)
  deriving (Show, Eq)

I'd like to make my tree a collection, so:

inOrder :: Tree a -> [a]
inOrder Empty = []
inOrder (Node a l r) = (inOrder l) ++ [a] ++ (inOrder r)

instance (Eq a) => Collection (Tree a) a where
  isMember a c = a `elem` (inOrder c)

This doesn't quite work right:

*Main> (isMember '2' Empty)
<interactive>:1:1:
    No instance for (Collection (Tree a) Char)
      arising from a use of `isMember' at <interactive>:1:1-18
    Possible fix:
      add an instance declaration for (Collection (Tree a) Char)
    In the expression: (isMember '2' Empty)
    In the definition of `it': it = (isMember '2' Empty)

Presumably the value of the typeclass would be lost if I had to create an implementation for each concrete type. So I'm not writing the instance declaration correctly. But I can't quite figure out how to proceed.

Answer 1

The issue here is that, by default, each type class parameter is independent of the others. Simply applying isMember to a Char and a tree of unknown element type isn't enough to let it deduce that it should use the (seemingly obvious) instance.

This is clearly not how you want it to work, and a bit silly to boot, but that's how it works. To deal with the problem, you need to give it some way of making the connection, for which there are other extensions: FunctionalDependencies is the more common, while TypeFamilies is newer and much nicer to use, but still has some rough edges.

With functional dependencies, you would specify that some subset of the type class parameters fully determine others, e.g. Collection c a | c -> a. This has its own pitfalls, but works well enough in many cases.

With type families, you would probably reduce this to a single-parameter type class, with the element type associated, e.g.:

class Collection c where
    type Elem c
    isMember :: Elem c -> c -> Bool

Answer 2

You need to add a functional dependency to indicate that the container type determines the element type:

{-# LANGUAGE FunctionalDependencies #-}

class Collection c a | c -> a where
    ...

There are also other ways of doing this, like using type families, but I think this is the simplest fix in this case.

Answer 3

The problem is that Empty's type is Tree a and ghc doesn't have enough information to know that you want the a to be Char in this case. If you manually specify the type, it works:

isMember '2' (Empty::Tree Char)

The reason ghc can't just infer that a needs to be Char is that theoretically you could have one instance Collection (Tree Char) Char and another Collection (Tree Int) Char. In that case there would be no way to infer which one should be used, unless you specify so explicitly.