4 ms·

Nobody has mentioned immutability yet - linked lists are easily used as one of the simplest immutable persistent data structures. Your definition of "better" ap

Nobody has mentioned immutability yet - linked lists are easily used as one of the simplest immutable persistent data structures. Your definition of "better" appears to be solely about keeping the CPU burning, but if CPU isn't the bottleneck, I prefer "immutable linked list" over "clone a vector many times" merely on aesthetic and reason-ability grounds.

gleenn 4y ago
Or you could go the Clojure route and do the tree-style immutable vectors where the cost is log32(N) for most operations, small enough in all the relevant operations, and you get the amazing usability of immutable data structures that are performant enough in most cases.
- kazinator 4y ago
  How does that scale down to small sequences of under ten items?
  - Jim_Heckler 4y ago
    an array is used for the last 1-32 elements of the vector (the "tail") so there would be no trie at all, just the tail
mst 4y ago
cons cells are a local maximum. often they're sufficiently maximal.
yongjik 4y ago
Well, of course if a solution is "cloning a vector many times" then arguably you're using the vectors wrong - in which case it's totally appropriate to find a different data structure (or a better way to use vectors, if possible).
dan-robertson 4y ago
In C where using the simplest data structures is valuable, you’d likely do much better by upgrading your programming language to something that offers a better data structure. If you’re using a higher level language where you can abstract details about your sequence data structure, I think there’s very little benefit to using the simplest data structure and you should instead have widely used libraries that offer a good immutable sequence type, e.g. RRB trees. One exception is ML style languages where singly linked lists get a big syntax advantage (Haskell only half counts because most of its lists are really just iterators). I think this was, in hindsight, a mistake for a widely used language. It’s also a source of pointless pain for learners (eg I don’t think there’s much benefit to people having to write lots of silly tail-recursive functions or learning that you have to build your list backwards and then reverse it). Another exception would be some lisps where lists are everywhere and the cons-cell nature of them makes it hard to change.

gleenn 4y ago

Or you could go the Clojure route and do the tree-style immutable vectors where the cost is log32(N) for most operations, small enough in all the relevant operations, and you get the amazing usability of immutable data structures that are performant enough in most cases.

kazinator 4y ago
How does that scale down to small sequences of under ten items?
- Jim_Heckler 4y ago
  an array is used for the last 1-32 elements of the vector (the "tail") so there would be no trie at all, just the tail

mst 4y ago

cons cells are a local maximum. often they're sufficiently maximal.

yongjik 4y ago

Well, of course if a solution is "cloning a vector many times" then arguably you're using the vectors wrong - in which case it's totally appropriate to find a different data structure (or a better way to use vectors, if possible).

dan-robertson 4y ago

In C where using the simplest data structures is valuable, you’d likely do much better by upgrading your programming language to something that offers a better data structure. If you’re using a higher level language where you can abstract details about your sequence data structure, I think there’s very little benefit to using the simplest data structure and you should instead have widely used libraries that offer a good immutable sequence type, e.g. RRB trees. One exception is ML style languages where singly linked lists get a big syntax advantage (Haskell only half counts because most of its lists are really just iterators). I think this was, in hindsight, a mistake for a widely used language. It’s also a source of pointless pain for learners (eg I don’t think there’s much benefit to people having to write lots of silly tail-recursive functions or learning that you have to build your list backwards and then reverse it). Another exception would be some lisps where lists are everywhere and the cons-cell nature of them makes it hard to change.