> [...] large memory allocations due to immutable data structures sounds [...]
Why would there be large memory allocations because of immutable data structures? Btw, you can also use immutable data structure in eg Rust fairly easily. And Haskell also supports mutation and mutable data structures.
However, Haskell can use a lot of memory, but that's more to do with pervasive 'boxing' by default, and perhaps laziness.
No reason. OC probably thinks that immutable data structures are always copied when being operated on.
Yes indeed, unless you use ropes or other specialised structures
Lists aren’t copied on prepend.
Tries (like scala’s Vector) or trie maps (the core map types of Scala, Clojure and probably Haskell?) aren’t copied on updates.
In fact, whether a data structure is an immutable or persistent data structure or merely an unmodifiable data structure (like Kotlin uses) is based on whether it requires full copies on most updates or not. In FP languages, immutable data structures aren’t “specialized” at all.
> whether a data structure is an immutable or persistent data structure or merely an unmodifiable data structure...
This hurt my brain. It seems that in some places (e.g. Java land) unmodifiable refers to something that you can't modify but could just be a wrapper around a structure that can be modified. In that case they use immutable to mean something that is nowhere modifiable.
I may be misrepresenting this idea, but I think the terminology is so poor that it deserves to be misunderstood.
Think about mutability in Java land this way:
// Using mutability.
// `increment` is void, and makes 2 bigger for everyone.
increment(2);
// Typical Java "safety".
// It's still void, but now it throws a RuntimeException
// because the developers are saving you from making everyone's 2 bigger.
increment(2);
// Immutable
// Returns 3
increment(2);Doesn't it depend on the data structure? Eg prepending to a list is actually cheaper with immutable data structures: you keep the original list and add a new head pointing to its head. Now you have two lists available in your program, but only one stored in memory. Yay!
Well luckily, Haskell is full of said "specialized structures."
containers and unordered-containers handle most of your needs and they only copy their trees' spines (O log n) on update.
Not really. You might want to look into “ Purely functional data structures” by Chris Okazaki.