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.
