ImmutableList.cs

public static class ImmutableListExtensions
{
    public static ImmutableList<T> Filter<T>(this ImmutableList<T> source, Func<T, bool> predicate)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (predicate == null) throw new ArgumentNullException("predicate");

        if (source.IsEmpty) return source;
        return ImmutableList<T>.Create(source.Where(predicate));
    }

    public static ImmutableList<T> QuickSort<T>(this ImmutableList<T> list, Func<T, T, int> compare)
    {
        if (list == null) throw new ArgumentNullException("list");
        if (compare == null) throw new ArgumentNullException("compare");

        return list.IsEmpty ? list :
            list.Tail.Filter(e => compare(e, list.Head) < 0).QuickSort(compare) +
            ImmutableList<T>.Create(list.Head) +
            list.Tail.Filter(e => compare(e, list.Head) >= 0).QuickSort(compare);
    }
}


public abstract class ImmutableList<T> : IEnumerable<T>
{
    public static readonly ImmutableList<T> Empty = new EmptyImmutableList<T>();

    public static ImmutableList<T> Create(T element)
    {
        return new NonEmptyImmutableList<T>(element, Empty);
    }

    public static ImmutableList<T> Create(params T[] elements)
    {
        if (elements == null) throw new ArgumentNullException("elements");

        return Create(elements, Empty);
    }

    public static ImmutableList<T> Create(IEnumerable<T> elements)
    {
        if (elements == null) throw new ArgumentNullException("elements");

        return Create(elements, Empty);
    }

    private static ImmutableList<T> Create(IEnumerable<T> elements, ImmutableList<T> tail)
    {
        return NonEmptyImmutableList<T>.FromEnumerable(elements, tail);
    }

    public static ImmutableList<T> operator +(ImmutableList<T> headList, ImmutableList<T> tailList)
    {
        if (headList == null) throw new ArgumentNullException("headList");
        if (tailList == null) throw new ArgumentNullException("tailList");

        if (headList.IsEmpty) return tailList;
        if (tailList.IsEmpty) return headList;

        return Create(headList, tailList);
    }

    public abstract T Head { get; }

    public abstract ImmutableList<T> Tail { get; }

    public abstract bool IsEmpty { get; }

    #region IEnumerable<T> Members

    public IEnumerator<T> GetEnumerator()
    {
        var current = this;
        while (!current.IsEmpty)
        {
            yield return current.Head;
            current = current.Tail;
        }
    }

    #endregion

    #region IEnumerable Members

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

    #endregion
}

internal sealed class EmptyImmutableList<T> : ImmutableList<T>
{
    public EmptyImmutableList() { }

    public override T Head
    {
        get
        {
            throw new InvalidOperationException("an empty list has no head.");
        }
    }

    public override ImmutableList<T> Tail
    {
        get
        {
            throw new InvalidOperationException("an empty list has no tail.");
        }
    }

    public override bool IsEmpty { get { return true; } }
}

internal class NonEmptyImmutableList<T> : ImmutableList<T>
{
    public static ImmutableList<T> FromEnumerable(IEnumerable<T> elements, ImmutableList<T> tail)
    {
        NonEmptyImmutableList<T> result = null, last = null;

        foreach (var item in elements)
        {
            var newNode = new NonEmptyImmutableList<T>(item, Empty);
            if (last == null)
            {
                result = last = newNode;
            }
            else
            {
                last.m_tail = newNode;
                last = newNode;
            }
        }

        if (last != null)
        {
            last.m_tail = tail;
        }

        return result ?? tail;
    }

    public NonEmptyImmutableList(T head, ImmutableList<T> tail)
    {
        this.m_head = head;
        this.m_tail = tail;
    }

    private T m_head;
    public override T Head { get { return this.m_head; } }

    private ImmutableList<T> m_tail;
    public override ImmutableList<T> Tail { get { return this.m_tail; } }

    public override bool IsEmpty { get { return false; } }
}