А там очень многие методы возвращают новые коллекции, оставляя старые значения неизменными.
Другой вопрос, что никаких технических удобств этому, вроде персистентных коллекций, нету, поэтому сколько-нибудь "горячие" места быстро начинают обращать на себя внимание.