I'm not an authority on pure functional programming, and I don't have any working code, so takes this with a grain of salt. But this:
Only the rightmost X has the information about the operation and there is only one slot free to pass an iterator.
Is it possible to write the intermediate (and final) iterators in a purely functional way that the operation (here plus) is incapsulated within the logic of the passed iterators?
sounds an awful lot like you solve the "only one free slot" problem by returning a more complicated object, like an array ref of [$operator, $iterator]. Of course that changes the calling convention of the subsequent operations, and you'll likely want to write a lift function that deals with the changed calling convention for you. And congratulations, you have invented monads.
Which is, of course, the way to solve problems in purely functional languages which you'd solve with state in impure languages.