racket
Make doubly-linked lists the canonical data structure
Are there downsides to making lists doubly-linked by default? If rhombus is stepping away from scheme, maybe this would be a good time to make some more fundamental changes and break from how lisps normally operate.
In my mind, some of the benefits of doubly-linked lists are:
- Aesthetics. It is more symmetrical to allow (first xs) and (last xs), (rest xs) and (but-last xs), foldl and foldr, and (reverse xs) have the same performance. Reading items in reverse or putting a value at the end for no extra cost would make some algorithms and use-cases more elegant.
- Better support for adding and removing elements from a list.
Den man. 16. nov. 2020 kl. 22.10 skrev erichaney [email protected]:
Are there downsides to making lists doubly-linked by default?
Currently each cons cell consists of a next pointer and an element/element pointer. For a doubly linked cons cell (a dcons) you also need a back pointer. The memory needed to store the list thus increases by 50%. And that in turn means they will be slower.
If rhombus is stepping away from scheme, maybe this would be a good time to make some more fundamental changes and break from how lisps normally operate.
In my mind, some of the benefits of doubly-linked lists are:
Aesthetics. It is more symmetrical to allow (first xs) and (last xs), (rest xs) and (but-first xs), foldl and foldr, and (reverse xs) have the same performance. Reading items in reverse or putting a value at the end for no extra cost would make some algorithms and use-cases more elegant.
A list
A wider selection of easy to use builtin data structures would certainly be a good thing. I am not sure a double-linked list is the best alternative though - and I am not sure I want to give up the good old cons-based lists either :-)
Anyways, for those with a need to use doubly linked lists in Racket or just want to experiment, take a look at:
https://github.com/soegaard/remacs/blob/master/dlist.rkt
It contains an implementation with iterators as well as a for comprehension.
/Jens Axel
Well the obvious downside is memory use, sure theoretically xor-linked-lists https://en.wikipedia.org/wiki/XOR_linked_list can have similar memory use to single linked lists but they then need more code for iteration. I think double linked lists can be great but I would always like to have the choice between single and double, or another data structure altogether.
A whole other thing is immutable vs mutable, rackets cons/list is immutable, which is good because you know that certain lists never change, allowing things like length optimization that cache the length of the list.
Also adding to the front is very easy with immutable lists you just add a new cell before the rest of the list which is shared between the two lists. When you have double linked lists you would have to copy the whole list because you have pointer chains through out the list in both directions, only way around that would be to use mutable lists, but then you have to let the user handle mutable semantics, or you have to track the "owners" of the list and copy the list if there is more than one before you modify it.
That said, I think it would be great if there wasn't a data-structure that seems like the default and instead the core library would work with many data-structures, through making constructs that iterate more generic by using things like transducers, even better would be if the type inference of a typed variant would use non-generic faster implementations automatically. Using in-list, in-vector etc. in for loops is fine for me in racket, but it is not a great selling point if the language could know to do that itself from the context. (disclaimer: I don't know how much and when typed racket already does this, but a new iteration of the language should definitively be good at it)
Really what we want to do in Rhombus is provide good collection interfaces instead of changing default implementations.
There are a lot of data structures that could be considered in place of simple linked lists. Finger trees a nice range of operations. I'm only just now finding out about VLists, but they seem interesting.
Doubly linked lists are a surprising choice.... Wouldn't you need to traverse and rebuild the whole list just to compute the tail of the list? But the general idea of rethinking common data structures seems valuable.
