Albert Y. C. Lai trebla at vex.net
Tue May 29 17:56:31 EDT 2007

```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.

```