where FP seeks to make most things pure
I made this mistake for ages because Haskell is so popular and it's functional and pure, but it's not actually a requirement for functional languages to be pure. OCaml isn't.
When I read Rust code, I have to completely shift my thinking to something much more imperative.
I agree Rust code has a different feel to OCaml code but that's because it makes some things easier (e.g. mutation, vectors). You still could write Rust as if it was OCaml (except for the lack of currying), it's just that nobody does that because it sucks.
I think we're probably agreeing, it's just that "functional programming" is extremely poorly defined and we're interrupting it differently. You're thinking "a language where people write enormous nested expressions and over-use recursive functions and linked lists" and I'm thinking "a language that supports lots of features common in the FP paradigm: first class functions, pattern matching, expression based not statement based, iterators/map/filter/reduce, currying, tagged unions/sum types, etc."