I don't understand "Adding to list has low memory cost, while retaining the immutability that we desire."
I have a list A -> B -> C
I want to add D to the list end.
next(C) == nil?
I expect that next(C) should be D.
I need to mutate C, so I must copy it.
But if C was changed then I need to change B...
So I get full list copy then I add element to the list end.
Looks like this is suboptimal algorithm.
Can you please explain how it really works?
Good point! Yes you're right, I should've clarified by adding I in fact meant prepending.
In the end, it's just a normal linked lists that Elixir uses under the hood, so it inherits the same appending Big O for time. What you're asking is a little more, which is the fact that we have to maintain immutability for structural sharing, so yes you're also right in that regard - we'd need to recopy the entire linked lists and then only append it.
If we look back on my structural sharing example:
list = [5,6,7,8]
list_one = [1 | list]
list_two = [2 | list]
we have 3 lists, but three of them point to the same existing list (structural sharing), but if I choose to append instead:
list_three = [ list | 3 ] # => This creates an entirely new list
Although list_three has the same values [5,6,7,8], it does not point to the same nodes in list_one and list_two. I hope that makes sense!
There's this another really good article that even comes with Benchmark that shows this in action :)
You can also see it on the official language guide here too
We're a place where coders share, stay up-to-date and grow their careers.
We strive for transparency and don't collect excess data.