Fun w/ lazy streams (was RE: functional programming)

[Tim Peters]

[Moshe Zadka]
> Just one thing bugged me:

Hmm!  Something else bugged me:  the version I got back on the mailing list
said "filter" in one place where "sfilter" is in the original program, so
the "stream of primes" example blew up.  So, if that happens to anyone else,
change any instance of "filter" to "sfilter".  I probably bumped the
"delete" key in my eagerness to see what the timbot was posting <wink>.

> ...
> Tim, with the natural implementation of even_stream, and odd_stream,
> you do realize (of course you do) that
>
> sintersect2(even_stream, odd_stream)
>
> is a good old fashioned infinite loop?

Oh yes.  I bothered to write an "infinite loop" caution for sfilter's
docstring, but got bored, so you should consider it implied everywhere else
<wink -- it's a potential problem for sintersect and sdifference too, but
that's it>.

> (What's more : sintersect2(even_stream, prime_stream) is not an infinite
> loop, but taking its tail *is*)

Yes, that's business as usual for this kind of approach too -- nothing gets
computed until something else *requires* it.  The raw intersection is, in
effect, a delayed function evaluation.  It's not until you specifically try
to extract the tail (or head!) that the hopeless computation gets invoked.

Here's the same thing in Haskell (read ":" as an infix cons):

sintersect2 (x:xs) (y:ys)
    | x == y    = x : sintersect2 xs ys
    | x < y     =     sintersect2 xs (y:ys)
    | otherwise =     sintersect2 (x:xs) ys

evens = [2, 4 ..]
odds  = [1, 3 ..]

hopeless = sintersect2 evens odds

No problem there, but you'll wait forever if you try to print

   head hopeless
or
   tail hopeless

Note the key word "print" there, though!  Haskell is profoundly lazy, and
e.g. the further definitions

    h = head hopeless
    t = tail hopeless

don't cause a problem either -- unless you try to display h or t, or use
them in some other context that actually requires one to get evaluated.

> I sort of wonder how common this bug is in Haskell: it doesn't *look* like
> an infinite loop.

I'd say it's a common enough newbie problem, akin to getting surprised by
mutable default args in Python.  It's rare after experience, for two
reasons:  working with infinite streams requires picking up a few "tricks of
the trade" (this is one), and functions like sintersect2 are pretty rare in
practice.  An experienced programmer knows better than to *try* to intersect
infinite streams unless they have a priori reason to believe that the
intersection is also infinite.  So if they flub that, it's viewed not as a
bug in the code but as a failure of analysis.

Note one curious thing:  the "vulnerable" stream functions I posted in
Python are obvious from inspection:  they're exactly the ones that begin
with a "while" loop!  It's harder to see the true source of the potential
problem if they're written recursively instead (so much for recursion always
being easier to reason about <0.9 wink>).

> BTW: It reminded me of implementing the same thing in Scheme, where
> everything is natural as breathing (with a snorkel, and through the ears,
> but what the heck <wink>)
>
> I actually think it was the same thing, except I didn't implement
> intersect (probably unconcious fear of the infinite loop)

Scheme, Haskell or Python, it's inherent in the problem domain.  After all,
even a simple "x in stream" is (in general, when stream is unbounded)
undecidable.

recusively-enumerable-made-concrete-ly y'rs  - tim