Elixir array-like data structure?

Ah, both of those are fixed in a couple of ways!

For array slicing I’ve found I just use Elixir ranges, like 1..12 or so, simple enough. And making a simple wrapper that just wraps the erlang module but adds support for range indexing and giving it a prettier inspect display is quite simple too.

Wouldn’t surprise me if someone already did it on hex.pm actually?

Those aren’t mutation on the beam, those are sending immutable messages to other locations. The BEAM abstracts mutation via Algebraic Effects, I.E. it’s messages. Editing an array via messages is fine, that’s basically how it would be via a NIF or emulating it via another process, but editing an array in-process would break some invariants, hence the purpose of NIF’s and so forth.

I would highly not recommend it, keep mutation beyond message or NIF (which is still essentially a message as the storage exists beyond the process) bounds. Allowing it in-process will break code invariants.

BEAM has mutability in the form of ETS and IO devices (:file.read, :file.position mutate the state of the device). It’s been working out fine for decades.

I think it would be benefical to have the ability to create a mutable value that is copied when passed between processes. One other restriction might be that a closure can only capture such a value by making an immutable copy. A single process would then be able to mutate the value in place (similarly to process dictionary) but there won’t be any shared mutable state. Because all mutation is localized in a single process, no locks are needed.

I’m pretty sure Erlang won’t get any such thing natively. Still, it would be nice to be able to implement a custom data structure as a NIF with the restrictions I described above, if only Erlang provided hooks that allowed to copy the custom value when it is passed to closures or sent to other processes. It would also be nice to be able to inspect custom data structures as if they were normal terms (like we have custom inspect for MapSet, structs, etc.).

A simple example would be a mutable map that is built incrementally by processing a stream of values:

iex> mmap = Enum.reduce(<stream>, MutableMap.new(), fn item, mmap -> 
       # There's no need to create a new immutable map on every iteration, just
       # reuse the already existing mutable data structure.
       MutableMap.put(mmap, item) 
     end)

iex> IO.inspect mmap
#MutableMap{"foo" => "bar", ...}

# Now that the value is fully built, convert it to a normal map.
iex> MutableMap.as_map(mmap)
%{"foo" => "bar", ...}

Other more useful examples include any kind of array processing algorithm that involves many transient changes before the final result is obtained and can be converted into an immutable value. I can also imagine using a mutable value as part of a gen server’s state since it almost universally stays within a single process and is only updated in gen server callbacks. This would only make sense as a niche optimization though.

I may pitch the idea for Lumen if I get a chance to think it through more thoroughly.

The feature that I was missing with :array was the ability to slice. Also the fact that the textual representation of the array in the console is so ugly and annoying to work with.

Yep!

He did say

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.

Not supported on the BEAM, you’d need to fall to another language, like via a NIF. Mutability in the BEAM world would pretty well break a lot of things.

Ah I didn’t mean with pure immutability - I meant as an option to use impure functions if needed. Definitely a rare case but I’ve come across it myself

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.

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.

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.