Haskell: How can I define a type class for sets?

Question

Total newbie here, struggling.

I'm trying to define a type class for sets. For this case it would only require the definition of 'exists'. 'exists' would take a set and function on a set item, and return a boolean. How can I define that in Haskell?

Is the following even in the right direction? So there is the type class definition and an implementation of set with list, for which 'exists' returns true for now..

-- Set.hs --

class Set a b where

  exists :: a -> (b -> Bool) -> Bool


-- ListSet.hs --

instance Set ListSet a where 

  exists a f = True

--

(result: Too many parameters for class `Set')

Answer 1

You can do it this way, with enough extensions. At the very least, you'll need multiple-parameter type classes. However, it will be very annoying to use: you'll need to specify explicit type signatures all over the place. One way to fix it is to introduce a functional dependency (using another extension):

class Set a b | a -> b where
    exists :: a -> (b -> Bool) -> Bool

This says that if you know the type of the set, you know the type of the elements, too. However, there's a simpler way that works without any extensions:

class Set f where
    exists :: f a -> (a -> Bool) -> Bool

Here, the type class ranges over higher-kinded types, which is a neat trick and hard to come up with on your own if you've never seen it before!

Answer 2

Daniel Wagner already gave perfect answer on what you are trying to do. I just want to add a point about your error - Too many parameters for class 'Set'. This means that you didn't enable corresponding GHC extension - MultiParamTypeClasses. You can do it by specifying special kind of comment at the top of your source file:

{-# LANGUAGE MultiParamTypeClasses #-}
--
-- Your source code here
--

Then you should be able to compile your code.

Another Haskell feature mentioned in Daniel's answer also requires enabling certain extension, namely FunctionalDependencies (this is the weird .. | a -> b .. thing inside type class declaration). You can enable multiple extensions at the same time using comma, like this:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

Carl's comment mentions another extension, TypeFamilies, which could also provide means for what you are trying to do (generic class of set types or other kind of collections). You can read about it here: http://www.haskell.org/haskellwiki/Type_families.