Finger Trees: A Simple General-purpose Data Structure by Ralf Hinze and Ross Paterson.
This paper presents 2-3 finger trees, a purely functional representation of persistent sequences. The ends of each sequence can be accessed in amortised constant time and they can be concatenated and split in logarithmic time. Best of all, the paper develops them in Haskell.
I've started working through the code myself, but have not yet managed to get it finished.
DOI | LtU | CiteULike | Del.icio.us
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment