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

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?

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
}

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.)

Microsoft releases a stable version of Immutable collections nugget package. It doesn't come with ImmutableArray yet. But these immutable data structures should be very useful.

• ImmutableList
• ImmutableDictionary
• ImmutableSortedDictionary
• ImmutableHashSet
• ImmutableSortedSet
• ImmutableStack
• ImmutableQueue

http://blogs.msdn.com/b/dotnet/archive/2013/09/25/immutable-collections-ready-for-prime-time.aspx

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.