P
Paul Rubin
Steven D'Aprano said:You don't think Python's dict implementation is functional?
I'm using the term "functional" in the sense of Chris Okasaki's book
"Purely Functional Data Structures". Basically a functional dictionary
is an immutable dictionary that supports fast "update" operations
by letting you quickly make a new dictionary that shares structure
with the old one. For example, if d is a functional dictionary, then
e = d.update(("name", "joe"))
would be something like Python's
e = d.copy()
e["name"] = "joe"
except that it would not incur the overhead of copying d completely
and instead would usually take O(log n) operations where n is the
number of entries in d. Among other things this makes it trivial
to implement rollback for dictionaries, multiple views of the same
data, etc.
Functional dictionaries are normally implemented using balanced tree
structures such as red-black trees as their association mechanism,
rather than hash tables.