14

It seems to me there is an extreme lack of safe, immutable collection types for .NET, in particular BCL but I've not seen much work done outside either. Do anyone have any pointers to a (preferably) production quality, fast, immutable collections library for .NET. A fast list type is essential. I'm not yet prepared to switch to F#.

*Edit: Note to searchers, this is being rolled into the BCL soon: .NET immutable collections

0

7 Answers 7

19

You might want to take a look at the Microsoft.FSharp.Collections namespace in the FSharp.Core assembly. You do not have to program in F# to make use of these types.

Keep in mind that the names will be different when used from outside F#. For example, the Map in F# is known as FSharpMap from C#.

7
  • Hi Rich, I'm trying these out now. Thanks. Aug 14, 2010 at 22:23
  • Rich, I think these may actually work practically from within C# with the addition of some extension methods for typical operations like consing etc. Aug 14, 2010 at 22:30
  • 1
    related: stackoverflow.com/questions/8238757/… Nov 23, 2011 at 14:41
  • 1
    Unfortunately all of the F# collections are implemented as classes and not interfaces. This makes them less than ideal for API specification. Sep 27, 2012 at 5:12
  • @drozzy I haven't tried this but the documentation suggests they do implement all the usual interfaces. Sep 27, 2012 at 10:12
11

The .NET BCL team has released a Immutable Collections preview for .NET 4.5

0
9
2
  • 1
    This is more like it! Do you know how these collections stack up against the Microsoft.FSharp.Collections, that Rich mentioned above, in terms of performance? Thanks for the reference, Mauricio! Aug 15, 2010 at 10:43
  • 1
    This library, by Alexey, looks to be very well factored and clean. A huge thanks from me to you! :-) Aug 15, 2010 at 11:04
6

I wrote an ImmutableList<T> class some time ago :

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class ImmutableList<T> : IList<T>, IEquatable<ImmutableList<T>>
{
    #region Private data

    private readonly IList<T> _items;
    private readonly int _hashCode;

    #endregion

    #region Constructor

    public ImmutableList(IEnumerable<T> items)
    {
        _items = items.ToArray();
        _hashCode = ComputeHash();
    }

    #endregion

    #region Public members

    public ImmutableList<T> Add(T item)
    {
        return this
                .Append(item)
                .AsImmutable();
    }

    public ImmutableList<T> Remove(T item)
    {
        return this
                .SkipFirst(it => object.Equals(it, item))
                .AsImmutable();
    }

    public ImmutableList<T> Insert(int index, T item)
    {
        return this
                .InsertAt(index, item)
                .AsImmutable();
    }

    public ImmutableList<T> RemoveAt(int index)
    {
        return this
                .SkipAt(index)
                .AsImmutable();
    }

    public ImmutableList<T> Replace(int index, T item)
    {
        return this
                .ReplaceAt(index, item)
                .AsImmutable();
    }

    #endregion

    #region Interface implementations

    public int IndexOf(T item)
    {
        if (_items == null)
            return -1;

        return _items.IndexOf(item);
    }

    public bool Contains(T item)
    {
        if (_items == null)
            return false;

        return _items.Contains(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        if (_items == null)
            return;

        _items.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get
        {
            if (_items == null)
                return 0;

            return _items.Count;
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        if (_items == null)
            return Enumerable.Empty<T>().GetEnumerator();

        return _items.GetEnumerator();
    }

    public bool Equals(ImmutableList<T> other)
    {
        if (other == null || this._hashCode != other._hashCode)
            return false;
        return this.SequenceEqual(other);
    }

    #endregion

    #region Explicit interface implementations

    void IList<T>.Insert(int index, T item)
    {
        throw new InvalidOperationException();
    }

    void IList<T>.RemoveAt(int index)
    {
        throw new InvalidOperationException();
    }

    T IList<T>.this[int index]
    {
        get
        {
            if (_items == null)
                throw new IndexOutOfRangeException();

            return _items[index];
        }
        set
        {
            throw new InvalidOperationException();
        }
    }

    void ICollection<T>.Add(T item)
    {
        throw new InvalidOperationException();
    }

    void ICollection<T>.Clear()
    {
        throw new InvalidOperationException();
    }

    bool ICollection<T>.IsReadOnly
    {
        get { return true; }
    }

    bool ICollection<T>.Remove(T item)
    {
        throw new InvalidOperationException();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    #endregion

    #region Overrides

    public override bool Equals(object obj)
    {
        if (obj is ImmutableList<T>)
        {
            var other = (ImmutableList<T>)obj;
            return this.Equals(other);
        }
        return false;
    }

    public override int GetHashCode()
    {
        return _hashCode;
    }

    #endregion

    #region Private methods

    private int ComputeHash()
    {
        if (_items == null)
            return 0;

        return _items
            .Aggregate(
                983,
                (hash, item) =>
                    item != null
                        ? 457 * hash ^ item.GetHashCode()
                        : hash);
    }

    #endregion
}

All methods that modify the collection return a modified copy. In order to fulfill with the IList<T> interface contract, the standard Add/Remove/Delete/Clear methods are implemented explicitly, but they throw an InvalidOperationException.

This class uses a few non-standard extension methods, here they are :

public static class ExtensionMethods
{
    public static IEnumerable<T> Append<T>(this IEnumerable<T> source, T item)
    {
        return source.Concat(new[] { item });
    }

    public static IEnumerable<T> SkipFirst<T>(this IEnumerable<T> source, Func<T, bool> predicate)
    {
        bool skipped = false;
        foreach (var item in source)
        {
            if (!skipped && predicate(item))
            {
                skipped = true;
                continue;
            }

            yield return item;
        }
    }

    public static IEnumerable<T> SkipAt<T>(this IEnumerable<T> source, int index)
    {
        return source.Where((it, i) => i != index);
    }

    public static IEnumerable<T> InsertAt<T>(this IEnumerable<T> source, int index, T item)
    {
        int i = 0;
        foreach (var it in source)
        {
            if (i++ == index)
                yield return item;

            yield return it;
        }
    }

    public static IEnumerable<T> ReplaceAt<T>(this IEnumerable<T> source, int index, T item)
    {
        return source.Select((it, i) => i == index ? item : it);
    }
}

And here's a helper class to create instances of ImmutableList<T> :

public static class ImmutableList
{
    public static ImmutableList<T> CreateFrom<T>(IEnumerable<T> source)
    {
        return new ImmutableList<T>(source);
    }

    public static ImmutableList<T> Create<T>(params T[] items)
    {
        return new ImmutableList<T>(items);
    }

    public static ImmutableList<T> AsImmutable<T>(this IEnumerable<T> source)
    {
        return new ImmutableList<T>(source);
    }
}

Here's a usage example :

    [Test]
    public void Test_ImmutableList()
    {
        var expected = ImmutableList.Create("zoo", "bar", "foo");
        var input = ImmutableList.Create("foo", "bar", "baz");
        var inputSave = input.AsImmutable();
        var actual = input
                .Add("foo")
                .RemoveAt(0)
                .Replace(0, "zoo")
                .Insert(1, "bar")
                .Remove("baz");

        Assert.AreEqual(inputSave, input, "Input collection was modified");
        Assert.AreEqual(expected, actual);
    }

I can't say it's production quality, as I haven't tested it thoroughly, but so far it seems to work just fine...

4
  • 3
    Very nice implementation! However, it would probably be faster under stress if you created the target array directly and used Array.Copy. IEnumerable<T> is nice for readable functional code, but honestly, it’s going to be slow.
    – Timwi
    Aug 14, 2010 at 22:55
  • @Timwi, indeed, this implementation could certainly be optimized. I didn't need a very efficient implementation when I wrote it, so I did it the Linq way because it's more fun ;) Aug 15, 2010 at 0:23
  • @Timwi - This approach is more memory-friendly though at least, because the contents of the lists is being reused, though as you say inefficient - especially for indexed access to elements. Something akin to a Lisp list using immutable cons cells (en.wikipedia.org/wiki/Cons) would provide a nice middle ground - where indexed access to sequential members can be optimised (fixed cost to fetching next item), where the enumerable solution has a variable cost, while avoiding the need to copy the entire contents of the list for scenarios where the tail of the list is unchanged. Sep 2, 2010 at 1:34
  • 2
    @Bittercoder: No, this implementation makes a copy of every new version of the immutable list (by invoking ToArray in the constructor).
    – Timwi
    Sep 2, 2010 at 2:06
1

C5 springs to mind, but I'm not sure how fast it is. It has been around for years, and is very stable.

Additionally, List<T>.AsReadOnly() does the job rather well IMO, but unfortunately there is no equivalent for dictionaries or arbitrary ICollection<T>'s.

4
  • Unfortunately, .AsReadOnly() only returns a wrapper around the original collection; the original reference is still mutable, and therefore so is the read-only wrapper. It seems that the same is true of C5.
    – Timwi
    Aug 14, 2010 at 22:16
  • @Timwi If you're worried that the original reference may be modified by some other code then just make a copy of it: return new List<T>(myList).AsReadOnly() Aug 14, 2010 at 22:30
  • @romkyns If one always makes a copy of lists, there would be no need for immutable lists :-) Sep 27, 2012 at 5:14
  • @drozzy .AsReadOnly() is pretty decent in many circumstances and we don't have anything better built-in :) Also, you only need the copy made once, after that the list is properly immutable and can be passed around everywhere. Sep 27, 2012 at 10:10
1

You may look at Extras or System.collections.concurrent tutorial

0
0

You could try BclExtras by JaredPar.

Not the answer you're looking for? Browse other questions tagged or ask your own question.