5
$\begingroup$

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 direction—I'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.

$\endgroup$
1
$\begingroup$

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 "zipping" 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 <*> and *> implementations now use this technique; the latter takes advantage of Louis Wasserman's applicativeTree function to obtain asymptotic reductions in time and allocation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.