List, tuples and arrays, oh my! (N00b question)

Questions / Help
,
1

After a (too) long forced timeout from Elixir in “J-world” (no questions, please, I’m trying to block it out), I can again focus on my two new-found loves: Elixir, Haskell, and Elm… My three greatest loves: Elixir, Haskell, Elm, and Rust… my FOUR greatest loves (please tell me someone got the reference. :))

Jokes aside, I’ve been hitting Programming Elixir from the beginning and since I’m also doing an “Algorithms and data structures” course right now I’ve got a question about Elixir’s data structures:
Elixir doesn’t have arrays, per se, “out-of-the-box”. The closest equivalent of those would be the tuple.

The tuple is contiguous in memory, has an O(1) random access, so on, so forth.
However, Elixir also is immutable: if I make a change to an element in the tuple it will return a completely new tuple.

More so, if I append to a tuple it will return a new tuple that references the old, sort of: {old tuple | new element} (yes, I know this is List syntax, but you get what I mean).

So, is the new tuple also O(1)? especially if I’m trying to access an element from the “old” tuple?
And if I did change an element, a new tuple is created… while the new one is contiguous in memory, creating it will be O(N), right? Since I have to traverse the old tuple, copy-pasting all values to the new one, other than the one I changed?

Or have I got Elixir’s data structures completely wrong?

Thanks in advance for replies and, it’s good to be back!

2

This is not true, when you append to a tuple, a new tuple of the new size will be created, old content will be copied from the shorter tuple and your new elements will be copied into the remaining slots.

Therefor your remaining questions are obselete.

Depending on the contents of the old tuple, it may be, that not complete content is copied, but only references to the old content, but this is an implementation detail that we do not need to care about here.

All you need to know is, that reading from a tuple is guaranteed to be O(1), writing is always O(n) since you need to copy it.

1 Like
3

Your reference is about one of the biggest problem in computer science, off-by-one error :smile:

4

I got the reference… though I wasn’t (ahem) expecting it.

1 Like