Brian Hulley wrote:
jerzy.karczmarczuk@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). Thanks. Jerzy Karczmarczuk