Can we append better?

[treeowl]

It seems plausible that we could append queues in O(min(m,n)) time rather than O(m+n) time. Can we append stacks faster too? Maybe O(m) time?

[treeowl]

For stacks, I think I see a path. If the first argument is deeper than the second (or the same depth), I don't think we can do anything very interesting; everything has to be restructured. But if the first argument is shallower, I think there's quite a bit more potential. Let's think about adding the shapes of two stacks. We need to use carries of up to 3 until the first stack runs out. The step after that, we may have to carry 2. But in the next step, we need to carry at most 1. So we can rebuild the elements of the first stack and an initial segment of the second stack into a fresh stack initial segment plus (possibly) an extra array to insert below. So all in all, m <> n should take O(|m|). It's going to be a bear to implement though...