Explain?
That being said, whether data sharing is a good thing or not depends on the situation. For example, copying to a cache can expose more memory parallelism in an application. I feel like you are taking this opportunity to take a jab at FP here ("the purists detest mutation"). While FP is my preferred paradigm of development, I wasn't trying to push it on anyone--I was merely making a technical point.
If you do happen to be doing something where the difference is truly going to matter, or you're writing a library anticipating needing that kind of performance, using mutability internally in your functions isn't discouraged as long as they remain referentially transparent: http://clojure.org/transients
Likewise mutable data structures while not the default, can be implemented in Haskell, they just have some caveats attached and shouldn't be used lightly. In other words, all things being equal, use the immutable data structure, but if you have a good reason to, you can use a mutable data structure instead, just be sure you know what you're getting into.
:) You could say that "all things being equal" never happens because mutable data structures have worse persistence if they're not used in a way that their performance matters. But also, different defaults make sense for different problem domains.
I was a bit confused because O(log_32(n)) = O(log(n)) = log(32)+log(n) = O(log(32n)), so no matter how I parsed it I would just get O(log(n)) :)
Eventually by the time they came to an agreement on hash tables (C++11), a lot of vendors had their own versions of it as non-standard additions to the library. To avoid conflicts with these existing hash tables, they named it "unordered_map".
> Many operations have a worst-case complexity of O(min(n,W)). This means that the operation can become linear in the number of elements with a maximum of W -- the number of bits in an Int (32 or 64).
[1] http://hackage.haskell.org/packages/archive/hashmap/1.3.0.1/... [2] http://hackage.haskell.org/packages/archive/containers/lates...
In the face of these techniques (and others, e.g. re-structuring things to use zippers and being clever manually or whatever), I suspect the actual amount of redundant data might be quite a bit less than you might think.
Pure FP = don't mutate variables in the program. Of course the actual implementation can reuse memory blocks or else pure FPers would have to keep buying new memory!
So, no, even in pure functions like
f x = x + 1
From http://en.wikipedia.org/wiki/Variable_(mathematics):
"Varying, in the context of mathematical variables, does not mean change in the course of time, but rather dependence on the context in which the variable is used."
"The identifier in computer source code can be bound to a value during run time, and the value of the variable may thus change during the course of program execution. Variables in programming may not directly correspond to the concept of variables in mathematics."
val y = Console.readInt
var x = y + 1
x = y + 2 //valid
y = 5 //error, vals can't be changed in the same block- val a = 1;
val a = 1 : int
- fun f() = a;
val f = fn : unit -> int
- f();
val it = 1 : int
- val a = 2;
val a = 2 : int
- f();
val it = 1 : int // a is still bound to 1 as far as f() is concerned
Now in Javascript:
> var a = 1;
undefined
> function f(){return a};
undefined
> f();
1
> a = 2;
2
> f();
2
>
If you bind a val, then you define a function that references that val, then you later shadow the val binding, then call the function again, the function still sees the earlier val binding, because it's a closure of the environment at the point where the function was defined, not at the point where it was called. This is unlike variable assignment in imperative languages.
For example, in programs with mutable state, it's not uncommon for modules to return deep copies of objects to avoid mutation-related bugs. Java's String objects are immutable precisely to avoid having to do this.
It's the opposite: functional programs prefer immutable data and the only way to achieve this is to copy a lot more data than you would if you were just overwriting existing objects.