ISet<T> Considered Harmful
Tags: computerscience, csharp, dotnet
Published: 2020-09-24 17:03:37

[`ISet<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1) is a disaster waiting to happen, should be considered a code smell, and considered harmful. But why?

___

> Nanos gigantum humeris insidentes

___ 

> If I have seen further it is by standing on the shoulders of Giants. -- Isaac Newton

___

> I say with Didacus Stella, a dwarf standing on the shoulders of a giant may see farther than a giant himself. -- Diego de Estella

___

**If** we reuse an existing idea, we can build upon the entire corpus of knowlege built upon it. _We can stand on giants, and see further_.

So is there an existing idea and corpus we can stand upon? Yes, and it's [Set Theory](https://en.wikipedia.org/wiki/Set_theory) and [Set Algebra](https://en.wikipedia.org/wiki/Algebra_of_sets). In reusing these ideas, we can build upon ever pitfall, every mistake, every advancement, and every solution people before us have found. Does [`ISet<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1) do this? **No**.

# Where [`ISet<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1) goes wrong

Before anything else, I should probably clarify what a set is. A set is a collection where each element only exists once, and does not care about the order of the elements, nor how the internals are structured. It only cares about what is in the set. Evaluating against this alone, [`ISet<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1) seems fine. But this isn't the whole picture.

Sets are inherently immutable. Consider the set of all even numbers. There's no reason to add a new number to the set, for the set _always_ contained all even numbers. So why does [`ISet<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1) provide [`Add()`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1.add)? Is this problematic? Consider:

~~~~csharp
ISet<Int32> evens = new HashSet<Int32>(new Int32[] { 2, 4, 6, 8...});
Assert.False(evens.Contains(1)); // passes
_ = evens.Add(1);
Assert.False(evens.Contains(1)); // fails
~~~~

Whoa, wait, why is this allowable? We just violated the semantics of the set!

But this isn't the only place where we can violate set semantics. Oh no.

~~~~csharp
ISet<Color> primaryColors = new HashSet<Color>(new Color[] { Color.Red, Color.Yellow, Color.Blue });
ISet<Color> printerColors = new HashSet<Color>(new Color[] { Color.Cyan, Color.Magenta, Color.Yellow, Color.Black });
primaryColors.UnionWith(printerColors);
Assert.False(primaryColors.Contains(Color.Magenta)) // fails
~~~~

Magenta isn't a primary color! Why did this happen? One only needs to look at the signature and summary of [`UnionWith()`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1.unionwith) to see why.

~~~~csharp
public void UnionWith(IEnumerable<T> other);
~~~~

> Modifies the current set so that it contains all elements that are present in the current set, in the specified collection, or in both.

This isn't even the end of the story though. [Set Algebra](https://en.wikipedia.org/wiki/Algebra_of_sets), much like the [Abstract Algebra](https://en.wikipedia.org/wiki/Abstract_algebra) you're familiar with from [Algebraic Number Theory](https://en.wikipedia.org/wiki/Algebraic_number_theory) has the concept of identities that are very important for its operation. These are empty set (Ø) and universe set (U). Trying to do set algebra without identities is like trying to do abstract algebra without 0 and 1!

Furthermore, [`ISet<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1) is a [leaky abstraction](https://en.wikipedia.org/wiki/Leaky_abstraction), and this isn't just a case of a code smell where it makes it difficult to do refactorings later on, although that is a problem in and of itself. Because of the implementation details leaking through, we know [`ISet<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1) is a collection like any other. What's wrong with that? The problem is immediately apparent with the [compliment](https://en.wikipedia.org/wiki/Complement_(set_theory)) operation. Consider the compliment of all primary colors. This is a set that has to contain _every_ color that is not one of the three primary colors. You're guaranteed to run out of memory! There's infinite colors! Even if we were to just go with 24-bit colors that computers can represent, even though some advanced color spaces use even larger amounts, this means allocating `16,777,216 - 3` color structures, at 32-bits each, for `536,870,816` bits or `67,108,852` bytes of memory! I don't know about you, but I don't have a computer that can hold that.

# What [`ISet<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1) should be

[`ISet<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.iset-1)'s problems stem from deriving from [`ICollection<T>`](https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.icollection-1) which itself is problematic because it makes incorrect assumptions about what is common amongst all collections. Sets are only one of the areas where those assumptions are violated.

Instead, sets should adhere as closely to the established [Set Theory](https://en.wikipedia.org/wiki/Set_theory) and [Set Algebra](https://en.wikipedia.org/wiki/Algebra_of_sets) as possible. This not only ensures that basic semantics of a set are as they should be, but also that discovered and published solutions which utilize [Set Theory](https://en.wikipedia.org/wiki/Set_theory) and [Set Algebra](https://en.wikipedia.org/wiki/Algebra_of_sets) can be readily adopted by programmers facing difficult problems, rather than working out new solutions using an ad-hoc theory and ad-hoc algebra likely rife with undiscovered problems.

I've been doing exactly this inside of [**Collectathon**](https://github.com/Entomy/Collectathon), a project I revived earlier this month (Sept, 2020). As of this article the resulting code hasn't been committed just yet, as I'm fleshing out expected algebraic operations, but the implementation and interface have been delightful, and actually rather simple. Furthermore, as I talked about in a previous article, [`Category`](https://dev.to/entomy/category-class-1602) was conceptually a set as well, and in implementing a generalized set base, the implementation of [`Category`](https://dev.to/entomy/category-class-1602) can be simplified, with the entirety of set algebra automatically provided, by simply deriving from `Set`. That is a fantastic example of code reuse.

Again:

> If I have seen further it is by standing on the shoulders of Giants. -- Isaac Newton