Where is the class set type?

Question

In Haskell, Data.Set implements a specific type of set. Normal [] lists also implement all dial operations (in Data.List ). But there seems to be no predefined Set class that they both implement. You can implement it 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 looks like it would already be done if it were the way. So my question is: where is the Set class, or what alternative solution does the Haskell community have?

My question is admittedly very similar to Why Haskell is missing the “obvious” Typeclasses , but being more specific (with emphasis on a concrete example with an approximate implementation), I hope to get even more specific answers.

Answer 1

For some reason, Haskell does not want to do anything to have deep hierarchies of type classes to represent all possible kinds of containers.

Typically, different types of containers have performance properties for different operations. Usually you know which operations are important to you, and you choose the most suitable container and use it explicitly. There are not many requirements to be able to write truly generic code that works in all possible containers.

Please note that there are some type classes for working with containers already - they are simply not the ones you expect. For instance:

• Functor allows you to apply a function to each element of the container - any container; and collect the results in a new container of the same type.

• Applicative and / or Monad allow you to apply a function to each element and call more than one element as a result. (This may not be obvious, but you can use it to perform “filtering” and even “deleting,” although it is probably inefficient.)

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

• Alternative , Foldable and Traversable allow you to do interesting magic.

Answer 2

You can try Data.Containers from mono-traversable

Typically, Haskell code tends to have less tendency to generalize data types like these than, say, Java, so these abstractions are not in containers or unordered-containers .

Answer 3

I 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 

Thus, the community prefers many small classes that are more reusable than this Set class.

Here is another point that may be helpful. You seem to mentally associate classes with types, as a mental classification of types that are similar because they “represent sets”. But the Haskell community more often associates classes with operations . You can see this in the annotation above, I hope most of the operations you offer remind me of an existing class. The black label is the fact that most of these classes will not work with a type of type Set , which has an element type constraint ...