In it's simplest terms, functional programming is programming without side-effects. Functions take inputs and produce outputs, but the inputs are not modifed. Crudely, pass by value rather than pass by reference.
Traditionally, regex modify their targets in-place rather then producing a modified copy of the original. I don't think that there is any technical reason why a regex-like find & replace facility couldn't be implemented in the functional style. Except maybe efficency, but as many will express, that can be a double edged sword.
Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon