What is the best way of representing an immutable list in .NET?

Question

I've recently started using F# for "real work" and rediscovered the beauty of immutable data structures such as the discriminated unions and records in F#. I've also found them to be quite straight forward to use from C#, especially as they don't require any direct dependencies on the F# runtime. However, when it comes to representing lists in these structures, I have not yet found an ideal solution.

My first attempt was to type the lists as seq<'a> (IEnumerable in the C# world) which provides a nice general collection interface without exporting any methods for mutating the collection the way ICollection<> and its friends does. However, since I have no control over the constructor of a discriminated union or record, it is possible for the creator of an instance of these types to provide an IEnumerable<> implementation that might change or throw when used (such as a LINQ expression). IEnumerable<> will therefor not give me any help from the compiler in proving that the value is immutable and therefor thread safe.

My current strategy is to use the F# list type which does guarantee an immutable collection, but adds a dependency on the F# runtime and looks a bit off when used from non F# projects. It does however allow for F# pattern matching which IEnumerable<> does not. It also doesn't give any choice in the actual representation of a list, and in some cases (such as large lists of primitive values) the F# list representation does not really fit.

What I really would like to see is an immutable array type in .NET, represented just as compactly as the normal array but with a compiler guarantee of not being mutated. I would welcome const as in C++ although it's probably not very likely to happen. In the meantime, is there any other option I've missed?

Answer 1

If what you want is an immutable array implementation then you can just use something like the following

public sealed class ImmutableArray<T> : IEnumerable<T>{
  private readonly T[] m_array;
  public T this[int index] {
    get { return m_array[index]; }
  }
  public int Length {
    get { return m_array.Length; }
  }
  public ImmutableArray(IEnumerable<T> enumerable) {
    m_array = enumerable.ToArray();
  }
  // IEnumerable<T> implementation ommitted
}

Answer 2

Wrap your normal array in a ReadOnlyCollection<T> instance:

var readOnlyData = new ReadOnlyCollection<TheType>(theRealCollection);

(Note, this does not copy the underlying collection, but holds a reference and and modifying members of IList<T> etc. are implemented to throw an exception.)

Answer 3

I'd recommend looking at Eric Lippert's series on immutability, it's a very useful read. Part 4 about a immutable queue would be a good place to start.