Extreme Cleverness: Functional Data Structures in Scala - Daniel Spiewak
Why Stack Overflow recommends it
Stack Overflow users link it when explaining how immutable Scala collections reuse structure between versions and what the real allocation costs are.
Recommended by 2 people across 2 different months, 2014 to 2018.
What it is
Daniel Spiewak's conference talk walks through the theory and Scala implementation of six functional, persistent data structures, with diagrams. It ends by looking at how hardware architecture and JVM constraints shape data structure design in ways the theory does not show.
Cited in 1 Wikipedia article, including Persistent data structure.
What people said
Recommends Rüdiger Klaehn · 2014-12 · Stack Overflow · on “Cost of Scala's immutable object creation”
The question is very generic, so it is hard to give a definite answer. It seems that you are just uncomfortable with the amount of object allocation happening in idiomatic scala code using for comprehensions and the like. The scala compiler does not do any special magic to fuse operations or to elide object allocations. It is up to the person writing the data structure to make sure that functional data structures reuse the as much as possible from previous versions (structural sharing). Many of the data structures used in scala collections do this reasonably well. See for example this talk about Functional Data Structures in Scala [this video] to give you a general idea. If you are interested in
Recommends GlenPeterson · 2015-10 · Stack Overflow · on “what's a good persistent collections framework for use in java?”
Paguro provides type-safe versions of the actual Clojure collections [LINK] for use in Java 8+. It includes: List (Vector), HashMap, TreeMap, HashSet, and TreeSet. They behave exactly the way you specify in your question and have been painstakingly fit into the existing java.util collections interfaces [LINK] for maximum type-safe Java compatibility. They are also a little faster than PCollections [LINK] . Coding your example in Paguro looks like this: // List with the elements (a,b,c) ImList<T> list = vec(a,b,c); // With a persistent list, when I call list.add(d), // I get back a new list, holding (a,b,c,d) ImList<T> newList = list.append(d); list.size(); // still returns 3 newList.size();
Cites user51 · 2018-01 · Stack Overflow · on “What goes on behind the scenes when adding immutable collections in Scala?”
The data structures in functional programming languages are not just simply immutable(their reference can't be changes once it is created) but also persistent. By persistent means it reuses the existing collection for some of the operations. For example, in Scala prepending an element to the list is optimized(So when you are using list, you should think append operation as kind of pushing an element to stack). Similarly, other collections are optimized as well for other operations. I gave you few references that help you to get more understanding on persistent data structures in functional programming. Persistent data structures in Scala [LINK] 2. [LINK] [this video] [LINK]