Why is that? They're perfectly fine for most purposes, and have the advantage that when you pass one across a function boundary the callee can play with it or modify it or do whatever the hell they want and when the callee returns, the caller's linked list is untouched. That's an incredibly valuable feature for correctness and safety.
They have poor cache performance when you want to iterate over them, and more size overhead, because there's one pointer lookup per item. Also, the common definition of a linked list has the list responsible for allocating each item, meaning it can't be a member of more than one list at once. The actual useful version of this is called instrusive linked lists, which isn't the one taught.
> That's an incredibly valuable feature for correctness and safety.
Are you thinking of something else? That's an effect of call by value, but linked lists actually aren't good at that and you have to copy them to pass them around. You need something like these to make it efficient:
> Are you thinking of something else? That's an effect of call by value, but linked lists actually aren't good at that and you have to copy them to pass them around.
Are you thinking of something else? Haskell (and all other ML-family languages, and Lisps) lists are passed around by copying a single pointer to the head element. Different lists can share tail elements, i.e., elements can be members of more than one list.
All this is in contrast to Java-style linked lists, where there is a list object that controls its elements.
I think the point is to contrast them with dynamic arrays --- linked lists, unlike arrays, are persistent data structures, which does make them easier to reason about.
> Also, the common definition of a linked list has the list responsible for allocating each item
I'm not sure how this is relevant in the context of Haskell, given that it's garbage collected.
Why is that? They're perfectly fine for most purposes, and have the advantage that when you pass one across a function boundary the callee can play with it or modify it or do whatever the hell they want and when the callee returns, the caller's linked list is untouched. That's an incredibly valuable feature for correctness and safety.