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