How can I calculate tree sizes to "stretch up" a finger tree?
As it turns out, the best way to calculate the necessary tree sizes is not to. While crushing down one copy of the $ys$ finger tree (in a process reminiscent of &quot;zipping&quot; a Huet zipper), I can simultaneously crush down just one side of each of two additional copies, while pulling digits off the other sides to use directly (no calculation!). When I get near the bottom, I finish off the complete 2-3 tree, and then attach the two crushed half-trees to the $xs$ finger tree (once I've replaced its leaves using the complete 2-3 tree).
Edit (March, 2015)
The code (recently simplified and cleaned up) can be found in the GitHub repository. Both the &lt;*&gt; and *&gt; implementations now use this technique; the latter takes advantage of Louis Wasserman's applicativeTree function to obtain asymptotic reductions in time and allocation.