5 ms·

Show HN: New Lisp data structure

62 points by daniel-cussen 16y ago

daniel-cussen 16y ago
I know this is a big claim, but there are mathematical reasons to support why it works. And it works, at least on my computer.
- daniel-cussen 16y ago
  Also, I'd like to talk about what it does for those that don't feel like reading the GitHub. It's almost exactly like linked lists, except for two things: one, it is less flexible, and two, it is much faster. Most of its functions work in logarithmic time whereas those of linked lists work in linear time. Other than that, it's made of the same things (cons cells), it is navigated the same way (cars and cdrs) it is sequential, so it has clearly delimited first, second, and third elements, and it nests.
- jbapple 16y ago
  > I know this is a big claim Perhaps, but it needn't be to get the same asymptotic performance. Okasaki's simplest random access list has performance proofs that depend only on the simplest properties of binary numbers, rather than those of the Exponential-Golumb coding, and the code is very easy to write: data BRAL a = Empty | Full (Maybe a) (BRAL (a,a)) deriving (Show) cons :: a -> BRAL a -> BRAL a cons x Empty = Full (Just x) Empty cons x (Full Nothing ys) = Full (Just x) ys cons x (Full (Just y) ys) = Full Nothing (cons (x,y) ys) nth :: Integer -> BRAL a -> a nth 0 (Full (Just x) _) = x nth 0 (Full Nothing xs) = fst (nth 0 xs) nth n (Full (Just _) xs) = nth (n-1) (Full Nothing xs) nth n (Full Nothing xs) = let pair = nth (n`div`2) xs in if n`mod`2 == 0 then fst pair else snd pair
j_baker 16y ago
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. http://en.wikipedia.org/wiki/VList http://en.wikipedia.org/wiki/VList
- 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.
nickik 16y ago
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?
- daniel-cussen 16y ago
  You know, I tried clojure out, but the cons cells are implemented in a weird way; they can't combine two objects, only an object and a sequence. So I could probably do something like trellises, but they wouldn't be as elegant.
  - cgrand-net 16y ago
    I think one can use [a b] and destructuring instead of cons/car/cdr and be as elegant.
- tensor 16y ago
  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 https://github.com/clojure/data.finger-tree
aidenn0 16y ago
What is the insertion time on this? It seems like it would be O(n) to insert at the head, at which point why don't you just use a vector? [edit]It is always log(n) to insert at end, which is better than vector in the worst-case
- daniel-cussen 16y ago
  Insertion into the middle is O(n) because you have to rearrange everything after that. Adding something to the end (#'add) is O(logn). Inserting at the head is indeed slow (unless you are willing to break the structure) but there are many reasons not to use a vector; insertion time isn't everything. With vectors, you have to make sure your vector has empty space left or is a dynamic array. Here, you don't have to worry about anything (short of blowing the stack).
gwern 16y ago
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 http://en.wikipedia.org/wiki/Finger_tree
- daniel-cussen 16y ago
  Thanks for the link. While they both use trees they're not the same thing.
- pjscott 16y ago
  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 insert/delete * amortized O(1) push and pop at either end of the sequence * Caching the value of a monoid reduction of each subsequence. Surprisingly useful. Trellises are easier to understand, though.
jemfinch 16y ago
How are these better than balanced binary trees that keep subtree size in the node?
- daniel-cussen 16y ago
  Predictable structure and smaller nodes. And most of the other advantages linked lists have over binary trees, with some of those advantages being slower.
  - jemfinch 16y ago
    If I'm using both as a abstract data types, does predictable structure really help me at all?
    - daniel-cussen 16y ago
      If you're using it for code (the way Lisp uses linked lists) you know when one function ends and a nested one begins. I'd like to point out, however, that this is in theory, as I haven't seen this data structure doing anything other than moving data around.
- jbapple 16y ago
  > How are these better than balanced binary trees that keep subtree size in the node? I suspect that cons will be )(1) amortized (when the trellis is used ephemerally), which is not true of your usual balanced binary trees. There are many data structures that offer O(1) (amortized or worst-case) modification near the front, and several of them really are just balanced trees but with the pointers down the left spine reversed. In fact, this is a key idea behind Hinze & Patterson's FingerTress, mentioned elsewhere in this thread.
somnium 16y ago
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 http://www.eecs.usma.edu/webs/people/okasaki/fpca95.ps Scheme SRFI with implementation http://srfi.schemers.org/srfi-101/srfi-101.html http://srfi.schemers.org/srfi-101/srfi-101.html
- jbapple 16y ago
  > 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 used in a functional setting. As far as I can tell from the Wikipedia page on Exponential-Golumb coding, trellises require Omega(lg n) for cons.
  - jbapple 16y ago
    > trellises require Omega(lg n) for cons. In the worst-case, I mean.
  - daniel-cussen 16y ago
    I get the feeling these can do things Random Access Lists can't (I haven't experimented yet, but I think trellises can support both data and code).
    - somnium 16y ago
      Perhaps you could elaborate on that feeling? (and also clarify what you mean by supporting data and code) The linked SRFI advocates replacing Scheme's traditional pairs/lists with RALists.
      - daniel-cussen 16y ago
        I'm looking at that and McCarthy's eval now.
    - jbapple 16y ago
      > 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 good to learn and explore new things, but from this comment ("support both data and code"?) as well as other comments of yours on this thread and in your code ("I can't really explain it yet, but it works", "I didn't want to weird people out", the assumption that building a data structure out of cons cells makes it different from most data types, supporting your asymptotic analysis by claiming that "it works, at least on my computer", or noting that the reason it works is "mathematical" (yes, mathematics is a language for reasoning about structure, including algorithm correctness), claiming that balanced binary search trees don't have "predictable structure", etc.) makes me suspect of your intuition about this data structure about which you are clearly very excited -- unless you can provide a reason why you have this feeling that doesn't just say what's good about your data structure, but explains what's lacking in Okasaki's It's clear you don't have a lot of experience with the design of functional data structures. I think if you read some of Okasaki's work, you will be better able to communicate statement like "trellises can support both data and code" using prose that other programmers can understand. In this particular case, I suspect my confusion about your feeling is the same as that of somnium in reply to your comment. Okasaki's random access lists are a polymorphic data structure. They can hold anything -- data, code, linguine, fettuccine, bikini. They support pushing an element onto (or removing an element from) the front of the list in O(1) worst-case time, even when used functionally (this has a special meaning here other than "in a functional language" or "in a way that is not broken". Compare "confluently presistent", which is weaker.) They also support lookup (that is, nth) and update of the ith element in O(min(i,lg n)) time. I do not think your data structure supports all of these operations with the same time bounds, and it's unclear what is unique about its ability to "support both data and code".
daniel-cussen 16y ago
Update: I feel I'm not nailing the questions about why this is better than other data types or why this is not identical to other data types. But I found this: http://en.wikipedia.org/wiki/Composite_data_type http://en.wikipedia.org/wiki/Composite_data_type The trellis is a composite data type in lisp, and of those composite data types (which also includes assoc-lists and...?), it is the only one with O(logn) for any of its functions (particularly search). I hope that conveys what I felt was exciting about discovering (or rediscovering) this data type.
- jbapple 16y ago
  > of those composite data types (which also includes assoc-lists and...?), it is the only one with O(logn) for any of its functions (particularly search). I think you meant "all", not "any", since assoc list offers O(lg n) performance for one of its functions. In any case, this is incorrect. You can build any tree-like data structure you like with cons and nil, and, as pointed out elsewhere, Okasaki (as well as others before him), have demonstrated several tree-like data structures with O(lg n) cons, car, cdr, and nth equivalents.
  - daniel-cussen 16y ago
    Which function on assoc lists is O(log n)?
    - jbapple 16y ago
      > Which function on assoc lists is O(log n)? acons is O(1), and the O() notation is for upper bounds, so anything O(1) is also O(lg n).
      - varjag 16y ago
        Strictly speaking, no. Precisely because O-notation defines the worst case. O(1) is not O(log n), since the list insert will never exhibit log behavior.
rntz 16y ago
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 removing the tail element, which are O(log n). So it seems inappropriate to propose trellises as general replacements for lists. Indeed, I'm not sure in what situations this tradeoff of cons/decons- for lookup-speed is helpful. If I just need fast lookup, I'll use a mapping structure (hashtable, balanced binary tree, patricia trie, etc). If I need reasonable lookup speed and also standard sequence manipulations, finger trees or ropes seem like a better choice. They're more complex, but if performance is an issue, then it's probably worth it. Also, a bug/design flaw: You can't store NILs in the terminal position: > (trellis 1 2) (1 (2)) > (trellis 1 2 nil) (1 (2))
- daniel-cussen 16y ago
  About the bug, I talk about this at the end of trellis2.lisp. I didn't want to weird people out by adding a second sentinel to the list. I realize these aren't the best at any one thing, but in situations where you'd normally use lists (exploratory programming, say) you can swap to this for a performance boost.
  - jules 16y ago
    That'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.
    - daniel-cussen 16y ago
      > That's just broken, and will lead to horrible bugs. You mean you think people will use this? Thanks :) Here's how I was thinking of fixing it: (setf nol 'nol) ; make nol evaluate to itself (defun my-null (x) ;redefine null (if (or (null x) (eql nol x)) t null)) Then, change add so that if it's adding a nil, it changes the sentinel at the end of the linked list part of the list to nol. So (trellis 1 2) returns (1 . ((2 . NIL) . NIL)) And (add nil (trellis 1 2)) returns (1 . ((2 . NIL) . NOL)) As soon as someone adds something other than a nil to a cdr of a cons in a tree, add changes nol back to nil.
jules 16y ago
This "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 about numerical representations). His random access lists have O(1) adding an element compared to this O(log n).
puredanger 16y ago
Kind of reminds me intuitively of skip lists where the additional partial lists provide a "fast track" for searching, inserting, and removing in the list in logn rather than n time.

62 points by daniel-cussen 16y ago

I know this is a big claim, but there are mathematical reasons to support why it works. And it works, at least on my computer.

daniel-cussen 16y ago
Also, I'd like to talk about what it does for those that don't feel like reading the GitHub. It's almost exactly like linked lists, except for two things: one, it is less flexible, and two, it is much faster. Most of its functions work in logarithmic time whereas those of linked lists work in linear time. Other than that, it's made of the same things (cons cells), it is navigated the same way (cars and cdrs) it is sequential, so it has clearly delimited first, second, and third elements, and it nests.
jbapple 16y ago
> I know this is a big claim Perhaps, but it needn't be to get the same asymptotic performance. Okasaki's simplest random access list has performance proofs that depend only on the simplest properties of binary numbers, rather than those of the Exponential-Golumb coding, and the code is very easy to write: data BRAL a = Empty | Full (Maybe a) (BRAL (a,a)) deriving (Show) cons :: a -> BRAL a -> BRAL a cons x Empty = Full (Just x) Empty cons x (Full Nothing ys) = Full (Just x) ys cons x (Full (Just y) ys) = Full Nothing (cons (x,y) ys) nth :: Integer -> BRAL a -> a nth 0 (Full (Just x) _) = x nth 0 (Full Nothing xs) = fst (nth 0 xs) nth n (Full (Just _) xs) = nth (n-1) (Full Nothing xs) nth n (Full Nothing xs) = let pair = nth (n`div`2) xs in if n`mod`2 == 0 then fst pair else snd pair

j_baker 16y ago

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. http://en.wikipedia.org/wiki/VList http://en.wikipedia.org/wiki/VList

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.

nickik 16y ago

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?

daniel-cussen 16y ago
You know, I tried clojure out, but the cons cells are implemented in a weird way; they can't combine two objects, only an object and a sequence. So I could probably do something like trellises, but they wouldn't be as elegant.
- cgrand-net 16y ago
  I think one can use [a b] and destructuring instead of cons/car/cdr and be as elegant.
tensor 16y ago
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 https://github.com/clojure/data.finger-tree

aidenn0 16y ago

What is the insertion time on this? It seems like it would be O(n) to insert at the head, at which point why don't you just use a vector? [edit]It is always log(n) to insert at end, which is better than vector in the worst-case

daniel-cussen 16y ago
Insertion into the middle is O(n) because you have to rearrange everything after that. Adding something to the end (#'add) is O(logn). Inserting at the head is indeed slow (unless you are willing to break the structure) but there are many reasons not to use a vector; insertion time isn't everything. With vectors, you have to make sure your vector has empty space left or is a dynamic array. Here, you don't have to worry about anything (short of blowing the stack).

gwern 16y ago

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 http://en.wikipedia.org/wiki/Finger_tree

daniel-cussen 16y ago
Thanks for the link. While they both use trees they're not the same thing.
pjscott 16y ago
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 insert/delete * amortized O(1) push and pop at either end of the sequence * Caching the value of a monoid reduction of each subsequence. Surprisingly useful. Trellises are easier to understand, though.

jemfinch 16y ago

How are these better than balanced binary trees that keep subtree size in the node?

daniel-cussen 16y ago
Predictable structure and smaller nodes. And most of the other advantages linked lists have over binary trees, with some of those advantages being slower.
- jemfinch 16y ago
  If I'm using both as a abstract data types, does predictable structure really help me at all?
  - daniel-cussen 16y ago
    If you're using it for code (the way Lisp uses linked lists) you know when one function ends and a nested one begins. I'd like to point out, however, that this is in theory, as I haven't seen this data structure doing anything other than moving data around.
jbapple 16y ago
> How are these better than balanced binary trees that keep subtree size in the node? I suspect that cons will be )(1) amortized (when the trellis is used ephemerally), which is not true of your usual balanced binary trees. There are many data structures that offer O(1) (amortized or worst-case) modification near the front, and several of them really are just balanced trees but with the pointers down the left spine reversed. In fact, this is a key idea behind Hinze & Patterson's FingerTress, mentioned elsewhere in this thread.

somnium 16y ago

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 http://www.eecs.usma.edu/webs/people/okasaki/fpca95.ps Scheme SRFI with implementation http://srfi.schemers.org/srfi-101/srfi-101.html http://srfi.schemers.org/srfi-101/srfi-101.html

jbapple 16y ago
> 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 used in a functional setting. As far as I can tell from the Wikipedia page on Exponential-Golumb coding, trellises require Omega(lg n) for cons.
- jbapple 16y ago
  > trellises require Omega(lg n) for cons. In the worst-case, I mean.
- daniel-cussen 16y ago
  I get the feeling these can do things Random Access Lists can't (I haven't experimented yet, but I think trellises can support both data and code).
  - somnium 16y ago
    Perhaps you could elaborate on that feeling? (and also clarify what you mean by supporting data and code) The linked SRFI advocates replacing Scheme's traditional pairs/lists with RALists.
    - daniel-cussen 16y ago
      I'm looking at that and McCarthy's eval now.
  - jbapple 16y ago
    > 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 good to learn and explore new things, but from this comment ("support both data and code"?) as well as other comments of yours on this thread and in your code ("I can't really explain it yet, but it works", "I didn't want to weird people out", the assumption that building a data structure out of cons cells makes it different from most data types, supporting your asymptotic analysis by claiming that "it works, at least on my computer", or noting that the reason it works is "mathematical" (yes, mathematics is a language for reasoning about structure, including algorithm correctness), claiming that balanced binary search trees don't have "predictable structure", etc.) makes me suspect of your intuition about this data structure about which you are clearly very excited -- unless you can provide a reason why you have this feeling that doesn't just say what's good about your data structure, but explains what's lacking in Okasaki's It's clear you don't have a lot of experience with the design of functional data structures. I think if you read some of Okasaki's work, you will be better able to communicate statement like "trellises can support both data and code" using prose that other programmers can understand. In this particular case, I suspect my confusion about your feeling is the same as that of somnium in reply to your comment. Okasaki's random access lists are a polymorphic data structure. They can hold anything -- data, code, linguine, fettuccine, bikini. They support pushing an element onto (or removing an element from) the front of the list in O(1) worst-case time, even when used functionally (this has a special meaning here other than "in a functional language" or "in a way that is not broken". Compare "confluently presistent", which is weaker.) They also support lookup (that is, nth) and update of the ith element in O(min(i,lg n)) time. I do not think your data structure supports all of these operations with the same time bounds, and it's unclear what is unique about its ability to "support both data and code".

daniel-cussen 16y ago

Update: I feel I'm not nailing the questions about why this is better than other data types or why this is not identical to other data types. But I found this: http://en.wikipedia.org/wiki/Composite_data_type http://en.wikipedia.org/wiki/Composite_data_type The trellis is a composite data type in lisp, and of those composite data types (which also includes assoc-lists and...?), it is the only one with O(logn) for any of its functions (particularly search). I hope that conveys what I felt was exciting about discovering (or rediscovering) this data type.

jbapple 16y ago
> of those composite data types (which also includes assoc-lists and...?), it is the only one with O(logn) for any of its functions (particularly search). I think you meant "all", not "any", since assoc list offers O(lg n) performance for one of its functions. In any case, this is incorrect. You can build any tree-like data structure you like with cons and nil, and, as pointed out elsewhere, Okasaki (as well as others before him), have demonstrated several tree-like data structures with O(lg n) cons, car, cdr, and nth equivalents.
- daniel-cussen 16y ago
  Which function on assoc lists is O(log n)?
  - jbapple 16y ago
    > Which function on assoc lists is O(log n)? acons is O(1), and the O() notation is for upper bounds, so anything O(1) is also O(lg n).
    - varjag 16y ago
      Strictly speaking, no. Precisely because O-notation defines the worst case. O(1) is not O(log n), since the list insert will never exhibit log behavior.

rntz 16y ago

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 removing the tail element, which are O(log n). So it seems inappropriate to propose trellises as general replacements for lists. Indeed, I'm not sure in what situations this tradeoff of cons/decons- for lookup-speed is helpful. If I just need fast lookup, I'll use a mapping structure (hashtable, balanced binary tree, patricia trie, etc). If I need reasonable lookup speed and also standard sequence manipulations, finger trees or ropes seem like a better choice. They're more complex, but if performance is an issue, then it's probably worth it. Also, a bug/design flaw: You can't store NILs in the terminal position: > (trellis 1 2) (1 (2)) > (trellis 1 2 nil) (1 (2))

daniel-cussen 16y ago
About the bug, I talk about this at the end of trellis2.lisp. I didn't want to weird people out by adding a second sentinel to the list. I realize these aren't the best at any one thing, but in situations where you'd normally use lists (exploratory programming, say) you can swap to this for a performance boost.
- jules 16y ago
  That'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.
  - daniel-cussen 16y ago
    > That's just broken, and will lead to horrible bugs. You mean you think people will use this? Thanks :) Here's how I was thinking of fixing it: (setf nol 'nol) ; make nol evaluate to itself (defun my-null (x) ;redefine null (if (or (null x) (eql nol x)) t null)) Then, change add so that if it's adding a nil, it changes the sentinel at the end of the linked list part of the list to nol. So (trellis 1 2) returns (1 . ((2 . NIL) . NIL)) And (add nil (trellis 1 2)) returns (1 . ((2 . NIL) . NOL)) As soon as someone adds something other than a nil to a cdr of a cons in a tree, add changes nol back to nil.

jules 16y ago

This "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 about numerical representations). His random access lists have O(1) adding an element compared to this O(log n).

puredanger 16y ago

Kind of reminds me intuitively of skip lists where the additional partial lists provide a "fast track" for searching, inserting, and removing in the list in logn rather than n time.