Steven D'Aprano <st...@remove-this-cybersource.com.au> writes: > 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. -- http://mail.python.org/mailman/listinfo/python-list