Even can be odd

Wadler et al's criticism of the "odd" style of laziness is that it forces some unnecessary (and possibly unwanted) computation. Because only the tail of a stream is delayed, a stream-valued function always computes the head eagerly, even when it isn't needed. They show an example like the following, where taking a prefix of a stream still ends up computing too much because take can't prevent stream-map from computing the first element of the unwanted suffix:

...
→ E[(take 0 (stream-map div (countdown 0)))]
→ E[(take 0 (cons (div 0)
                  (delay
                   (stream-map div (countdown -1)))))]
→ error: division by zero

Their point is well-taken: languages like Haskell have a clearer model of need, and the SICP style of semi-lazy lists is, well, a bit odd.

But today Richard Cobbe warned me of an important subtlety with the authors' proposed "even" streams. Making streams fully lazy, so that neither the head nor the tail is forced unless it is observed, effectively removes any enforcement of order between their computations. In a pure functional language like Haskell, this is fine, but if your stream abstraction is built on top of, say, file I/O, it's all too easy to perform a simple refactoring like lifting a recursion into a let-bound variable:

(define (f str)
  ... (let ([rest (f (stream-cdr str))])
        ... (stream-car str) ... rest ...))

and suddenly you'll find your result stream is backwards, or even permuted!

I'm actually surprised the monadologists in question didn't address this (I've only skimmed the paper, so maybe I missed it). Monads add strictness to a non-strict language to pave the way for side effects, so naturally adding non-strictness to a strict language that already had side effects is going to be tricky.

I don't have any great categorical magic tricks to offer as a solution. But I imagine you could enforce the dependency by brute force: use even streams, except implement stream-cdr in such a way that it first forces the evaluation of the head.

Now I need to read SRFI-45 to understand the subtleties of tail-safe lazy computation, and then maybe I'll finally start feeling comfortable writing stream abstractions in Scheme. I really want to use streams: they make excellent abstractions of many I/O patterns. But they are fiendishly subtle.