What is a destructive update?

I 开发者_JAVA技巧see a lot of functional programming related topics mention destructive updates. I understand that it is something similar to mutation, so I understand the update part. But what is the destructive part? Or am I just over-thinking it?

You're probably overthinking it a bit. Mutability is all there is to it; the only thing being "destroyed" is the previous value of whatever you mutated.

Say you're using some sort of search tree to store values, and you want to insert a new one. After finding the location where the new values goes, you have two options:

• With an immutable tree, you construct new nodes along the path from the new value's location up to the root. Subtrees not along the path are reused in the new tree, and if you still have a reference to the original tree's root you can use both, with the common subtrees shared between them. This economizes on space with no extra effort if you have lots of slightly-different copies floating around, and of course you have all the usual benefits of immutable data structures.

• With a mutable tree, you attach the new value where it belongs and that's that; nothing else has to be changed. This is almost always faster, and economizes on memory allocation if you only ever have one copy around, but anything that had a reference to the "old" tree now has a reference to the new one. The original has been destroyed; it's gone forever. If you need to keep the original around, you have to go to the expense of creating an entirely new copy of the whole thing before changing it.

If "destruction" seems an unnecessarily harsh way to describe a simple in-place update, then you've probably not spent as much time as I have debugging code in order to figure out where on Earth some value is being changed behind your back.

The imperative programming languages allow variables to be redefined, e.g

x = 1
x = 2

So x first has the value 1 then, later, it has the value 2. The second operation is an destructive update, because x looses its initial definition as being equal to 1.

This is not how definition is handled in common mathematics. Once defined, a variable keeps its value. The above, seen as system of equations, would allow to subtract the first from the second equation, which would give

x - x = 2 - 1 <=> 0 = 1

which is a false statement. It is assumed that once introduced, x is the same.

A familiar statement like

x = x + 1

would lead to the same conclusion.

The functional languages have the same use of variables, once they are defined it is not possible to reassign them. The above statement would turn into

x2 = x + 1

and we would have no for or while loop but rather recursion or some higher order function.