3 ms·
Phil Bagwell's VList data structure seems really interesting as a way to avoid a bunch of the pitfalls of naive lists performance-wise - the paper's good fun an
by mst 5y ago
Phil Bagwell's VList data structure seems really interesting as a way to avoid a bunch of the pitfalls of naive lists performance-wise - the paper's good fun and there seems to be an implementation in racket for anybody who wants to play with it.
- spicybright 5y agoDoes any one have a copy of anything related to this? Wikipedia had an article on it deleted, and I'm not getting much from the first few pages of google...
- mst 5y agoRacket implementation: https://docs.racket-lang.org/functional-data-structures/VList.html https://docs.racket-lang.org/functional-data-structures/VLis... There's a copy I made of the original paper here: http://trout.me.uk/lisp/ http://trout.me.uk/lisp/
- celeritascelery 5y agoThe problem with a vlist is that it doesn’t maintain lisp list semantics. You can’t implement setcdr on a vlist. But you can with something like cdr-coding.
- mst 5y agoThe paper discusses how to handle appends and similar. Assuming the majority of your lists are read-only apart from appends, you can end up with something pretty performant overall. Trade-offs all the way down as ever though.