5 ms·

On-topic: How common is the usage of linked lists in real world Lisp projects? Isn't the prevalence of this data structure in books encourage writing inherently

by zerr 6y ago

On-topic: How common is the usage of linked lists in real world Lisp projects? Isn't the prevalence of this data structure in books encourage writing inherently inefficient programs?

mikelevins 6y ago
Depends on what you mean. In one sense, it's the most common thing in the world, because Common Lisp source code is made of linked lists, so every Lisp program makes extensive use of them. But that doesn't have any necessary relationship to the efficiency of running programs, because the compiled code doesn't have to traverse linked lists just because that's what the source code is made of. In another sense, it's still pretty common because linked lists are a standard feature of the language with extremely convenient surface-level support, and because linked lists are sufficiently flexible to represent arbitrary data structures (albeit not necessarily efficiently). Those characteristics make it really convenient to use lists for modeling data while you're figuring out how you want things to work, and I personally do that all the time. Again, that doesn't have any necessary relationship to efficiency in your completed program. I commonly use lists to knock together speculative data models and figure out access patterns. That doesn't mean I'll stick with them once I figure out the needed access pattern. It depends on the access pattern. If it happens to be the case that linked lists are close to optimal for the access pattern I discover, then I'll stick with them. Why wouldn't I? If not, I'll use another data structure. Lisp makes it easy to design APIs that are agnostic about the data structures they operate on, which makes it easy to swap out one structure for another once you figure out which is the right one.
bjoli 6y ago
Whenever you need random access you use something else. If all you need is sequential access, there are lots of optimizations that can be done to the representation of lists that make them more efficient. In guile scheme you gain very little by using vectors instead of lists unless you want random access. There is however a never-ending flood of people coming from python using lists in exciting ways to create accidentally O(n^3) programs :) Those can almost always be re-written to be o(n) using linked lists, otherwise you point them to vectors instead.
- zerr 6y ago
  Besides random access, I mean the data locality, cache-friendliness in general.
  - bjoli 6y ago
    That is usually done as a part of the GC. With a generational ormcopying GC you can "defragment" memory so you have the list in a contiguous region. Not as good as a vector of course, but still decent.

by zerr 6y ago

On-topic: How common is the usage of linked lists in real world Lisp projects? Isn't the prevalence of this data structure in books encourage writing inherently inefficient programs?

mikelevins 6y ago

Depends on what you mean. In one sense, it's the most common thing in the world, because Common Lisp source code is made of linked lists, so every Lisp program makes extensive use of them. But that doesn't have any necessary relationship to the efficiency of running programs, because the compiled code doesn't have to traverse linked lists just because that's what the source code is made of. In another sense, it's still pretty common because linked lists are a standard feature of the language with extremely convenient surface-level support, and because linked lists are sufficiently flexible to represent arbitrary data structures (albeit not necessarily efficiently). Those characteristics make it really convenient to use lists for modeling data while you're figuring out how you want things to work, and I personally do that all the time. Again, that doesn't have any necessary relationship to efficiency in your completed program. I commonly use lists to knock together speculative data models and figure out access patterns. That doesn't mean I'll stick with them once I figure out the needed access pattern. It depends on the access pattern. If it happens to be the case that linked lists are close to optimal for the access pattern I discover, then I'll stick with them. Why wouldn't I? If not, I'll use another data structure. Lisp makes it easy to design APIs that are agnostic about the data structures they operate on, which makes it easy to swap out one structure for another once you figure out which is the right one.

bjoli 6y ago

Whenever you need random access you use something else. If all you need is sequential access, there are lots of optimizations that can be done to the representation of lists that make them more efficient. In guile scheme you gain very little by using vectors instead of lists unless you want random access. There is however a never-ending flood of people coming from python using lists in exciting ways to create accidentally O(n^3) programs :) Those can almost always be re-written to be o(n) using linked lists, otherwise you point them to vectors instead.

zerr 6y ago
Besides random access, I mean the data locality, cache-friendliness in general.
- bjoli 6y ago
  That is usually done as a part of the GC. With a generational ormcopying GC you can "defragment" memory so you have the list in a contiguous region. Not as good as a vector of course, but still decent.