[Haskell-beginners] Re: Understanding cached fibonnacci function

[Heinrich Apfelmus]

Patrick LeBoutillier wrote:
>>
>>  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...).

Well, you can just try to replace fix by its definition and see what
happens:

   fix (\r x y -> x : r y (x+y)) 0 1
 =
   (let go = (\r x y -> x : r y (x+y)) go in go) 0 1
 =
   let go = \x y -> x : go y (x+y) in go 0 1
 =
   let go x y = x : go y (x+y) in go 0 1

In other words,  fix  can define a recursive function.

-- 
http://apfelmus.nfshost.com