Having spent several months on this exact problem, I'll say that I consider it pretty unlikely. I wouldn't be very surprised if that was the case.
A clever data structure might give you logarithmic or even amortized constant time access in sequential cases, but you probably will not have good garbage collection properties (all data will remain for all time). I guess cleverness should be concentrated on aging streams properly. But I do see how the ability to extract the diagonal conflicts with such efforts.
Stick with Applicative for this type of thing. Monad will drive you insane :-) In fact, even applicative is far from trivial. ;) For instance, I still can't see how I could implement the <*> operator with stateless streams that don't need to keep track of their local time (needed when combining them with stateful streams, that is).
Gergely -- http://www.fastmail.fm - Access all of your messages and folders wherever you are