Show HN: New Lisp data structure

Re:Show HN: New Lisp data structure by gwern on Wednesday December 01, 2010 @06:11PM (#1960145)

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

[ Parent | on HN ]

Re:Show HN: New Lisp data structure by pjscott on Wednesday December 01, 2010 @06:32PM (#1960218)

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.

[ Parent | on HN ]

Re:Show HN: New Lisp data structure by daniel-cussen on Wednesday December 01, 2010 @06:13PM (#1960163)

Thanks for the link. While they both use trees they're not the same thing.

[ Parent | on HN ]