A Mutable Type Inside an Immutable Container

a mutable type inside an immutable container

You can always modify a mutable value inside a tuple. The puzzling behavior you see with

>>> thing[0] += 'd'

is caused by +=. The += operator does in-place addition but also an assignment — the in-place addition works just file, but the assignment fails since the tuple is immutable. Thinking of it like

>>> thing[0] = thing[0] + 'd'

explains this better. We can use the dis module from the standard library to look at the bytecode generated from both expressions. With += we get an INPLACE_ADD bytecode:

>>> def f(some_list):
...     some_list += ["foo"]
... 
>>> dis.dis(f)
  2           0 LOAD_FAST                0 (some_list)
              3 LOAD_CONST               1 ('foo')
              6 BUILD_LIST               1
              9 INPLACE_ADD         
             10 STORE_FAST               0 (some_list)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE        

With + we get a BINARY_ADD:

>>> def g(some_list):
...     some_list = some_list + ["foo"]
>>> dis.dis(g)
  2           0 LOAD_FAST                0 (some_list)
              3 LOAD_CONST               1 ('foo')
              6 BUILD_LIST               1
              9 BINARY_ADD          
             10 STORE_FAST               0 (some_list)
             13 LOAD_CONST               0 (None)
             16 RETURN_VALUE        

Notice that we get a STORE_FAST in both places. This is the bytecode that fails when you try to store back into a tuple — the INPLACE_ADD that comes just before works fine.

This explains why the "Doesn't work, and works" case leaves the modified list behind: the tuple already has a reference to the list:

>>> id(thing[0])
3074072428L

The list is then modified by the INPLACE_ADD and the STORE_FAST fails:

>>> thing[0] += 'd'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

So the tuple still has a reference to the same list, but the list has been modified in-place:

>>> id(thing[0])
3074072428L
>>> thing[0] 
['b', 'c', 'd']

Immutable container with mutable content

The simplest option would probably be a standard STL container of pointers, since const-ness is not propagated to the actual objects. One problem with this is that STL does not clean up any heap memory that you allocated. For that take a look at Boost Pointer Container Library or smart pointers.

Python mutable/immutable containers

List, Dictionary: Mutable

Tuple: Immutable

Can tuple be considered both as mutable and immutable based on content

All a tuple does is contain a fixed list of references. Those references cannot be changed, and so this makes a tuple immutable. Whether the referenced objects are mutable is another story, but that's beyond the scope of tuple, so it would not be accurate to say a tuple can be mutable if it references mutable objects.

A mutable container of immutable objects in C++

Your conception of how the vector works is incorrect.

The vector uses the allocator to allocate raw memory. That raw memory does not contain default constructed objects--it's just raw memory.

When you do a push_back (for example) it then uses a placement new to construct an object into the raw memory. Likewise, when you erase an object, it will end up directly invoking its destructor to turn the object back into raw memory.

With a current (C++11 or later) implementation of std::vector, your object doesn't need to support default construction or assignment. Supporting move construction and move assignment should be sufficient. To put them to use, you'd want to use emplace_back instead of push_back though.

Why can tuples contain mutable items?

That's an excellent question.

The key insight is that tuples have no way of knowing whether the objects inside them are mutable. The only thing that makes an object mutable is to have a method that alters its data. In general, there is no way to detect this.

Another insight is that Python's containers don't actually contain anything. Instead, they keep references to other objects. Likewise, Python's variables aren't like variables in compiled languages; instead the variable names are just keys in a namespace dictionary where they are associated with a corresponding object. Ned Batchhelder explains this nicely in his blog post. Either way, objects only know their reference count; they don't know what those references are (variables, containers, or the Python internals).

Together, these two insights explain your mystery (why an immutable tuple "containing" a list seems to change when the underlying list changes). In fact, the tuple did not change (it still has the same references to other objects that it did before). The tuple could not change (because it did not have mutating methods). When the list changed, the tuple didn't get notified of the change (the list doesn't know whether it is referred to by a variable, a tuple, or another list).

While we're on the topic, here are a few other thoughts to help complete your mental model of what tuples are, how they work, and their intended use:

1. Tuples are characterized less by their immutability and more by their intended purpose.
   
   Tuples are Python's way of collecting heterogeneous pieces of information under one roof. For example,
   s = ('www.python.org', 80)
   brings together a string and a number so that the host/port pair can be passed around as a socket, a composite object. Viewed in that light, it is perfectly reasonable to have mutable components.

2. Immutability goes hand-in-hand with another property, hashability. But hashability isn't an absolute property. If one of the tuple's components isn't hashable, then the overall tuple isn't hashable either. For example, t = ('red', [10, 20, 30]) isn't hashable.

The last example shows a 2-tuple that contains a string and a list. The tuple itself isn't mutable (i.e. it doesn't have any methods that for changing its contents). Likewise, the string is immutable because strings don't have any mutating methods. The list object does have mutating methods, so it can be changed. This shows that mutability is a property of an object type -- some objects have mutating methods and some don't. This doesn't change just because the objects are nested.

Remember two things. First, immutability is not magic -- it is merely the absence of mutating methods. Second, objects don't know what variables or containers refer to them -- they only know the reference count.

Hope, this was useful to you :-)

Is an object that contains a fixed set of mutable objects mutable?

From wikipedia:
In object-oriented and functional programming, an immutable object (unchangeable object) is an object whose state cannot be modified after it is created. This is in contrast to a mutable object (changeable object), which can be modified after it is created.

In your example the Puzzle object is mutable because you can change the state of one of its Pieces.

Returning a mutable reference that is behind an immutable reference, passed to the function

You can't create a mutable reference from an immutable one. This means that you need to change &self into &mut self:

impl<'a: 'b, 'b> Bar<'b> {
    fn func(&'a mut self) -> &'b mut Foo {
         self.f
    }
}

And now the your variable needs to be mutable so that you can take a mutable reference to it for the method:

let mut bar = Bar { f: &mut foo };
bar.func(); 

What exactly is being assigned into self (or inside of self.x?) ?

The error message might be a little off. There is no assignment in your code, but you are returning a mutable reference. The only extra thing that a mutable reference would let you do here is to assign self.f or self.f.i.

Definitely this error message can be improved, but it does include a hint to make the &'a self mutable to fix the problem.

Now, your original question:

How is returning a mutable reference that is behind an immutable reference, passed as an argument to the function, handled?

Rust provides a variety of container types for interior mutability, such as Cell and RefCell. These types take the responsibility for ensuring correctness away from the compiler and make it a runtime check. One way of applying a RefCell to your code might be like this:

use std::cell::RefCell;
use std::ops::DerefMut;

struct Foo { i: i32 }

struct Bar<'b> {
    // store the data in a RefCell for interior mutability
    f: &'b RefCell<Foo>
}

impl<'a: 'b, 'b> Bar<'b> {
    // Return a RefMut smart pointer instead of mutable ref, but hide the implementation,
    // just exposing it as something that can be mutably dereferenced as a Foo
    fn func(&'a self) -> impl DerefMut<Target = Foo> + 'b {
         self.f.borrow_mut()
    }
}

fn main() {
    let foo = RefCell::new(Foo { i: 1 });
    let bar = Bar { f: &foo };

    let mut f = bar.func(); 
    f.i = 3;
}

In Haskell, does mutability always have to be reflected in type system?

Short answer: yes.

In Haskell, all variables are technically immutable. Unlike in, say, JavaScript, once you've defined a new variable in Haskell and bound it to an initial value:

let x = expression1 in body1

that's its value forever. Everywhere that x is used in body1, its value is guaranteed to be the (fixed) value of expression1. (Well, technically, you can define a brand new immutable variable x with the same name in body1 and then some of the xs in body might refer to that new variable, but that's a whole different matter.)

Haskell does have mutable data structures. We use them by creating a new mutable structure and binding that to an immutable variable:

do ...
   xref <- newIORef (15 :: Int) 
   ...

Here, the value of xref itself is not the integer 15. Rather, xref is assigned an immutable, undisplayable value that identifies a "container" whose contents are currently 15. To use this container, we need to explicitly pull values out of it, which we can assign to immutable variables:

  value_of_x_right_now <- readIORef xref

and explicitly put values into it:

  writeIORef xref (value_of_x_right_now + 15)

There's obviously much more that can be said about these values, and the way in which they generally need to be accessed via monadic operations in IO or another monad.

But, even setting that aside, it should be clear that the integer 15 and a "container whose contents are initialized to the integer 15" are objects with necessarily different types. In this case, the types are Int and IORef Int respectively.

So, the mutability of data structures will necessarily be reflected at the type level, simply by virtue of the fact that mutability in Haskell is implemented via these sorts of "containers", and the type of a value is not the same as the type of a container containing that value.

---

Related Topics