I doubt you'll see that - at least in CPython. Guido's been very clear about how he feels about implementing functional paradigms in Python, so it will probably never support functional programming in the standard implementation - just a bit in syntax/interface.
I honestly don't understand that. Data structures are just code ... isn't it much more work to change syntax and interfaces instead of adding some decent implementations of data structures to the library?
The syntax changes happened very much against Guido's will - he actively tried to remove lambda (and I believe map as well) for quite a while.
Anyone can write whatever Python libraries they want, but I doubt anything of the sort would be added to the standard library, and certainly nothing that would require an FP-aware interpreter to optimize in a useful way.
“… a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure.”
There are situations where balanced search trees are appropriate. A general purpose priority queue (with delete and decrease-key operations); there's actually code for this in the _documentation_ of the heapq module; this seems really odd to me, why not just include it? It's also a shame that heapq is built on list instead of being a first-class data-structure, it feels bolted-on. Bitwise tries would be nice as well.
Even if heaps were a first class data-structures wouldn't the choice between trees and lists exist in the underlying implementation? Ultimately you would have to allow for both or deal with the strengths and weaknesses of that implementation.
As far as I know array-based heaps are most efficient with practical workloads (because it doesn't have the overhead & non-locality due to pointers for a tree structure). I don't think it's necessary to offer multiple implementations, just as there is only a single well tuned hash table in Python. What matters is that the functionality of an abstract data type is offered.
