this post was submitted on 12 Nov 2023
1 points (100.0% liked)
Lisp
52 readers
3 users here now
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
I think it's because it's more natural to represent a tree with a linked list. The body of Lisp code is also a tree - some even say an "abstract syntax tree", but that's not fully accurate - which facilitates the syntax manipulation done with macros.
Not just trees; any operation that involves mutating or manipulating list-like structures is more efficient than arrays.
Some examples:
Removing an element is delinking a single cons cell, vs either copying to a new array or shuffling all subsequent elements left. It also doesn't break any references to list cells, even the removed cell.
Slicing, at minimum, only requires having the cons cell at the new head of the list; rather than either a special datastructure to represent a slice, or copying to a new array.
Filtering means pulling cons cells from a nursery on an ad-hoc basis, using them to collect filtered elements into a new list of unknown length. With an array, you need a pre-allocated buffer that either sets a limit on the size of the filtered set, or requires reallocation on resize with a O(n) copy.
Just, in general, you can be a lot more relaxed with flinging data around lists without having to think about the algorithmic overhead of allocating, reallocating, copying and shuffling arrays.