I\'m writing a data structure library, and I want to write an efficient algorith
ID: 648988 • Letter: I
Question
I'm writing a data structure library, and I want to write an efficient algorithm for adding many elements to a finger tree (from an iterable sequence). I'm going to do this by constructing a finger tree from the sequence efficiently, as described below, and then concat it to the original finger tree. Concat is a very cheap operation compared to adding many elements.
To construct the finger tree, I put the elements into an array, and get its length. Then I build the finger tree from the bottom up, starting with the deepest deep tree and working outwards. This should be much, much more efficient.
In order to do this, I must guess the structure of the resulting finger tree from the number of elements to be added, and I'm not sure how to do this.
Explanation / Answer
From first principles, every 2-3 tree is a finger tree viewed from another angle, so you could solve the problem by solving the somewhat easier problem of "What shape are the valid 2-3 trees of size n?"
You can also look at many existing finger-tree libraries. The first one created, was, of course, the Haskell one. The function you are looking for is replicate, which takes a value v and size n, then creates a finger tree of size n containing n copies of v. The real work of replicate is done in applicativeTree, which has individual cases for n?8 and recurses for larger n.