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.