Singly linked lists let you do fast immutable list copies on entry into a new function context.
In python, for example let's say:
def f:
arr = [0, 1, 2]
g(arr)
return arr[0]
What does f return? You don't know. It depends on g. If g has other dependencies, and someone changes a deep dependency (or maybe a library changes an implementation) you could completely fuck up the result of f, spooky action at a distance, and all of your code could be hosed.
Languages that default to using linked lists do not have this problem.
There are better alternatives to linked lists for this use case.
1. Clojure uses wide balanced trees as its general-purpose ordered collection.[0] These have probably already been adapted for Haskell, and they offer persistence and fast random access and some degree of cache-friendliness. In my opinion it makes better trade-offs as a general-purpose structure.
2. By passing an &[usize] in Rust, or a const size_t* in C (i.e. by making g accept a read-only pointer), you can be guaranteed that g doesn't modify the array.
>>> x = ([1,2,3,4],"whatever")
>>> x[0].append('z')
>>> x
([1, 2, 3, 4, 'z'], 'whatever')
And python gives you access to anything:
>>> def gotcha():
... z = globals()['x']
... z = list(z)
... z.append("I've seen'em do it man!")
... globals()['x'] = tuple(z)
...
>>> x = (1,2,3,4)
>>> gotcha()
>>> x
(1, 2, 3, 4, "I've seen'em do it man!")
It be shallow with a Singly Linked List too no? What inherently makes a Singly Linked List better at addressing this problem if it contains mutable elements?
Typically, in a functional language, values are immutable.
So if you cons to a list, you create a new value that has the current list as its tail. Since all lists are immutable, they can be shared and there's no need for a deep copy.
Python is not a functional programming language....
sure but IIRC the performance characteristics of manipulating python tuples ultimately way worse if you need to change the contents of the list, by say, prepending, or trimming, or whatever. This is no fun in python:
"Copying" an immutable singly-linked list is just copying the reference to the first element. That is, the entire list is really shared, not actually copied element by element like an array would have to be. But since it is immutable, this doesn't matter: You cannot change it in a way that would mess up other users' view of the list.
What you can still do is cons new elements to the front of your copy. No other copy of the list will be affected. Because the list is singly linked, other owners of references into the list cannot walk back to observe your elements. They can even cons their new elements to the "same" list without any conflict.
All this is very useful if you want to process something with a stack, such that sub-operations can push elements to the stack that they have to remove again before returning. Pushing x and y to the stack is just constructing the list y : x : stack. Popping y and x from the stack when you're done is a no-op: "stack" is still a reference to the stack as it was before these operations.
In python, for example let's say:
What does f return? You don't know. It depends on g. If g has other dependencies, and someone changes a deep dependency (or maybe a library changes an implementation) you could completely fuck up the result of f, spooky action at a distance, and all of your code could be hosed.Languages that default to using linked lists do not have this problem.