10.6. Functional Immutable

  • Purely functional data structures have persistence

  • (keeps previous versions of the data structure unmodified)

The array with constant access and update times is a basic component of most imperative languages, and many imperative data-structures, such as the hash table and binary heap, are based on arrays. Arrays can be replaced by maps or random access lists, which admit purely functional implementation, but have logarithmic access and update times. Source: [1]

Variables are immutable, i.e., it isn't possible to modify one once it has been initialized. However, we can create a new variable. The immutable nature of variables helps preserve the state throughout the program. [2]

Mutable:

>>> data = [1, 2, 3]
>>> id(data)  
4505485888
>>>
>>> data += [4, 5, 6]
>>> id(data)  
4505485888
>>>
>>> data
[1, 2, 3, 4, 5, 6]

Immutable:

>>> data = (1, 2, 3)
>>> id(data)  
4506214016
>>>
>>> data += (4, 5, 6)
>>> id(data)  
4502812416
>>>
>>> data
(1, 2, 3, 4, 5, 6)

10.6.1. Mutable vs. Immutable

../../_images/fp-immutable-tuple.png
../../_images/fp-immutable-str.png
../../_images/fp-immutable-tables.png

10.6.2. Changes

../../_images/fp-immutable-sharedstate.png

10.6.3. Immutable Types

  • int

  • float

  • complex

  • bool

  • None

  • str

  • bytes

  • tuple

  • frozenset

  • mappingproxy

10.6.4. Mutable Types

  • list

  • set

  • dict

10.6.5. Comparison

Table 10.1. Comparison

Immutable

Mutable

int

float

complex

bool

None

str

bytes

bytearray

tuple

list

frozenset

set

mappingproxy

dict

NamedTuple

namedtuple

array

TypedDict

dataclass(frozen=True)

dataclass(frozen=False)

10.6.6. Computational Complexity

  • Usually immutable types are faster

  • Date: 2024-12-16

  • Python: 3.13.1

  • IPython: 8.30.0

  • System: macOS 15.2

  • Computer: MacBook M3 Max

  • CPU: 16 cores (12 performance and 4 efficiency) / 3nm

  • RAM: 128 GB RAM LPDDR5

>>> def increment(x):
...     return x + 1

Tuple:

>>> data = tuple(range(0,100))
>>>
>>> # doctest: +SKIP
... %%timeit -n 1000 -r 1000
... tuple(map(increment, data))
...
2.49 μs ± 119 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
2.49 μs ± 90.6 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
2.48 μs ± 122 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
2.48 μs ± 88.8 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
2.48 μs ± 86.2 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)

List:

>>> data = list(range(0,100))
>>>
>>> # doctest: +SKIP
... %%timeit -n 1000 -r 1000
... list(map(increment, data))
...
2.56 μs ± 84.8 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
2.56 μs ± 115 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
2.57 μs ± 95.5 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
2.57 μs ± 108 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)
2.57 μs ± 85.8 ns per loop (mean ± std. dev. of 1000 runs, 1,000 loops each)

10.6.7. Memory Complexity

  • Usually immutable types are more memory efficient

>>> from sys import getsizeof
>>>
>>> a = (1, 2, 3)
>>> b = [1, 2, 3]
>>>
>>> getsizeof(a)
64
>>> getsizeof(b)
88

10.6.8. Array

Return a new array whose items are restricted by typecode, and initialized from the optional initializer value, which must be a list, string or iterable over elements of the appropriate type.

Arrays represent basic values and behave very much like lists, except the type of objects stored in them is constrained. The type is specified at object creation time by using a type code, which is a single character. The following type codes are defined:

Table 10.2. Comparison

Type code

C Type

Minimum size in bytes

'b'

signed integer

1

'B'

unsigned integer

1

'u'

Unicode character

2 (see note)

'h'

signed integer

2

'H'

unsigned integer

2

'i'

signed integer

2

'I'

unsigned integer

2

'l'

signed integer

4

'L'

unsigned integer

4

'q'

signed integer

8 (see note)

'Q'

unsigned integer

8 (see note)

'f'

floating point

4

'd'

floating point

8

SetUp:

>>> from array import array

Define:

>>> data = array('b')  # 8 bit signed integer -> values from -128 to 127

Use:

>>> data.append(0)
>>> data.append(1)
>>> data.append(127)
>>> data.append(128)
Traceback (most recent call last):
OverflowError: signed char is greater than maximum

>>> data.append(-1)
>>> data.append(-128)
>>> data.append(-129)
Traceback (most recent call last):
OverflowError: signed char is less than minimum

10.6.9. Mutable Dataclass

>>> from dataclasses import dataclass

>>> @dataclass
... class Point:
...     x: int
...     y: int

>>> pt = Point(x=1, y=2)
>>> pt.x = 10
>>> pt.y = 20
>>> pt
Point(x=10, y=20)
>>>
>>> pt.z = 30
>>> pt
Point(x=10, y=20)
>>>
>>> vars(pt)
{'x': 10, 'y': 20, 'z': 30}

10.6.10. Immutable Dataclass

>>> from dataclasses import dataclass

>>> @dataclass(frozen=True)
... class Point:
...     x: int
...     y: int

>>> pt = Point(x=1, y=2)
>>> pt.x = 10
Traceback (most recent call last):
dataclasses.FrozenInstanceError: cannot assign to field 'x'
>>>
>>> pt.x = 20
Traceback (most recent call last):
dataclasses.FrozenInstanceError: cannot assign to field 'x'
>>>
>>> pt
Point(x=1, y=2)
>>>
>>> pt.z = 30
Traceback (most recent call last):
dataclasses.FrozenInstanceError: cannot assign to field 'z'
>>>
>>> pt
Point(x=1, y=2)

10.6.11. References