More of an data structure question than a Rust question:
Can someone please motivate how one would invent Finger tree - Wikipedia (in particular: what problem does finger tree solve that avl tree, red-black tree, and b-tree all fail to solve?)
The part that baffles me is:
data FingerTree a = Empty
| Single a
| Deep (Digit a) (FingerTree (Node a)) (Digit a)
data Node a = Node2 a a | Node3 a a a
The confusing line is:
data FingerTree a = | Deep (Digit a) (FingerTree (Node a)) (Digit a)
The confusing part is that the 'spine' does not go FingerTree a -> FingerTree but instead it goes:
FingerTree a -> FingerTree (Node a) -> FingerTree (Node (Node a)) -> ...
Simple: Amortized constant time push and pop operations on both ends. (And that in a persistent data structure with arbitrarily branching access patterns. And it can be implemented in a pure functional programming language (as long as you have some way of doing lazy evaluation).)
It's a truly marvelous data structure. In Haskell you have then called Data.Sequence.
As to how to come up with them: no idea. I've read somewhere the they're like an ordinary tree but somehow upside down and you enter the thing by its bottom ends. I don't remember where I've seen that.
That thing is a somewhat weird (when you see it first) technical trick that's allowing you to prescribe you have some sort of full n-ary trees of increasing height at at depths of the FingerTree hierarchy.
It makes more sense once you've seen how to do full/perfect binary trees in Haskell in much the same way (for example, see the NTree data type in this blog post). By the way, this is something that Rust can't do. Because of monomorphization, Rust doesn't have “polymorphic recursion” which is necessary to handle data types like this.
I am not sure I am understanding your statement correctly. Are you saying that because of the FingerTree a -> subfield of type FingerTree(Node a) that therefore we can not implement FingerTree in Rust (i.e. Rust may generate infinite number of structs in trying to expand FingerTree<T> ?). Can you expand on this more ?
Unfortunately I'm on mobile, so it's hard to do anything too much more detailed, in particular involving code examples. Perhaps reading that blog post (it even mentions finger trees and links to a paper) or other sources on polymorphic recursion and nested datatype helps on the meantime.
Of course we can implement finger trees in Rust, just not the same way as that Haskell implementation, and a Rust version may involve more in variants not provided by the type system. That way you get less help by the type checker to not mess up your tree's levels, and perhaps you get some overhead checking certain Optons to be Some at runtime.. (unless you allow unsafe code).
I feel like there's a lot of technical terms in here. Let me explain what this is all about.
Amortized constant time means that in a sequence of operations, the amortized times of all the operations together give an upper bound on the actual time the operations take alltogether. If you do 100 constant time operations, it may be that the first 99 ones take 1 unit of time and the last one takes 101 units of time. An amortized analysis might have credited each operation with 2 units of time, and you've built some form of "dept" that was payed back by the occasional more-expensive-than-advertised operation.
Persistent data structure means, modifying the data structure doesn't consume the pervious version. Instead you keep the old state and also get the new state, and can then continue working with both of them independently however you want to.
A naive amortized analysis may not account for persistent data structures: You can break the promise of amortized constant time if you single out the occasional actually-expensive operation and recompute that operation repeatedly. If our first 99 operations were cheap, but the last one took 101 units of time, and repeating just the last one over and over is possible (because we've persisted the state just before that operation), then that's a problem.
The finger tree solves this problem by making sure that when you repeat a too-expensive operation, all repetitions after the first execution are actually-cheap. The persistent data structures work by sharing a lot of data under the hood anyways, with some form of interior mutability you can thus "cache" the result of expensive operations and make repeating them cheap.
This interior mutability must not actually observably mutate anything, since persistent data structures are immutable. It's, as I mentioned, more of a "cache". In this way it's similar to lazy evaluation, which also mutates stuff under the hood (replacing an unfinished computation with its results) but not observably so (accessing the lazy value a second time is faster (because it's already pre-computed) but produces the same result).
Finger trees can be (and are) implemented in Haskell in such a way that all the necessary hidden interior mutability comes in the form of lazy evaluation. It's clever use of lazy evaluation that lays the ground for the data structure's strong properties in terms of amortized time complexity for pushing and popping elements at either end.
This concrete example case is easy to handle, really, but in a generic case you'd probably send the type resolver into infinite recursion again. (You'd also regret not using boxes pretty quick...)
