BSD-3-Clause licensed by Athan Clark
Maintained by [email protected]
This version can be pinned in stack with:sets-,3046


This package provides overloaded terms, commonly used with set-like types, like Map and Set from containers. There are also unorthodox, mostly useless data types defined here - playing with ordering, uniqueness and finiteness.


The following actions are overloaded:

Binary Operators:

  • union
  • intersection
  • difference
  • complement

Top and Bottom Elements:

  • empty
  • total

Element-Wise Operations:

  • singleton
  • insert
  • delete

Metrics and Comparison:

  • size
  • isSubsetOf isProperSubsetOf

Each of the operations has their own typeclass. We have also made newtype wrappers for lists, for different restrictions:

  • Ordered Sets
    • Multiple
  • Unordered Sets
    • Unique
    • Multiple

This way, we can expect the following to work:

uniqueAppend :: Eq a => [a] -> [a] -> [a]
uniqueAppend xs ys = unUUSet $ fromFoldable xs `union` fromFoldable ys

orderedAppend :: Ord a => [a] -> [a] -> [a]
orderedAppend xs ys = unOMSet $ fromFoldable xs `union` fromFoldable ys

We’ve also made a few newtypes to encode our binary operations, for Monoid and Semigroup instances:

instance (HasUnion s, HasEmpty s) => Monoid (Union s) where
  mempty = empty
  mappend = union

Multiple Set Types

To use the overloaded terms, they need to be the only ones in scope. To make this correct, we need to import our container with caution:

import qualified Data.Set as Set
import Data.Map (Map) -- only the type name to designate behavior

foo :: Map
foo = x `union` y

bar :: Set.Set
bar = a `union` b

This way, we can keep our code more readable while still having set-like intuition.

Testing and Benchmarking

You can view the results here (warning: it’s a 7MB text file - your browser will hate you)

The tests are built with QuickCheck - it’s pretty easy to get them working for you:

cabal install --enable-tests
cabal test --show-details=always

(…or for the stack folk…)

stack build
stack test

To benchmark (it usually takes about 10 minutes on my laptop), run the command!

cabal install --enable-benchmarks
cabal bench

(…stiggitty-stack is co-wiggity-whack…)

stack build
stack bench --benchmark-arguments="--output profile.html"