If you have an immutable list, you expect it to always return a reference to the same object when you ask for, say
list.get(0)
My question is, would you expect to be able to mutate the object and have the mutation reflected next time you get it from the list?
That's usually to be expected. The list is immutable, which means you cannot add or remove items in it or replace items entirely. If you want those items to be immutable you have to take care of that yourself. The list certainly can't stop you from mutating the object's state once you got a reference to it.
It depends on the context. In a general purpose library, all we should assume is that the list is immutable. Changes to the elements in the list would be reflected to all callers, as a direct consequence of returning the same reference each time.
However, if this is a specialized immutable tree (or whatever), and is documented as such then you would expect the items in the list to themselves be immutable, and it becomes a moot question.
Yes, knowing Java, for an "immutable" List<T> I wouldn't expect T to be immutable unless T was immutable. However, a reasonable implementation of, say, List<Date> would be to copy the Date each time. The problem is that Date is mutable and can be distinguished from other equal Dates.
The question if not about the immutability of the list, but about the immutability of the objects contained.
In fact, if you have reference types, the immutable entity in the list is the reference. This means that the reference will always be the same. Now whether the referenced object changes only depends on what kind of object it is. If the object is immutable (like, for instance, strings in both .NET and Java, or all value types in .NET), the object cannot change.
Otherwise, the object can change and all other references to the same object will see the changed state, since they hold a reference to the same instance. Therefore, as I wrote in the beginning, this is completely independent of the list (and whether it is immutable or not).
Yes.
I don't expect an immutable list to clone its objects when I get them, unless it is documented as doing so.
It really depends on the context in which you ask that question. Any experienced Java or C# developer knows that it's technically almost impossible to have a general "deep immutability" and therefore would not expect this. In C++, it's a very complex topic, so most developers probably also don't expect a dependable deep immutability. The D programming language, on the other hand, does have a language-level concept of transitive immutability, so a D programmer would probably expect it wherever it makes sense (which is quite often).