After a nasty and prolonged debugging session, finally isolated the problem that was producing bizarre results to the Distributive instance for Tapes. The problem was that the instance duplicated the center element in both directions, so that if you had (conceptually):

t = Tape [..., 3, 2, 1] 0 [1, 2, 3, ...]

Then if you did distribute (Just t), you'd get:

Tape [..., 3, 2, 1, 0] 0 [0, 1, 2, 3, ...]

And *this* is what was screwing with everything forever.

Holy crap, that was a hard bug to find. And you know what would have made it easier? Testing. Adding to todo list: create QuickCheck tests for my stuff, especially basic identities about the various laws that should hold.