Timeline for Is there a purely functional vector with O(1) access to the front and back but O(log n) concatenation?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2023 at 22:01 | answer | added | Glenn Tang | timeline score: 3 | |
| Dec 17, 2014 at 14:53 | comment | added | jbapple |
Yes, Hinze and Paterson's finger trees have amortized $O(1)$ car, amrtized $O(\log n)$ updating, and amortized $O(\log n)$ append.
|
|
| Dec 15, 2014 at 16:59 | comment | added | Andrej Bauer | I am just scrtaching the back of my skull, but where do finger trees stand on this issue? | |
| Dec 14, 2014 at 15:17 | comment | added | jkff | I'm not so sure about prepend, but it would be fast for append. | |
| Dec 14, 2014 at 14:38 | comment | added | ithisa |
Hmm. That seems interesting. So with such a technique, constructing an array by (prepend 1 (prepend 2 (prepend 3 (prepend 4 empty)))) would be reasonably fast?
|
|
| Dec 14, 2014 at 5:39 | comment | added | jkff | I think you'd get what you want (O(1) indexing, O(log n) concat, very fast element append) by combining Clojure's HAMT with some generic techniques along the lines of Haskell's "diff arrays" hackage.haskell.org/package/array-0.2.0.0/docs/… - e.g. make the pointer block be a slice of a (mutably growable, COW) array. On append, append to the array and return a grown slice. On append to a non-recent slice, you'll need to create a new mutable block, but it solves the typical "append in a loop" problem. | |
| Dec 14, 2014 at 3:46 | history | edited | ithisa | CC BY-SA 3.0 |
added 64 characters in body; edited title
|
| Dec 14, 2014 at 3:34 | comment | added | ithisa |
Amortized would be fine. I meant appending two vectors ("concatenation"). Mutable state is fine as long as all the operations on the objects are referentially transparent: i.e. users should be able to pretend that they are purely functional vectors. This kinda implies O(1) to all versions, the idea of "version" is not exposed to the user.
|
|
| Dec 14, 2014 at 2:28 | comment | added | jkff | Please clarify if you mean appending an element or appending two vectors, and whether you're interested in purely functional data structures or its OK to use mutable state. Also, should access be O(1) to the latest version of the structure, or to all versions? Worst case or amortized? | |
| Dec 13, 2014 at 21:43 | history | tweeted | twitter.com/#!/StackCSTheory/status/543883926897688576 | ||
| Dec 13, 2014 at 21:06 | history | edited | ithisa | CC BY-SA 3.0 |
edited title
|
| Dec 13, 2014 at 20:55 | history | asked | ithisa | CC BY-SA 3.0 |