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.
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
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.
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.
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.
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.
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).
> 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.
> 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.
> 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".
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
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.
> 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.
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.
Strictly speaking, yes. O-notation describes the growth of a function as the argument tends to infinity. Formally, the statement "f(x) is O(g(x))" means that there's some point x_0 such that f(x) is less than a constant factor times g(x) for any x > x_0.
This is clearly the case for f(n) = 1, g(n) = lg(n), hence the constant function is O(lg(n)).
An algorithm can be O of different g(x)s, depending on the properties of the input. For example, the runtime of a naive quicksort implementation (which always chooses the leftmost value as a pivot) is O(n^2) if the input list is sorted, while it has runtime O(n*lg(n)) on average and in the best case (where the pivot is always the median of the section of the list being partitioned).
> This is clearly the case for f(n) = 1, g(n) = lg(n), hence the constant function is O(lg(n)).
It is not, because constant function has no logarithmic behavior. To distinguish that is the whole point of big-O notation. When you tell someone "this is a O(logn) operation" they do expect log performance.
Yes O(c) is strictly under O(n) too, but so what? We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions.
> When you tell someone "this is a O(logn) operation" they do expect log performance.
If you look in the appendix of your algorithms textbook that explains big-O notation, you will see this is not the actual definition. I'm sorry if my usage confused you, but I was using it in the formal sense of "there exists an N such that there exists a c such that for all m > N, f(m) <= c*g(m)". In your log example, we can choose N = 2 and c = 1.
> We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions.
For saying "f is doubly-exponential", use Theta. For saying "f is doubly-exponential or smaller", use big-O.
> It would be one of those formally correct but practically useless definitions.
"Hi, my name is Aperiodic, and I'm... a mathematician."
"Hi Aperiodic."
"It all started out so easily; you know, a few lemmas with the boys in the evenings. But before I knew it, I was picking up Bourbaki as soon as I got home from work. I would wake up in the mornings, surrounded loose sheets of paper covered in commutative diagrams, without a clear idea of what I did last night..."
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:
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.
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.
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).
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.
45 comments
[ 5.3 ms ] story [ 96.1 ms ] threadIt'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.
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:
http://en.wikipedia.org/wiki/VList
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.
Am I interpreting that right?
What are the benefits of these over clojure vectors?
https://github.com/clojure/data.finger-tree
[edit]It is always log(n) to insert at end, which is better than vector in the worst-case
* 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.
And most of the other advantages linked lists have over binary trees, with some of those advantages being slower.
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.
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.
Scheme SRFI with implementation http://srfi.schemers.org/srfi-101/srfi-101.html
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.
In the worst-case, I mean.
The linked SRFI advocates replacing Scheme's traditional pairs/lists with RALists.
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".
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.
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.
acons is O(1), and the O() notation is for upper bounds, so anything O(1) is also O(lg n).
This is clearly the case for f(n) = 1, g(n) = lg(n), hence the constant function is O(lg(n)).
An algorithm can be O of different g(x)s, depending on the properties of the input. For example, the runtime of a naive quicksort implementation (which always chooses the leftmost value as a pivot) is O(n^2) if the input list is sorted, while it has runtime O(n*lg(n)) on average and in the best case (where the pivot is always the median of the section of the list being partitioned).
It is not, because constant function has no logarithmic behavior. To distinguish that is the whole point of big-O notation. When you tell someone "this is a O(logn) operation" they do expect log performance.
Yes O(c) is strictly under O(n) too, but so what? We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions.
If you look in the appendix of your algorithms textbook that explains big-O notation, you will see this is not the actual definition. I'm sorry if my usage confused you, but I was using it in the formal sense of "there exists an N such that there exists a c such that for all m > N, f(m) <= c*g(m)". In your log example, we can choose N = 2 and c = 1.
> We can just as happily declare most functions double-exponential in complexity, but what use is that? It would be one of those formally correct but practically useless definitions.
For saying "f is doubly-exponential", use Theta. For saying "f is doubly-exponential or smaller", use big-O.
http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachma...
"Hi, my name is Aperiodic, and I'm... a mathematician."
"Hi Aperiodic."
"It all started out so easily; you know, a few lemmas with the boys in the evenings. But before I knew it, I was picking up Bourbaki as soon as I got home from work. I would wake up in the mornings, surrounded loose sheets of paper covered in commutative diagrams, without a clear idea of what I did last night..."
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:
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.
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.