In the latter definition, Cons a (interleaveStreams bs as), (interleaveStreams bs as) is a thunk. The thunk should only be evaluated when it is needed.  In my original definition, (interleaveStreams as bs) is a thunk. The difference is an extra Cons (e.g., Cons b).  It seems like the additional Cons is causing problems, I just don't understand why. Can anyone point out what I'm missing?