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.

Answer 2

I'll annotate the class a bit:

-- The functional dependency here ties in to the issues with 
-- restricted type class instances, for which there is no one
-- globally adopted solution.
class Set set a | set -> a where
  -- This is a `Monoid`- or `Alternative`-like constant
  empty :: set

  -- This is an `Applicative`-like operation
  singleton :: a -> set

  -- If you have `singleton` and `union` you have `insert`.
  -- Which means that `insert` might fall out of the 
  -- `Alternative` class.
  insert :: a -> set -> set

  -- This looks like a variant of `filter` below.
  delete :: a -> set -> set

  -- These two are `Semigroup` operations
  union :: set -> set -> set
  intersection :: set -> set -> set

  -- Can't think of anything for this one.
  member :: a -> set -> Bool

  -- This is very `Monad`-like operation.  You can write this
  -- in terms of a bind/`unionMap` operation + your `singleton`
  -- and `empty`.
  filter :: (a -> Bool) -> set -> set

So basically, the community prefers a lot of small classes that are more reusable than this Set class would be.

Here's another point that might be useful. You seem to be mentally tying classes to types, as a mental classification of types that are similar because they "represent sets." But the Haskell community more often ties classes to operations. You can see this in the annotation above, I hope—most of the operations that you propose remind me of some already existing class. The black mark is the fact that most of those classes won't work with a type like Set that has an element type constraint...

Answer 3

You can try Data.Containers from mono-traversable

Haskell code in general tends to have less of a leaning towards generalizing data types like this than, say, Java, which is why these abstractions aren't in containers or unordered-containers.