000169879 001__ 169879
000169879 005__ 20190316235225.0
000169879 037__ $$aREP_WORK
000169879 245__ $$aRRB-Trees: Efficient Immutable Vectors
000169879 269__ $$a2011
000169879 260__ $$c2011
000169879 300__ $$a16
000169879 336__ $$aReports
000169879 520__ $$aImmutable vectors are a convenient data structure for functional programming and part of the standard library of modern languages like Clojure and Scala. The common implementation is based on wide trees with a fixed number of children per node, which allows fast indexed lookup and update operations. In this paper we extend the vector data type with a new underlying data structure, Relaxed Radix Balanced Trees (RRB-Trees), and show how this structure allows immutable vector concatenation, insert-at and splits in O(log N) time while maintaining the index, update and iteration speeds of the original vector data structure.
000169879 6531_ $$adata structures
000169879 6531_ $$aconcatenation
000169879 6531_ $$afunctional programming
000169879 700__ $$aBagwell, Philip
000169879 700__ $$0243345$$g185682$$aRompf, Tiark
000169879 8564_ $$uhttps://infoscience.epfl.ch/record/169879/files/RMTrees.pdf$$zPreprint$$s271068$$yPreprint
000169879 909C0 $$xU10409$$0252187$$pLAMP
000169879 909CO $$qGLOBAL_SET$$pIC$$ooai:infoscience.tind.io:169879$$preport
000169879 917Z8 $$x185682
000169879 917Z8 $$x185682
000169879 917Z8 $$x185682
000169879 937__ $$aEPFL-REPORT-169879
000169879 973__ $$sPUBLISHED$$aEPFL
000169879 980__ $$aREPORT