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.
[0]: https://hypirion.com/musings/understanding-persistent-vector...
there are immutable non-linked list datastructures (the most obvious one in python are tuples)
>>> x = ([1,2,3,4],"whatever")
>>> x[0].append('z')
>>> x
([1, 2, 3, 4, 'z'], 'whatever')
>>> 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!")Python is not a functional programming language....
def f(some_tuple):
part_one = take_the_last_three_parts_of_the_tuple(some_tuple)
part_two = append_to_self(part_one)
part_three = tail(part_two)
You saying before the call to "g", you would make a deep copy of "arr" and that's faster to do with a singly linked list? Could you explain why?
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.
I'd still have to say that Singly Linked List arn't ideal for that either, better use a persistent hash array mapped trie backed list instead.
there's a real memory overhead for that structure.
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.