Where is the Set type class?

Question

In Haskell Data.Set implements a concrete set type. Normal [] lists also implement all operations of a set (in Data.List). But there seems to be no predefined Set typeclass that they both implement. You can implement one yourself:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}

module Set where

import qualified Data.List as ConcreteList
import qualified Data.Set as ConcreteSet

class Set set a | set -> a where
  empty :: set
  singleton :: a -> set
  insert :: a -> set -> set
  delete :: a -> set -> set
  union :: set -> set -> set
  intersection :: set -> set -> set
  member :: a -> set -> Bool
  filter :: (a -> Bool) -> set -> set

instance (Ord a) => Set (ConcreteSet.Set a) a where
  empty = ConcreteSet.empty
  singleton = ConcreteSet.singleton
  insert = ConcreteSet.insert
  delete = ConcreteSet.delete
  union = ConcreteSet.union
  intersection = ConcreteSet.intersection
  member = ConcreteSet.member
  filter = ConcreteSet.filter

instance (Eq a) => Set [a] a where
  empty = []
  singleton e = [e]
  insert = (:)
  delete = ConcreteList.delete
  union = ConcreteList.union
  intersection = ConcreteList.intersect
  member = ConcreteList.elem
  filter = ConcreteList.filter

but it seems that this would already have been done if this was the way to go. So my question is: Where is the Set typeclass or what alternative solution has the Haskell community come up with?

My question is admittedly quite similar to Why is Haskell missing “obvious” Typeclasses, but by being more concrete (focusing on a specific example with sample implementation), I'm hoping to get some more concrete answers as well.

Answer 1

For whatever reason, Haskell tends not to do the whole thing of having deep hierarchies of type classes for representing all possible sorts of containers.

Generally, different sorts of containers have performance properties for different operations. Typically you know what operations are important to you, and you choose the most suitable container and use that explicitly. There's not much requirement to be able to write really generic code that operates over every possible kind of container.

Note that there are some type classes for dealing with containers already — they're just not the ones you might be expecting. For example:

• Functor allows you to apply a function to every element of a container — any container — and collect the results into a new container of the same type.

• Applicative and/or Monad allow you to apply a function to every element and produce more than one element as result. (It may not be obvious, but you can use this to perform "filtering" and even "deletion", although it's probably not efficient.)

• Monoid provides your empty and union methods (but named mempty and mappend).

• Alternative, Foldable and Traversable let you do further interesting magic.