[Haskell-beginners] Re: Understanding cached fibonnacci function
Thomas Davie
tom.davie at gmail.com
Fri Jan 30 11:55:25 EST 2009
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
More information about the Beginners
mailing list