Elm 0.12.1: Fast immutable arrays
elm-lang.org
elm-lang.org
a persistent data structure is a data structure that always preserves the previous version of itself when it is modified
An immutable array is just an array that never changes. A persistent array allows you to do operations on immutable arrays which returns new immutable arrays that is the old immutable array with the operation performed.
[Edit] As sgk284 pointed out elsewhere in the thread, my last paragraph mischaracterises the situation slightly.
An immutable array with any operations defined on it will necessarily be persistent, so it was misleading to say 'is _just_ an array that never changes'.
To the people using that definition of persistent, "immutable" just means constant, i.e. no insertion or deletion at all.
Immutability is a common way of achieving persistence, but fundamentally a persistent data structure simply preserves previous versions. This can be achieved through some mutability via things like fat nodes[1].
It turns out that when you use immutability, many other nice properties often fall out from that decision. You can absolutely insert and delete into an immutable data structure though. You'll simply get back a new structure.
[1] http://en.wikipedia.org/wiki/Persistent_data_structure#Fat_N...
The use of efficient persistent maps in Clojure, and the fact Rich Hickey explains that in most of the early Clojure introductory talks, has popularised it outside of academia.
I miss those email clients. They were much nicer than most of the email software which is considered modern today.
[1] https://github.com/clojure/core.rrb-vector [2] https://github.com/clojure/data.avl
ahh, found it. http://swannodette.github.io/mori/
The fact that elm announces constant array access will not surprise anybody, as this is an inherent property of arrays. But then seeing that they have to use radix-trees for arrays and announcing it as constant is highly misleading. These guys should switch over to politics.
And this only holds for immutable arrays! So even without push,pop,shift,unshift they have to use trees for arrays.
So the absolute worst case scenario - even if we get science fiction computing - is a small, constant number of indirections.
The whole purpose of this type of analysis is to get an intuitive approximation as input size grows. The graphs for log32(n) and 1 will be essentially indistinguishable, and most programmers have a much clearer understanding of constant time versus O( log32( n ) ).
It is not misleading, it is a simplification that is absolutely valid to make.
[1] https://blogs.oracle.com/bonwick/entry/128_bit_storage_are_y...
What the article calls "constant time in practice" is necessary, but not sufficient.
As you say, it's not correct to say that CTIP means that you're fast - after all, you could make a HTTP request per array access and maintain constant time.
But you can say that taking advantage of CTIP allows you to achieve speed.
In my opinion, it takes quite an uncharitable reading of the article for it to seem like they mean the former.
[1] (The closest section to your quote) "Elm now has fast immutable arrays. How can that be? Is there such a thing? Thanks to Christian Widera, the new Array library uses some very clever data structures that make common operations like get and set constant time in practice! We will get into the details later in this post, but the big takeaway is that you can have immutability and speed. "
So non-CTIP data structures cannot be fast! There it is again!
This line in particular jumped out at me:
One way to make these trees faster is to increase the “branching factor”.
And we are lead to conclude that the 32-ary tree is faster than the binary tree. But there's necessarily a tradeoff here: a larger branching factor results in fewer node traversals, but more copying and wasted space on insertions and deletions.
So it's not at all obvious that a higher branch factor is faster. After all, in the limit as the branch factor approaches infinity, you recover naive arrays.
Basically I'm begging for benchmarks! It would be very interesting to see the performance effects of adjusting the branch factor.
I can always sort a 32-bit int array in worst case linear time using counting sort, which in theory is better than the worst case runtime of quicksort, O(n²). Is it better in practise? Of course not, the constant factor is just too high, both for time and memory.
The 'constant' vs. 'almost constant' has been covered by other comments.