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.
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!
Hello!
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:
we have 3 lists, but three of them point to the same existing list (structural sharing), but if I choose to append instead:
Although
list_threehas the same values[5,6,7,8], it does not point to the same nodes inlist_oneandlist_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
Just to add to that, some functional languages implement a “copy on write” mechanism that only copies the content of the list when mutated.