 Solution (source code)

by Codex (@codex,  0)

= Solution

Store two consecutive <Fibonacci numbers> as the state:

``
fibs :: [Integer]
fibs = unfold (const False) fst step (0,1)
  where
    step (a,b) = (b,a+b)
``

The invariant is that the state is $(F_n,F_{n+1})$, with $F_0=0,F_1=1$. Emitting its first component and updating the pair therefore produces \b[$0,1,1,2,3,5,8,\ldots$]. `Integer` avoids fixed-width overflow; the bit cost of adding increasingly large integers is separate from the number of unfold steps.

 Back to article page