2 ms·
Even ignoring real hardware, finger trees are only efficient in an amortized sense where more specialized purely functional data structures offer better real-ti
by catnaroek 10y ago
Even ignoring real hardware, finger trees are only efficient in an amortized sense where more specialized purely functional data structures offer better real-time guarantees.
(0) Asymptotically optimal heaps: Worst-case O(1) insert, merge and findMin. Worst-case O(log n) delete.
(1) Asymptotically optimal search trees: Worst-case O(log n) lookup, insert, update, delete.
(2) Asymptotically optimal deques: Worst-case O(1) cons, head, tail, snoc, init, last.
etc.
Another downside is that they require somewhat fancy language features (namely, polymorphic recursion) to implement in a type-safe way.