I've been working on implementing an efficient Cartesian product operation (actually the <*> operation, but it amounts to about the same thing) for sequences based on Hinze and Paterson's Finger trees: a simple general-purpose data structure. It seems that a natural way to calculate $xs \times ys$ when $xs$ and $ys$ each has at least two elements is to (conceptually) replace each leaf $x$ in $xs$ with a 2-3 tree representing $\{(x,y)\mid y \in ys\}$, and then stretch the first and last element of the resulting tree upwards/outwards to bring the tree to the proper depth. But for efficiency and other reasons, this actually needs to be done in the opposite directionI'd need to pull off the first and last element of $xs$, and then work my way down, calculating at each level how much of $ys$ to leave behind there, and also to check whether it's possible to represent $ys$ by a 2-3 tree of the appropriate size for that level. I'm not really sure how to get a grip on the necessary math.
How can I calculate tree sizes to stretch up a finger tree?
data structures;search trees