4 ms·

What's the advantage of not having lists? How does this affect one's programming style versus Scheme or Common Lisp (or Emacs Lisp, honestly the Lisp I'm most f

What's the advantage of not having lists? How does this affect one's programming style versus Scheme or Common Lisp (or Emacs Lisp, honestly the Lisp I'm most familiar with)?

tombert 5y ago
Disclaimer: I've never used Janet, but I am pretty familiar with Clojure. In Clojure, there are lists, but the most common structure for sequential data is actually a vector [1], which works more-or-less as a slightly modified version of the Clojure version of a hashmap. Advantages of doing it this way is that you get log32 indexed lookup times (vs linear for lists), and you also get log32 [2] append-to-the-end semantics instead of "push to the beginning" that you have with lists. In practice it generally doesn't affect a lot, but occasionally when I do need to put an item in the front of a collection, I will wish I had used a list instead of a vector, but I feel like the far more-common usecase is to append to the end, since in Erlang there's been a few times where I end up having to reverse the list after I'm done building it. [1] At least how I use it, I haven't done any statistics to prove this. [2] Don't let the log scare you! Log32 is very good and also effectively constant time for most in-practice use cases. Log32 of a billion is basically six, meaning you're dealing with a constant factor times six hops for inserts and lookups on a billion elements.
- 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 ago
    Does 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 ago
      Racket 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 ago
    The 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 ago
      The 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.
saikyun 5y ago
You can access any element in your array in O(1). I think it is faster to loop through as well, but I'm not so sure about that. The drawback is that appending / removing elements at the beginning of the array is O(n). When it comes to interacting with the collections I mostly use the loop / seq macros, which I believe are pretty similar to Common Lisp. Ofc you also have map / filter / reduce.

What's the advantage of not having lists? How does this affect one's programming style versus Scheme or Common Lisp (or Emacs Lisp, honestly the Lisp I'm most familiar with)?

tombert 5y ago

Disclaimer: I've never used Janet, but I am pretty familiar with Clojure. In Clojure, there are lists, but the most common structure for sequential data is actually a vector [1], which works more-or-less as a slightly modified version of the Clojure version of a hashmap. Advantages of doing it this way is that you get log32 indexed lookup times (vs linear for lists), and you also get log32 [2] append-to-the-end semantics instead of "push to the beginning" that you have with lists. In practice it generally doesn't affect a lot, but occasionally when I do need to put an item in the front of a collection, I will wish I had used a list instead of a vector, but I feel like the far more-common usecase is to append to the end, since in Erlang there's been a few times where I end up having to reverse the list after I'm done building it. [1] At least how I use it, I haven't done any statistics to prove this. [2] Don't let the log scare you! Log32 is very good and also effectively constant time for most in-practice use cases. Log32 of a billion is basically six, meaning you're dealing with a constant factor times six hops for inserts and lookups on a billion elements.

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 ago
  Does 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 ago
    Racket 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 ago
  The 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 ago
    The 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.

saikyun 5y ago

You can access any element in your array in O(1). I think it is faster to loop through as well, but I'm not so sure about that. The drawback is that appending / removing elements at the beginning of the array is O(n). When it comes to interacting with the collections I mostly use the loop / seq macros, which I believe are pretty similar to Common Lisp. Ofc you also have map / filter / reduce.