You basically already have this with a map where the keys are indices and the values are the value. %{0 => "first item", 1 => "second item"} is O(log32(n)). I swear I’ve seen a hex package that implements an array like UI around this.
benwilson512
Author of Craft GraphQL APIs in Elixir with Absinthe
1
mischov
A map with keys as indices isn’t ordered (which is to say, you don’t “basically already have this”, there’s still a lot to do).
RE Hex packages, take your pick: persistent_vector, steady_vector, one of the options in arrays.
But I think it’s important it’s one of the build-in types, with literal notation, pattern matching, etc.
0
benwilson512
Author of Craft GraphQL APIs in Elixir with Absinthe
Clojure’s vector is literally the same thing, they’re both HAMTs. “ordered” is entirely a function of the data structure API, not the memory layout. If you have to hop around in memory at all, then they aren’t “arrays” in the C sense. I’ll grant that the API of a Map is missing some common array operations but in terms of the underlying mechanic, map[i] does the same fundamental thing as (get [1,2,3] 1).
1
mischov
I think I may have sent you down the wrong track by listing a couple of the properties of Clojure’s vectors I think are useful, but I really meant “properties similar to Clojure’s vector in more than just access to items by index in log32N hops and optimized append.”
I appreciate what you’re saying about about a map providing log32 access, and maybe you’re trying to tell me something about implementation of Erlang’s map that I am not understanding, but the implementation of Clojure’s vectors isn’t just an interface around a map.
Of the libraries I linked persistent_vector and steady_vector are built with tuples internally. Only the map array in arrays is implemented using a map. Which is to say, you can build an interface around a map to get something similar to Clojure’s persistent vector, but it’s likely to have different characteristics.
All of which is ignoring my primary point, which is that I think it’s important such a structure be built into the platform (Erlang) so it’s widely available, with literal and pattern matching support, etc. This, like the addition of maps, would give the whole platform an important, universal tool to use in situations where it makes sense, rather than needing to work around the limitations in the provided collections.
1
keathley
I agree with everything you’re saying even though I have 0 expectation that we’ll ever see vectors added to the language.
Also saying you can use a map with integer keys to replace vectors is equivalent to saying you don’t need map and filter because you have for loops.
2
LukeWood
I’m getting on a long flight in a few hours - I may draft up a quick NIFS library with bindings to a mutable vector.
Certainly not “elixir-ey” but I have personally come across a few cases where I needed O(1) access and O(1) insert in my elixir programs
0
OvermindDL1
Eh, but :array doesn’t make big tuples, for example it will make a tree of tuples of size 10 each as I recall, it’s actually very efficient.
I’m curious what was the issue with :array missing a feature? What feature?
Matrex is an awesome BLAS library, if you need speed it’s well worth using.
The first class array type essentially is the Tuple, remember this is an immutable language because it is massively distributed.
The JIT makes them real array’s though, but until the JIT runs they are quite slow (and if certain access patterns are hit they ‘fall back’ to maps).
Yeah that absolutely does not sound like you should be using an array at all…
O(1) really? For both access and insert in an immutable language? Doesn’t sound possible as the very act of ‘inserting’ would mean duplicating the data (O(N)) or pointing to the old data (O(>1), like via a rope structure, which them makes access not O(1) either). I’m unsure how you’d implement such a structure in pure immutability?
1
benwilson512
Author of Craft GraphQL APIs in Elixir with Absinthe
And @mischov this isn’t even easy in mutable languages. O(1) append and prepend in mutable languages works by amortizing resize operation costs over N append or prepend operations. O(1) random inserts (as distinct from overwriting the value at position i) usually requires a more specialized data structure. You can’t do the same amortization trick with arbitrary inserts because you don’t know where you can put buffer space. Traditional arrays are actually O(n) for random inserts or deletions, so using the array’s module or a map is actually an improvement in that sense.
3
mischov
Did you mean to reply to @LukeWood? I haven’t suggested O(1) append and prepend.
Anyhow, if one were trying to build a persistent vector a good approach would probably be Bagwell’s RRB-Tree vector.
this structure allows immutable vector concatenation, insert-at and splits in O(logN) time while maintaining the index, update and iteration speeds of the original vector data structure.
2
sionide21
I don’t know whether there’s an Elixir implementation, but what about a finger tree? It gives constant time access to the beginning and end as well as logarithmic time arbitrary splitting.
3