4 ms·

Curious, I've been hearing a lot lately about functional languages and immutability and wasn't quite sure how it worked. I agree with it in premise but it seems

Curious, I've been hearing a lot lately about functional languages and immutability and wasn't quite sure how it worked. I agree with it in premise but it seems like all these immutable data structures introduce massive overhead. What is going on behind the scenes when I modify a single value in an array with 10k members? Surely it's not going to create an entirely new array.

programminggeek 12y ago
It might do that wildly inefficient thing... Or, you might do something where you have a list of pointers, and you point at a different value instead of mutating an existing value. I haven't dug into the details of how immutable data structures can be made to work efficiently, but part of the charm is that in many cases you don't mutate the array at all. What I mean is, there are certain behaviors around mutation that programmers do because they can. When you take away the ability to mutate data, you design differently and without side effects. All of a sudden testing becomes easier, faster, cheaper for large parts of your codebase. You have simpler solutions that are potentially easier to reason about because the complex (and sometimes elegant) solutions aren't so readily available. A few talks that are around this style of thinking: https://www.destroyallsoftware.com/talks/boundaries https://www.destroyallsoftware.com/talks/boundaries https://www.youtube.com/watch?v=WpkDN78P884 https://www.youtube.com/watch?v=WpkDN78P884 https://www.youtube.com/watch?v=tq5SQ4W3gRI https://www.youtube.com/watch?v=tq5SQ4W3gRI http://www.infoq.com/presentations/Simple-Made-Easy http://www.infoq.com/presentations/Simple-Made-Easy Boundaries are good, values are good, simple things that work together are good. The more we can take the good parts and form them together into a cohesive language/framework/platform, the better our software will be.
rdc12 12y ago
This book is more or less the definitive book on functional persistent data structures. More about how to design and reason about them, then a collection book. http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...
Dewie 12y ago
> Curious, I've been hearing a lot lately about functional languages and immutability and wasn't quite sure how it worked. I agree with it in premise but it seems like all these immutable data structures introduce massive overhead. There is some seemingly inherent overhead for certain data structures. On the other hand it allows for structural sharing, and plays more nicely with concurrency and whatnot. Suffice it to say that you'd be wise to design your immutable (persistent, specifically) data structures very differently to how you would design your regular imperative data structures. There was a famous PhD dissertation - now a book - on the topic. You'll find it easily enough if you search for it. Yes, immutable data structures seem very inefficient. But they're implemented in a more clever way than to just take regular imperative data structures and copying for every "update" instead of directly mutating. > What is going on behind the scenes when I modify a single value in an array with 10k members? Surely it's not going to create an entirely new array. It would be unwise to use a huge array (in the usual sense - contiguous memory) like that to begin with. You'd probably have an "array" that is more in the shape of a tree, which facilitates more efficient "updates".

programminggeek 12y ago

It might do that wildly inefficient thing... Or, you might do something where you have a list of pointers, and you point at a different value instead of mutating an existing value. I haven't dug into the details of how immutable data structures can be made to work efficiently, but part of the charm is that in many cases you don't mutate the array at all. What I mean is, there are certain behaviors around mutation that programmers do because they can. When you take away the ability to mutate data, you design differently and without side effects. All of a sudden testing becomes easier, faster, cheaper for large parts of your codebase. You have simpler solutions that are potentially easier to reason about because the complex (and sometimes elegant) solutions aren't so readily available. A few talks that are around this style of thinking: https://www.destroyallsoftware.com/talks/boundaries https://www.destroyallsoftware.com/talks/boundaries https://www.youtube.com/watch?v=WpkDN78P884 https://www.youtube.com/watch?v=WpkDN78P884 https://www.youtube.com/watch?v=tq5SQ4W3gRI https://www.youtube.com/watch?v=tq5SQ4W3gRI http://www.infoq.com/presentations/Simple-Made-Easy http://www.infoq.com/presentations/Simple-Made-Easy Boundaries are good, values are good, simple things that work together are good. The more we can take the good parts and form them together into a cohesive language/framework/platform, the better our software will be.

rdc12 12y ago

This book is more or less the definitive book on functional persistent data structures. More about how to design and reason about them, then a collection book. http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 http://www.amazon.com/Purely-Functional-Structures-Chris-Oka...

Dewie 12y ago

> Curious, I've been hearing a lot lately about functional languages and immutability and wasn't quite sure how it worked. I agree with it in premise but it seems like all these immutable data structures introduce massive overhead. There is some seemingly inherent overhead for certain data structures. On the other hand it allows for structural sharing, and plays more nicely with concurrency and whatnot. Suffice it to say that you'd be wise to design your immutable (persistent, specifically) data structures very differently to how you would design your regular imperative data structures. There was a famous PhD dissertation - now a book - on the topic. You'll find it easily enough if you search for it. Yes, immutable data structures seem very inefficient. But they're implemented in a more clever way than to just take regular imperative data structures and copying for every "update" instead of directly mutating. > What is going on behind the scenes when I modify a single value in an array with 10k members? Surely it's not going to create an entirely new array. It would be unwise to use a huge array (in the usual sense - contiguous memory) like that to begin with. You'd probably have an "array" that is more in the shape of a tree, which facilitates more efficient "updates".