Most other languages don't use singly linked lists to begin with.
Because they suck.
Because they suck.
Don't blame the language, & learn to use the right data structure for the job.
Not trying to throw any of the other languages mentioned under the bus, I do not know them well enough to know what list structure they default too or more idiomatically rely on.
That said, the ready availability of linked lists in Haskell does mean that you end up with rather more strictly-manifested linked lists than you might like, since any of them can be manifested as actual linked lists. If you're using Haskell though, while you haven't exactly completely given up on that sort of performance, it must not be foremost on your mind.
Yes, exactly. A lazy list is just another term for generator. If you hold on to a reference to the head of such a list as you run the generator, then you'll consume a lot of memory and will end up with a strict list, and also you'll be sad. But if you don't hold on to that reference, then it will be very efficient.
> That said, the ready availability of linked lists in Haskell does mean that you end up with rather more strictly-manifested linked lists than you might like, since any of them can be manifested as actual linked lists. If you're using Haskell though, while you haven't exactly completely given up on that sort of performance, it must not be foremost on your mind.
Especially strings as lists of characters. That was a mistake. Well, in some sense, character data has to be a list, since with Unicode you really can't efficiently index a string... unless it's a rope and you apply the sorts of tools that xi does (e.g., keeping track of character counts per rope segment, etc.). But strings should be sufficiently opaque that arrays, lists, and ropes are all equally able to implement their semantics.
It is also worth noting that haskell has library specified fusion rules so the closure isn't even allocated most of the time. So
sum (take 10 [0..])
Technically, if you want to really understand how the "IO monad" does its thing, this is actually how it works. Technically your program declares a probably-infinite data structure that contains all possible paths your code could take, e.g., if you have a "if user input is negative then do X else do Y", what you really have is a data structure representing the if-then clause. What keeps the infinite data structure from being manifested in RAM is that the whole thing is resolved lazily, so only one branch will be actually evaluated. That's why the "IO monad" is actually pure; it simply "purely" creates a huge data structure that is resolved by an interpreter later. In the theoriest of theories, an IO value in Haskell really doesn't execute anything either and the whole language is pure... it is only the interpretation of the IO value that finally interfaces with the real world.
It isn't always the most helpful perspective and you can become an expert Haskell programmer without ever looking at your program this way, but technically, under the theory hood, that's what's happening.
The majority of langauges web frameworks are written in do not have linked lists, at all.
Python doesn't. Ruby doesn't. Java doesn't.
Wrong. Intrusive, doubly-linked lists are extremely performant and useful in the right places, especially if you have callbacks which store a pointer to a list element (this often happens with device drivers in low level programming), or if the elements can belong to several lists.
The Linux kernel, for example, makes plenty use of linked lists.
> IMO, like goto’s it’s better to just forget they exist.
Wrong again. In a language without automatic memory management and without scoped destruction (cough C cough), they are immensely useful. Again, refer to the Linux kernel. Or any competently written, non-trivial C program for that matter. Note: I'm not defending C here, I'm defending correctly used gotos in C programs.
IDK if this is the case for device drivers, but AFAICT device drivers tend to preallocate memory on loading and manage it locally.
Look, I'm not saying that linked lists can replace arrays. In fact, I almost always use arrays instead of linked lists. What I'm arguing against is the notion that arrays always trump linked lists, which is false, and repeating that meme shows a lack of deeper understanding.
If you have a degenerate case and are never traversing nodes, you’re still likely better of with a rung buffer, array list, 2 different stacks, or various other options. And frankly you’re never going to endlessly just insert data without reading it.
Re-read my original post: "[...] especially if you have callbacks which store a pointer to a list element [...]"
This happens all the time in kernel code or bare-metal programming.
What else can I say? Open the Linux source code [1] and see for yourself.
PS: If you don’t feel like pointing to a concrete example, I am going to counter with 99% of the stuff you can find here: www.google.com.
> The way modern memory works linked lists are practically a denial of service attack on system performance.
and
> IMO, like goto’s it’s better to just forget they exist.
That's as close to "never use a linked list" as you can get without saying that literal sentence.
So do arrays, FYI.
> It's really better to aim for non-circularity and to avoid the need for locks.
How does an array avoid the need for a lock where a linked list needs one?
Now sure, if it’s small and you’re only creating then reading it once then that’s fine. But, you’re assumptions need to be accurate or you just created a problem.
But, yeah, if you’re relying heavily on random access, pick a vector/array or some kind of tree/hash table.
They're quite useful in functional languages.
In Haskell in particular they can have nice performance effects if you use them sensibly.
That's for streaming I/O. Lazy linked lists are appropriate for streaming without side effects
In python, for example let's say:
def f:
arr = [0, 1, 2]
g(arr)
return arr[0]
Languages that default to using linked lists do not have this problem.
there are immutable non-linked list datastructures (the most obvious one in python are tuples)
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)
>>> 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....
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.
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...