In practice, functional languages typically use persistent data structures, which represent collections such as dictionaries, vectors, sets internally as trees. Adding, removing and updating data requires changing a path in this tree while sharing the remaining of the structure. It is not a deep a copy and a really large map won't be very expensive to modify. Rich Hickey has a good talk on the matter:
https://www.youtube.com/watch?v=dzP05hEDNvsThere are also optimizations that are straight-forward to understand and implement once you assume immutability. For example, take the following function in Elixir:
def some_list do
[1, 2, 3]
end
Because a list is immutable, when code is compiled we put such data structures that appear literally in the code into something called a literal pool. Anything in literal pool is loaded when the code is loaded. Now every time you call that function, we return the same list and we don't create new instances/copies on every call. That list may be embedded in a map, another list, whatever, and still point to the same memory representation because nothing will ever change it.
Here is an example that leverages this in the context of a web framework for great rendering performance https://www.bignerdranch.com/blog/elixir-and-io-lists-part-2.... While this is definitely achievable in other languages, we get it pretty much for free with immutable data structures and it is a natural mechanism to reason about. IanCal talked about it a couple comments above: https://news.ycombinator.com/item?id=13498532
Regardless, you are still correct when you say that mutations are useful. There are many algorithms that will be more performant if implemented on top of mutations. Luckily, most functional programming languages, including the pure ones, provide mutable data structures or memory references for such cases. For example, when working on GenStage/Flow for Elixir, I optimized the hot paths by using mutable dictionary and called it a day.
Many claim immutable data structures are a better "default" for writing software since it is conceptually simple to reason about code when data cannot change right under your feet. However, I won't try to argue if this is actually the case or not, as this reply is already quite long as is. The point is that many concerns regarding immutable data structures are solved and functional languages also provide alternate paths when you need mutability.