Elm 0.12.1: Fast immutable arrays

[millstone]

I think this means to say fast persistent arrays. A fast immutable array is trivial - just use an array!

[anorwell]

I'm not sure what persistent means in this context, but what is meant by "fast" immutable array here is that the immutable array supports operations like insert and delete (returning new immutable objects) in near-constant time.

[pkhuong]

Fast(er) persistent arrays are easier than purely functional ones. See Baker's Shallow Binding Makes Functional Arrays Fast (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.3...). The problem with impure persistence is that it doesn't help concurrent accesses at all.

[tehabe]

When I read elm I thought it was about an email client. I think that makes me officially very old.

I miss those email clients. They were much nicer than most of the email software which is considered modern today.

[moomin]

Couldn't they just use Mori?

[malandrew]

Interesting that you ask this since I just created a new thread asking for advice and information on using mori in my JS code:

https://news.ycombinator.com/item?id=7689823

[JeanPierre]

Mori doesn't implement RRB-trees, thus doesn't support logarithmic concatenation.

[sitkack]

What is Mori?

ahh, found it. http://swannodette.github.io/mori/

[rurban]

Logarithmic is not constant.

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.

[reitzensteinm]

Fully populating a 128 bit memory pool would take enough energy to boil the oceans[1]. This requires a branching factor of 26 to address.

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...

[JeanPierre]

Constant time in practise is a notable difference from saying constant time.

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.

[ajanuary]

Much as I dislike it, not everyone uses 'array' to mean a collection with constant time indexing. Lots of people use it to mean an indexable collection.

The 'constant' vs. 'almost constant' has been covered by other comments.

[pohl]

Given the current rate of progress, what year would you predict that web browser applications use large enough arrays where that distinction makes a practical difference, and not just an academic one?

[tiles]

Why are Elm's arrays so much more complex than JavaScript's O(n) arrays?

[gliptic]

slice/push/get/append can stand in for push/pop/shift/unshift. The immutability of the arrays is considered a feature and Javascript arrays are O(N) for the same operations.