List append

Consider appending a node to a list. In the mutation world, we traverse the list until we reach the end and then change the last node to point to the new node. This is costly when the list is long and has a complexity of O(n).

For a persistent list (immutable and structurally shared) appending a new value, we need to traverse until the end of the list, copying all the elements on the way.

However, as noted, appending to a list is anyway a slow operation. When we need to append values, we need to ask ourselves whether lists are the right fit for the problem.

Whenever we want to grow a list by appending to the end, we should instead use a vector. When we are done with all of the appending, we could convert the vector into a list, if needed.

We can look at the original list at V0. This list has three nodes, holding the values 12, 99, and 37.

When we append the value 17, the original three nodes are copied, and then at construction time, the node with the value 17 is added. The data...