sets: Ducktyped set interface for Haskell containers.

[ bsd3, data, library ] [ Propose Tags ]
Versions [RSS] 0.0.1,, 0.0.2,,,, 0.0.3, 0.0.4,, 0.0.5,,, 0.0.6,, (info)
Dependencies base (>=4.11 && <5.0), bytestring, commutative (>=0.0.2), composition, containers, contravariant, hashable, keys, mtl, QuickCheck (>=2.9.2), semigroupoids, semigroups, transformers, transformers-base, unordered-containers, vector, witherable [details]
License BSD-3-Clause
Copyright 2018 Athan Clark
Author Athan Clark
Category Data
Home page
Bug tracker
Source repo head: git clone
Uploaded by athanclark at 2019-10-27T17:59:41Z
Distributions LTSHaskell:, NixOS:, Stackage:
Downloads 8842 total (28 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2019-10-27 [all 1 reports]

Readme for sets-

[back to package description]


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"