Menu
I don't understand, how FP compilers make the code dealing with immutable data structures fast, not blow up stack, etc.
For example, insert operation in tree, it has to copy the whole tree before adding the new node and return the copied tree, versus the imperative couterpart that only needs to add a pointer to the new node. If the insert operation is run millions times, it would take a load of memory, and copying will be slower and slower when the tree is bigger. How do FP compilers actually optimize this ?
740
Efficiency issuesFunctional programming languages are typically less efficient in their use of CPU and memory than imperative languages such as C and Pascal. This is related to the fact that some mutable data structures like arrays have a very straightforward implementation using present hardware.
FUNCTIONAL PROGRAMMING IS ABOUT IMMUTABILITY And they make it simple to perform operations that reflect the nature of the language. And you can see from the examples above that you are guided in the direction the language means is best for you. At least if you want to make your data and algorithms thread-safe.
Immutable data structures provides referential transparency which makes it easier to reason about our program locally. Another way to think about it is that every time we execute a pure (referentially transparent) function with the same input, we get the same output.
The immutability is a big thing in a multithreaded application. It allows a thread to act on an immutable object without worrying about the other threads because it knows that no one is modifying the object. So the immutable objects are more thread safe than the mutable objects.
You don't have to copy the whole tree to make a change; you can share most of the structure. See e.g. the diagrams in this blog, or this talk by Rich Hickey on Clojure (see discussion of hash tries about halfway through).
61
The compiler won't really optimize this, it is something you have to program for specifically when coding. Techniques for doing this are explained in the excellent Purely Functional Data Structures (book, thesis).
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
