The tools are there but you don't like their names.

Neither tuples nor frozen dicts offer efficient (logarithmic or constant time) updates, like lists or balanced trees or HAMT do. You can't really write a program with only immutable structures in python, unless you accept it will be unbearably slow, even for python. Clojure, erlang, elixir, these are dynamically typed and functional.