Trellis
Languages and libraries
lisp data structure
SHOW HN2010
How HN took it
0 positive, 16 neutral or asking, 0 mixed, 6 critical, out of 22 comments about the project. Thread score -0.17.
Idea: 0 for, 3 againstPerformance: 0 for, 2 against
The thread, comment by comment
Each row is a top-level comment and its replies, in HN's order. Select a cell to open that comment on HN.
positive neutral or mixed critical about another commenter or something else the maker
What HN said
What people liked
Interesting idea and clever structure.
From 1 comment
Finger trees are even more impressive than this (very clever) data structure. A sequence based on finger trees supports: * O(lg n) lookup, split, concatenate, random…
pjscott on HN
Objections
Cons and car/cdr are O(log n) rather than O(1), so it is not a general list replacement.
From 2 comments
The two most common operations on lists in typical functional programs are consing and deconsing, which are O(1). The most analogous operations on trellises are appending and…
rntz on HN> How do these differ and what advantage do they offer over Chris Okasaki's Random Access Lists? These are inferior, as Okasaki's structure offers O(1) worst-case cons, even when…
jbapple on HN
Existing structures like Okasaki's random access lists and finger trees do the same job better.
From 3 comments
How do these differ and what advantage do they offer over Chris Okasaki's Random Access Lists? http://www.eecs.usma.edu/webs/people/okasaki/fpca95.ps Scheme SRFI with…
somnium on HNThis "list of trees of increasing size" data structure is not new. You can find plenty of these structures in Okasaki's Purely Functional Data Structures (look in the chapter…
jules on HNI've never been very good at data structures, but the increasing size of trees makes it sound like finger trees: http://en.wikipedia.org/wiki/Finger_tree
gwern on HN
Storing NIL at the end of a trellis is broken.
From 2 comments
The two most common operations on lists in typical functional programs are consing and deconsing, which are O(1). The most analogous operations on trellises are appending and…
rntz on HNThat's just broken, and will lead to horrible bugs. There is a reason why normal Lisp lists end with NIL instead of storing the last element in the last cdr.
jules on HN
Claims about the structure's advantages were not well supported.
From 1 comment
> I get the feeling these can do things Random Access Lists can't It seems like you came to this topic without knowing a lot about purely functional data structures already. It's…
jbapple on HN
Requests
Explain how it differs from existing random access list and VList designs.
From 2 comments
How do these differ and what advantage do they offer over Chris Okasaki's Random Access Lists? http://www.eecs.usma.edu/webs/people/okasaki/fpca95.ps Scheme SRFI with…
somnium on HNWhy 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 finding.…
j_baker on HN
Questions
How does it compare to balanced binary trees with subtree sizes?
From 1 comment
How are these better than balanced binary trees that keep subtree size in the node?
jemfinch on HN
Could it be used in Clojure, and how does it compare to vectors?
From 1 comment
Very intressting. Could the be used in clojure (I mean do the provid the same imutabillity concells do) What are the benefits of these over clojure vectors?
nickik on HN
Alternatives named
Okasaki's random access lists
From 1 comment
How do these differ and what advantage do they offer over Chris Okasaki's Random Access Lists? http://www.eecs.usma.edu/webs/people/okasaki/fpca95.ps Scheme SRFI with…
somnium on HN
Finger trees
From 1 comment
I've never been very good at data structures, but the increasing size of trees makes it sound like finger trees: http://en.wikipedia.org/wiki/Finger_tree
gwern on HN
VLists
From 1 comment
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 finding.…
j_baker on HN
Clojure finger-tree library
From 1 comment
As I understand it, the finger trees library for clojure would give you more flexibility and better performance. https://github.com/clojure/data.finger-tree
tensor on HN