I once read a textbook I think I've read that book too. For the benefit of anyone following along at home: The unproven-but-accepted Church-Turing thesis stat

I once read a textbook I think I've read that book too. For the benefit of anyone following along at home: The unproven-but-accepted Church-Turing thesis states that any algorithm that can be done on a Turing machine (i.e., a Turing-complete language) can be represented as a recursive function and a function in the lambda calculus, and vice-versa. And then I can apply deforestation techniques and tail-call optimization to derive the iterative algorithm from the stream algorithm. How do you use deforestation and tail-call optimization to derive an iterative function from a stream in the general case? You're also pulling a false comparison: you've jumped from a 'general' algorithm to "what a corecursive function is evaluated as under Haskell's semantics". Corecursion builds a data structure. A TCO function, for example, won't produce that kind of output. The corecursive function could only be directly equivalent to the linear time, constant memory TCO function in a lazily-evaluated runtime (if that's true - tail recursive functions in Haskell can actually blow up the stack due to lazy evaluation).