Immutable or not immutable?

Question

Ok, as I understand it, immutable types are inherently thread safe or so I've read in various places and I think I understand why it is so. If the inner state of an instance can not be modified once the object is created there seems to be no problems with concurrent access to the instance itself.

Therefore, I could create the following List:

class ImmutableList<T>: IEnumerable<T>
{
    readonly List<T> innerList;

    public ImmutableList(IEnumerable<T> collection)
    {
         this.innerList = new List<T>(collection);
    }

    public ImmutableList()
    {
         this.innerList = new List<T>();
    }

    public ImmutableList<T> Add(T item)
    {
         var list = new ImmutableList<T>(this.innerList);
         list.innerList.Add(item);
         return list;
    }

    public ImmutableList<T> Remove(T item)
    {
         var list = new ImmutableList<T>(this.innerList);
         list.innerList.Remove(item);
         return list;
    } //and so on with relevant List methods...

    public T this[int index]
    {
        get
        {
            return this.innerList[index];
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return innerList.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return ((System.Collections.IEnumerable)this.innerList).GetEnumerator();
    }
}

So the question is: Is this really an immutable type? Is it really thread safe?

Obviously the type itself is immutable but there is absolutely no garantee that T is and therefore you could have concurrent access and threading issues related directly with the generic type. Would that mean that ImmutableList should be considered mutable?.

Should class ImmutableList<T>: IEnumerable<T> where T: struct be the only type truly considered immutable?

Thanks for any input on this issue.

UPDATE: A lot of answers/comments are concentrating on the particular implementation of ImmutableList I've posted which is probably not a very good example. But the issue of the question is not the implementation. The question I'm asking is if ImmutableList<MutableT> is really an immutable type considering everything that an immutable type entails.

Answer 1

If the inner state of an instance can not be modified once the object is created there seems to be no problems with concurrent access to the instance itself.

That is generally the case, yes.

Is this really an immutable type?

To briefly sum up: you have a copy-on-write wrapper around a mutable list. Adding a new member to an immutable list does not mutate the list; instead it makes a copy of the underlying mutable list, adds to the copy, and returns a wrapper around the copy.

Provided that the underlying list object you are wrapping does not mutate its internal state when it is read from, you have met your original definition of "immutable", so, yes.

I note that this is not a very efficient way to implement an immutable list. You'd likely do better with an immutable balanced binary tree, for example. Your sketch is O(n) in both time and memory every time you make a new list; you can improve that to O(log n) without too much difficulty.

Is it really thread safe?

Provided that the underlying mutable list is threadsafe for multiple readers, yes.

This might be of interest to you:

http://blogs.msdn.com/b/ericlippert/archive/2011/05/23/read-only-and-threadsafe-are-different.aspx

Obviously the type itself is immutable but there is absolutely no garantee that T is and therefore you could have concurrent access and threading issues related directly with the generic type. Would that mean that ImmutableList<T> should be considered mutable?.

That's a philosophical question, not a technical one. If you have an immutable list of people's names, and the list never changes, but one of the people dies, was the list of names "mutable"? I would think not.

A list is immutable if any question about the list always has the same answer. In our list of people's names, "how many names are on the list?" is a question about the list. "How many of those people are alive?" is not a question about the list, it is a question about the people referred to by the list. The answer to that question changes over time; the answer to the first question does not.

Should class ImmutableList<T>: IEnumerable<T> where T: struct be the only type truely considered immutable?

I'm not following you. How does restricting T to be a struct change anything? OK, T is restricted to struct. I make an immutable struct:

struct S
{
    public int[] MutableArray { get; private set; }
    ...
}

And now I make an ImmutableList<S>. What stops me from modifying the mutable array stored in instances of S? Just because the list is immutable and the struct is immutable doesn't make the array immutable.