3 ms·

Why would one want to use this over the VList? It provides O(1) access on average and O(log n) access in the worst case. Plus, it also does O(log n) length fi

• daniel-cussen 16y ago
  I looked at those before posting. Basically, the difference is that every trellis of a given length looks the same, whereas this is not the case for VLists. The trellis is also lispier. VLists are faster in a lot of cases, but they sound like they're harder for the programmer. They are also possible to implement in every Lisp (except Clojure [1]) because you only need cons, car, cdr, and some basic arithmetic to use them. This also means you can make them do anything (except, like, push and pop in constant time) that you would ordinarily need a linked list for. I haven't done this yet, but I think they support homoiconicity. [1] In clojure, cons takes an object and a sequence instead of an object and an object, making an implementation there a lot less elegant. EDIT: I thought this over, and, suppose you need to store huge, huge amounts of data. Where's that first array going to be stored on the memory? It needs to be contiguous. Here, you only need two memory addresses at a time for the cons cells. EDIT2: you have to declare a type for your array. With trellises don't. Even if you declare your array as an array of pointers, nesting is an issue.
• munificent 16y ago
  From skimming wikipedia and the code, it looks like a trellis is more or less a VList where each array in the VList is represented by a complete binary tree of an appropriate depth. That gives you the VList's O(1) average performance to find the right tree, but then you have to do an O(log n) walk down the tree to the desired element. Am I interpreting that right?
  • daniel-cussen 16y ago
    Pretty much. Finding the right tree takes O(logn) as long as walking down that tree.