Please add interface IReadOnlySet and make HashSet, SortedSet implement it

[dsaf]

Original

Since IReadOnlyList was added the parity between sets and lists has declined. It would be great to re-establish it.

Using it would be an implementation-agnostic way of saying: "here is this read-only collection where items are unique".

Clearly it's needed by many people:

SQL Server: https://msdn.microsoft.com/en-us/library/gg503096.aspx
Roslyn: https://github.com/dotnet/roslyn/blob/master/src/Compilers/Core/Portable/InternalUtilities/IReadOnlySet.cs
Some Guy In Comments: http://blogs.msdn.com/b/bclteam/archive/2013/03/06/update-to-immutable-collections.aspx

I found this discussion when working on a real world problem where I wanted to use the key collection of a dictionary for read only set operations. In order to support that case here's the API I propose.

Edit

Rationale

Proposed API

 namespace System.Collections.Generic {
+ public interface IReadOnlySet<out T> : IReadOnlyCollection<T>, IEnumerable, IEnumerable<T> {
+ bool Contains(T value);
+ bool IsProperSubsetOf(IEnumerable<T> other);
+ bool IsProperSupersetOf(IEnumerable<T> other);
+ bool IsSubsetOf(IEnumerable<T> other);
+ bool IsSupersetOf(IEnumerable<T> other);
+ bool Overlaps(IEnumerable<T> other);
+ bool SetEquals(IEnumerable<T> other);
+ }
- public class HashSet<T> : ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T> {
+ public class HashSet<T> : ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T>, IReadOnlySet<T> {
 }
- public class SortedSet<T> : ICollection, ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T> {
+ public class SortedSet<T> : ICollection, ICollection<T>, IDeserializationCallback, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, ISerializable, ISet<T>, IReadOnlySet<T> {
 }
+ public class ReadOnlySet<T> : ICollection<T>, IEnumerable, IEnumerable<T>, IReadOnlyCollection<T>, IReadOnlySet<T>, ISet<T> {
+ public int Count { get; }
+ public ReadOnlySet(ISet<T> set);
+ public bool Contains(T value);
+ public bool IsProperSubsetOf(IEnumerable<T> other);
+ public bool IsProperSupersetOf(IEnumerable<T> other);
+ public bool IsSubsetOf(IEnumerable<T> other);
+ public bool IsSupersetOf(IEnumerable<T> other);
+ public bool Overlaps(IEnumerable<T> other);
+ public bool SetEquals(IEnumerable<T> other);
+ }
 public class Dictionary<TKey, TValue> {
- public sealed class KeyCollection : ICollection, ICollection<TKey>, IEnumerable, IEnumerable<TKey>, IReadOnlyCollection<TKey> {
+ public sealed class KeyCollection : ICollection, ICollection<TKey>, IEnumerable, IEnumerable<TKey>, IReadOnlyCollection<TKey>, IReadOnlySet<TKey> {
+ public bool IsProperSubsetOf(IEnumerable<TKey> other);
+ public bool IsProperSupersetOf(IEnumerable<TKey> other);
+ public bool IsSubsetOf(IEnumerable<TKey> other);
+ public bool IsSupersetOf(IEnumerable<TKey> other);
+ public bool Overlaps(IEnumerable<TKey> other);
+ public bool SetEquals(IEnumerable<TKey> other);
 }
 }
 }

Open Questions

• Is adding these methods to Dictionary<TKey, TValue>.KeyCollection acceptable given the code size cost for a commonly instantiated generic type? See here.
• Should IReadOnlySet<T> be implemented in other Dictionary KeyCollections such as SortedDictionary or ImmutableDictionary?

Updates

• Removed TryGetValue as it's not in ISet<T> and as such would prevent potentially ever rebasing ISet<T> to implement IReadOnlySet<T>.
• Added ReadOnlySet<T> class which is similar to ReadOnlyCollection<T>.

[whoisj]

Wouldn't be nice if we just had some language construct to make things immutable? Then we would not have to have these magic interfaces.

[HaloFour]

@whoisj Which language? The CLR has dozens of them.

Even as a potential language feature it would require a metadata representation. For this case a marker interface (or behavioral interface) is as good as any. Trying to convey the immutability of a collection type through a new metadata entry doesn't seem appropriate since the CLR shouldn't be making assumptions as to how an arbitrary class functions internally (and the CLR has no concept of collection classes at all aside for arrays).

[dsaf]

@whoisj I think this is at least considered for one of the future C# versions. But that decision doesn't affect the need for symmetrical interfaces across all collections. Furthermore I can imagine scenarios where a readonly list of mutable items could be useful, e.g. in games that care about both code quality and performance.

Also immutable collections are already available:

https://msdn.microsoft.com/en-us/library/system.collections.immutable(v=vs.111).aspx

To achieve a fully immutable collection we just need a way of defining an immutable T and then use it to declare an Immutable...<T> collection.

[whoisj]

@HaloFour we've been down this road before 😏 but I still believe the CLR needs a way to say "here's a handle, read from it but all actions that cause any kind of write through it will fail; oh and this immutability is contagious so any handle reached from the immutable handle is also immutable (including this)".

@dsaf absolutely! In another issue I proposed that we have a writable anti-term for readdonly to enable the use of readonly collection of writeble elements. Something along the lines of readonly Bag<writable Element>.

I suggested that any reference marked with a & be treated as immutable by the compiler. I still feel it only need be a compile time check, and necessarily enforced by the CLR itself as I'm mostly seeking compile time verification of logic and not run-time guarantees. This would cover any reference which developers wanted to be immutable, but on a per call basis.

[HaloFour]

@whoisj Perhaps, but that's pretty tangential and it turns this request from something dsaf could branch/PR this afternoon into something that involves effort across three different teams.

You're also treating this as a compiler concern. At this point there isn't a compiler involved (beyond the JIT compiler) and only the verifier can attempt to prevent "improper" code from executing. Even the existing runtime mechanisms of immutability, initonly fields, can be easily defeated if verification is skipped (or via reflection).

I do agree that it would be nice if the C# language and compiler can have better support for "pure" methods. The attribute PureAttribute already exists but it's used sporadically and there really isn't any language support for it. And even if C# did support it through compiler errors (pure can only call pure, etc.), it's very easily defeated by using a different language. But these methods have to announce themselves and enforce themselves as once compiled to IL all bets are basically off and none of the compilers can bend how an existing assembly executes.

[whoisj]

@HaloFour fair.

Assuming we don't have a general way to support "pure" or "const" references, then I suppose the proposed is the best alternative.

[yanggujun]

If you need it now, my Commons library (Commons.Collections https://github.com/yanggujun/commonsfornet/tree/master/src/Commons.Collections/Set ) has the readonly set support. Admin please delete this post if this is thought as an advert... My suggestion is to look around for some open source implementation.

[dsaf]

@yanggujun Thank you for suggestion, that seems like a nice library, but I will roll my own to avoid extra dependencies.

My suggestion is to look around for some open source implementation.

This is a work-around, fundamental interfaces like IReadOnlySet should really be a part of .NET Framework itself.

[ashmind]

Does this need a speclet to become "ready for api review"?

[GiottoVerducci]

And while we're at it, consider naming it something different than "ReadOnly" (see interesting post: http://stackoverflow.com/questions/15262981/why-does-listt-implement-ireadonlylistt-in-net-4-5)
"Readable" seems fine.

[dsaf]

@GiottoVerducci No. I would prefer to keep a consistent naming pattern even if it is imperfect. You are free to raise a separate issue to rename existing interfaces though.

[ashmind]

Proposed API design:

public interface IReadOnlySet<T> : IReadOnlyCollection<T> { 
 bool Contains(T item);
 bool IsSubsetOf(IEnumerable<T> other);
 bool IsSupersetOf(IEnumerable<T> other);
 bool IsProperSupersetOf(IEnumerable<T> other);
 bool IsProperSubsetOf(IEnumerable<T> other);
 bool Overlaps(IEnumerable<T> other);
 bool SetEquals(IEnumerable<T> other);
}

This is based on ISet<> API (except mutation methods obviously).

It's a pity Comparer does not fit in this, but then neither ISet<> nor IReadOnlyDictionary<> expose comparers, so it's too late to fix now.

[binki]

 bool Contains(T item);

Shouldn’t this be in IReadOnlyCollection<T> instead since ICollection<T> has Contains(T item)?

[adamt06]

The immutable collections package has been unlisted from nuget while still beta.
I think this is a pretty common use case and should be handled in standard libs.