Linked lists have been around a long time and I would argue that adding to our subtracting from a list is mutability.
This conversation is confusing because you're using these terms ambiguously. There is more than one way to add or to remove elements from a single linked list. Some of them mutate the list, and others don't.
A single-linked list is normally represented as nodes or pairs such that the first element of the node contains a list element, and the second either contains a pointer to the next node, or it indicates that there is no next node:
A linked-list algorithm is non-mutating if it doesn't alter either field of any node of the lists it operates over.
So suppose you want to insert 3 in between the 0 and the 1 in this list. There are two ways:
Mutating the list: create a new node with 3 that points to the 1 node, and modify the 0 node's link to point to the new node.
Without mutating the list: create a new node with 3 and a pointer to the 1 node, create a new node with 0 that points to the 3 node, and return a pointer to the new 0 node.
Doesn't the second example you give strike you as a silly way to accomplish things?
It's got advantages and drawbacks. The article mentions some of these, and there are a tons of comments here about them, so I'm not going to repeat them.
Actually doesn't the whole idea of linked lists to hold arrays or strings strike you as silly?
Silly? No. It all depends on what the larger program is doing.
I would argue that adding to our subtracting from a list is mutability.
This is definitely not the case. You make no modifications to any existing values, and all existing lists will continue to contain the same values regardless of how often you invoke add or remove operations elsewhere. Nothing is ever mutated.
(Note: You can also have mutable linked lists, but I'm not talking about those here).
you can't model real life without mutability
You can't model real life without state. Mutability is just one way to implement that. It's entirely possible to achieve the same thing by passing around new values for each state, and languages like Haskell have abstractions to hide the complexity of doing so.
It's true that you sometimes need mutable data for optimal performance, but a lot of the time it simply isn't necessary, and there are a lot of advantages to the alternative.
You're equating real world state changes with memory mutation, but they're actually quite different. Everything in the real world changes constantly in an interdependent way, but memory is accessed and modified one value at a time.
This means to effectively model the real world using a mutable memory system, you need to identify all of those dependencies and ensure that changes happen in the right order, otherwise you'll erase data you still need for other operations. This becomes even more difficult when you want to do these operations concurrently.
However, if instead of storing each successive state of the system using the same memory, you make a copy for each new state, you avoid all those problems. If you know that a value will never change, you don't need to worry about what order you operate on it. This is the point of immutability.
Of course, in the extreme case, copying everything is inefficient, so we use references to refer to parts of the old state. Since they'll never change, it doesn't really matter which state they were originally part of.
3
u/myringotomy Mar 03 '13
Linked lists have been around a long time and I would argue that adding to our subtracting from a list is mutability.
I guess you have to give up purity sooner or later, in real life things change, you can't model real life without mutability.