You don't really need full tail-call optimization as long as your map/filter/reduce is optimized. Nearly everything can be expressed as combinations of those.

Actually, if you have generalized folds (folds over all data types, not just lists), all recursion can be expressed in terms of a fold. That's the point of a fold function: it captures the recursion pattern over a data type, letting you parameterize just the specific operation that replaces the constructor.

In practice, I found that the mutability of basic structures was more of a problem. By default, your subscripting/attribute assignment all mutate the original object instead of creating new ones. When I did FP in Python, I did a few decorators to hide this, but it still felt like an ugly kludge that was fighting the language.

Yes, that's a problem, too. E.g. dictonaries would need to be replaced by something persistent like balanced trees.