[Haskell-cafe] Cute code [was: The C Equiv of != in Haskell miscommunication thread]

[Albert Y. C. Lai]

Vincent Kraeutler wrote:
> Donald Bruce Stewart wrote:
>> P.S. Have some cute code:
>>
>>     Control.Monad.Fix.fix ((1:) . scanl (+) 1)
>>   
> either way, if one of the Masters Of The Shadow Y Style on this list
> feels like throwing in another koan or two, you'll have at least one
> thankful audience member ;-)

Rewriting in a more beginner form:

s = 1 : scanl (+) 1 s

Recursively defined lists are sometimes hard to predict. Here is a 
systematic way of watching what it does. Inspired by a theorem about 
fixed points, the following sequence gets closer and closer to the 
solution to s = f s:

_|_, f _|_, f (f _|_), f (f (f _|_)), ...

Applying this to our example,

_|_
1 : scanl (+) 1 _|_ = 1:1:_|_
1 : scanl (+) 1 (1:1:_|_) = 1:1:2:3:_|_
1 : scanl (+) 1 (1:1:2:3:_|_) = 1:1:2:3:5:8:_|_

You can continue the process until you run out of patience or you see 
the pattern. It is an alternative way to execute the recursion. It is 
harder in some cases (e.g., recursive functions) but easier in some 
others (e.g., recursive lists).

Executing a program to look for a pattern is the hardest way to 
understand it. (Sadly, in most schools it is the only way taught.) 
Deriving it from a specification provides more insight, answers the 
itching question "so how did you come up with this magic", takes away 
the mysticism, teaches more lessons, and moves programming closer to 
science-based engineering and further from secret-based guild.

We wish to compute a fibonacci-like sequence s with given s0 and s1, and 
s(n+2) = s(n+1) + sn afterwards. We already know a million ways, but 
today we add one more. After some exploration, we find

s(n+1) = s1 + (s0 + s1 + s2 + ... + s(n-1))
        = scanl (+) s1 s !! n

(This applies to s1 too: scanl (+) s1 s !! 0 = s1.)

Let me abbreviate "scanl (+) s1 s" as "f s". So s(n+1) = f s !! n.

s = [s0, s1, s2, s3, ...]
   = [s0, f s !! 0, f s !! 1, f s !! 2, ...]
   = s0 : f s
   = s0 : scanl (+) s1 s

Now we have it.