Immutability, dereferencing, and complex data structures

I’m not sure if I understand you correctly, but given a list [1, 2, 3], you want to alter the second element that the list looks like [1, -2, 3] and change the pointer from the first element to the second as well?

Such that we get this:

old = 1 --->  2 ---> 3 ---> []

garbage =     2
new = 1 ---> -2 ---> 3 ---> []

This would brake my assumption, that I were able to use old as it was before. Also it would brake assumptions of the garbage collector about the structure of the heap (old items never reference newer ones).

If though I got you wron, can you please elaborate?

In your example, what I am suggesting is:

[head | tail] = [ 1 | [2,3] ]

[head2 | tail2] = [ 2 | [3] ]

new_list = [-2] ++ tail2

parent(new_list, head) # => [1, -2, 3]

Under the hood, head’s reference to tail is dereferenced to new_list

However, dereferencing a middle node within linked list isn’t a good use case.

list = [1,2,3,4,5,6,7,8,9,10]

def dereference([head | [remove | keep]], 0, value), 
  do: parent([value] ++ keep, head)

def dereference([head | tail], index, value), 
  do: dereference(tail, index - 1, value)

dereference(list, 6, -7) # => [6, -7, 8, 9, 10]

list # => [1,2,3,4,5,6,-7,8,9,10]

This isn’t the API we want.

The API we want is dereference(...) # => [1,2,3,4,5,6,-7,8,9,10] a brand new list.

Changing a middle node is a bad use case because the traversal is necessary anyways so mutable dereferencing is unnecessary and mutates the data.

The better example would be appending to a linked list, which could now be done in constant time.

list = [1,2,3,4,5,6]

new_list = 
  [-7,8,9,10]
  |> dereference(list)
  # => [1,2,3,4,5,6,-7,8,9,10]

list # => [1,2,3,4,5,6]

list
|> tl
|> tl
|> tl
|> tl
|> tl
|> tl
# => []


new_list
|> tl
|> tl
|> tl
|> tl
|> tl
|> tl
# => [-7,8,9,10]

Under the hood, parent/2 copies list… okay, that’s a linear operation.

So this functionality isn’t the domain of a list because a list already has syntactic sugar and the way it is used, mutative dereferencing would be very counterintuitive.

As a result, a singly linked list would not qualify as a complex data structure, especially given that each parent has only one child.

The use case I have in mind is for a graph. I guess you’d lose the old copy, but if we modify @spec dereference(child, parent)'s API to return the dereferenced subtree, we can store that and still access it if we need it. In the meantime, we DO mutate the parent, meaning we can only access the old version by dereferencing again.

Given that I’m thinking about this functionality for what in Elixir are abstract data types, I no longer think this functionality need be added to Elixir. Rather, dereferencing can be implemented using an NIF function.

I think the thing to be very aware of is that all data, ALL data, in Erlang/Elixir is immutable. This is not just a language feature but implemented/enforced all the way down in the BEAM. This means that when mutating a structure and rebuilding “on the way up” you never have to make copies of the unchanged parts of the structure only the actual path down to the new parts. No one else can change them so you are always safe. So yes when appending a new element to the end of a list you need to rebuild the list cells but there is no need to copy the actual elements in the list.

This means that there is actually no copy instruction/call in the machine. Well, there is one for binaries but that exists for one special purpose.

Writing NIFs for accessing parts of deep structures would be fine but I am not certain that they would be very much faster than writing code instead.

I’m not sure I get what you’re suggesting, but newer data can’t point to older data in Erlang, it would break the GC. So you can’t have a child node keep a reference to a parent.

It’s interesting… The more I think about all the cases where people highlight the benefits of mutability, the more I realize that those cases almost always involve a traversal, in which case an immutable approach is just as performant.

And if one wants to do multiple things to that piece of data, one can just add an optional list of operator functions to pass in and call, passing in that piece to each, e.g. with tail recursion.

At this point, I think my initial concern has been resolved. Mutable implementations are usually just as time-efficient as immutable ones, and the Erlang VM allows them to be just about as space-efficient in most cases.

With the benefits immutability has for concurrent programming, I think in time immutable implementations will replace mutable equivalents.

Another misconception debunked. Thanks!