[Haskell-cafe] Functional progr., images, laziness and all the rest

Jerzy Karczmarczuk jerzy.karczmarczuk at info.unicaen.fr
Thu Jun 22 04:49:49 EDT 2006

Brian Hulley wrote:
> jerzy.karczmarczuk at info.unicaen.fr wrote:

>> you may transform a recurrential equation yielding Y out of X:
>> Y[n+1] = a*X[n+1] + b*Y[n]
>> usually (imperatively) implemented as a loop, into a stream
>> definition:
> Can you explain how this transformation was accomplished?
> I don't see how
>     yq = a * xq + b * y
> relates to
>    Y[n+1] = a*X[n+1] + b*Y[n]  -- (assuming the X[N+1] was a typo)
> since y is a longer list than yq but Y[n] is an earlier element than 
> Y[n+1], so it seems that the function is multiplying b by a later factor 
> than it should.

Sure, y[n] is earlier, so defining the tail by the stream itself refers
an element to its predecessor. No problemo Baby, as used to say
Terminator 2, whose relevance to our problem is obvious, since he
also couldn't terminate him(it)self...

Let's write the stream construction once more. Starting with x=(x0:xq)
and parameters a and b, assuming that for n<0 you take zero:

y  = (a*x0:yq)       -- Here I was in error, "a" missing
yq = a*xq + b*y

with, of course, a*xq meaning map(a*) xq; x+y meaning zipWith(*) x y ...

                 y0 = a*x0
Look yourself:  y1 = a*x1 + b*y0
                 y2 = a*x2 + b*y1, etc. So, first, this is correct,
                                   element by element.

Don't tell me you have never seen the assembly of all non-negative
integers as an infinite list thereof:

integs = 0 : (integs + ones)   where ones = 1:ones

it is quite similar (conceptually).

y IS NOT a longer list than yq, since co-recursive equations without
limiting cases, apply only to *infinite* streams. Obviously, the
consumer of such a stream will generate a finite segment only, but it
is his/her/its problem, not that of the producer.

> So:
> 1) Someone reading the code needs to do a lot of work to try to recover 
> the original equation
> 2) Wouldn't an imperative loop, using the original equation directly, 
> have made everything much simpler?
> 3) Therefore laziness has lead to obfuscated code.

1. Such codes are not meant to be thrown at an unprepared audience. Either
    the reader knows something about stream processing, or some introduction
    is necessary.

2. Are we speaking about assembly-style, imperative programming, or about
    functional style? Please write your loop in Haskell or any other fun.
    language, and share with us its elegance.
    Please note that for stream-oriented applications, as the sound processing
    I mentioned, this "n" index has no meaning whatsoever, it just denotes
    a position within the stream. Index-less style is more compact, with less
    redundant entities.

3. Full disagreement. There is NOTHING obfuscated here, on the contrary, the
    full semantics is in front of your eyes, it requires only some reasoning
    in terms of infinite lists. See point (1).


Jerzy Karczmarczuk

More information about the Haskell-Cafe mailing list