[Haskell-beginners] Re: Understanding cached fibonnacci function

[Thomas Davie]

On 30 Jan 2009, at 17:41, Patrick LeBoutillier wrote:

>>> fibs = fix ((0:) . scanl (+) 1)
>>
>> I don't like that one.  My favorite is the following, because it's
>> short, concise and still very comprehensible:
>>
>> import Data.Function
>>
>> fibs :: Num i => [i]
>> fibs = fix (\r x y -> x : r y (x+y)) 0 1
>
> Can someone please explain this one? I can't seem to figure out what
> 'fix' does (the definition in the documentation is a bit to
> mathematically inclined for me...).

It computes a fixed point for a function – that is a value which when  
passed to the function gives back the same answer.  Some examples:

fix id – any value is a fixed point for id, no matter what you give  
it, it always comes back the same!

fix (+ 1) – no values, no matter what you give it, it'll always come  
out one bigger, so there's no fixed point here

fix (1:) – the infinite list of 1s, if you put a 1 on the front of it,  
you get back the inifinite list of ones again.

fix (\r x y -> x : r y (x+y)) – Lets try giving this function to  
itself: (\r x y -> x : (y : r (x+y) (y+(x+y)))), and again... (\r x y - 
 > x : (y : ((x+y) : r (y+(x+y)) ((x+y)+y+(x+y))))... you can see  
where this is going, if we apply this to 0 and 1, we get 0 : 1 :  
(0+1) : (1 + (0 + 1)) : ... fibonacci numbers.

In general, we can write *any* recursive function using the fix  
function, we transform the function to accept another argument first,  
we replace all recursive calls with calls to this argument, and we  
wrap it in the fix function.

Hope that helps.

Bob