# Understanding cached fibonnacci function

9 messages
Open this post in threaded view
|

## Understanding cached fibonnacci function

 Hi all, I recently stumbled on this example in some wiki: mfib :: Int -> Integer mfib = (map fib [0 ..] !!)   where fib 0 = 0         fib 1 = 1         fib n = mfib (n-2) + mfib (n-1) I don't understand how the results get cached. When mfib is recursively called, doesn't a new (map fib [0 ..] !!) start over again? Or perhaps I'm thinking too imperatively here... Also, if I change the definition to this (adding "a" on both sides): mfib :: Int -> Integer mfib a = (map fib [0 ..] !!) a   where fib 0 = 0         fib 1 = 1         fib n = mfib (n-2) + mfib (n-1) the funtion becomes slow again. Why is that? Thanks a lot, Patrick LeBoutillier -- ===================== Patrick LeBoutillier Rosem?re, Qu?bec, Canada
Open this post in threaded view
|

## Understanding cached fibonnacci function

 On 29 Jan 2009, at 19:46, Patrick LeBoutillier wrote: > Hi all, > > I recently stumbled on this example in some wiki: > > mfib :: Int -> Integer > mfib = (map fib [0 ..] !!) >  where fib 0 = 0 >        fib 1 = 1 >        fib n = mfib (n-2) + mfib (n-1) > > I don't understand how the results get cached. When mfib is > recursively called, doesn't a new (map fib [0 ..] !!) start over > again? Or perhaps I'm thinking too imperatively here... > > Also, if I change the definition to this (adding "a" on both sides): > > mfib :: Int -> Integer > mfib a = (map fib [0 ..] !!) a >  where fib 0 = 0 >        fib 1 = 1 >        fib n = mfib (n-2) + mfib (n-1) > > the funtion becomes slow again. Why is that? The reason that the second one is slower is that ghc makes a   distinction that so called CAFs (constant applicative forms) are   likely to be constants, and evaluates them once.  Thus, your list (map   fib [0..]) gets kept between runs.  In the second form though, ghc   sees a function, and evaluates it every time it gets called, which   makes it into an exponential time algorithm. An aside:  fibs !! 0 is usually defined to be 1. Here's another couple of definitions of fib for you to play with, and   try and figure out the properties of: mfib :: Int -> Integer mfib = ((fibs  1 1) !!) fibs :: Integer -> Integer -> [Integer] fibs n m = n : fibs m (n+m) -- and fibs :: [Integer] fibs = 1 : 1 : zipWith (+) fibs (tail fibs) Have fun Bob
Open this post in threaded view
|

## Understanding cached fibonnacci function

 Am Donnerstag, 29. Januar 2009 20:29 schrieb Thomas Davie: > > The reason that the second one is slower is that ghc makes a > distinction that so called CAFs (constant applicative forms) are > likely to be constants, and evaluates them once.  Thus, your list (map > fib [0..]) gets kept between runs.  In the second form though, ghc > sees a function, and evaluates it every time it gets called, which > makes it into an exponential time algorithm. However, if you compile it with -O2, the optimiser sees it's better to keep the list and it's again a linear time algorithm. > > An aside:  fibs !! 0 is usually defined to be 1. I meet fibs !! 0 == 0 more often. > > Here's another couple of definitions of fib for you to play with, and > try and figure out the properties of: > mfib :: Int -> Integer > mfib = ((fibs  1 1) !!) > > fibs :: Integer -> Integer -> [Integer] > fibs n m = n : fibs m (n+m) > > -- and > fibs :: [Integer] > fibs = 1 : 1 : zipWith (+) fibs (tail fibs) > > Have fun Not to forget the marvellous import Control.Monad.Fix fibs :: [Integer] fibs = fix ((0:) . scanl (+) 1) > > Bob
Open this post in threaded view
|

## Re: Understanding cached fibonnacci function

 Daniel Fischer <[hidden email]> wrote: > Not to forget the marvellous > > import Control.Monad.Fix > > fibs :: [Integer] > 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 Replace 0 by 1, if you want to exclude it from the sequence.  I prefer to include it. Greets, Ertugrul. -- nightmare = unsafePerformIO (getWrongWife >>= sex) http://blog.ertes.de/
Open this post in threaded view
|

## Re: Understanding cached fibonnacci function

 Am Freitag, 30. Januar 2009 15:59 schrieb Ertugrul Soeylemez: > Daniel Fischer <[hidden email]> wrote: > > Not to forget the marvellous > > > > import Control.Monad.Fix > > > > fibs :: [Integer] > > 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 But that's too easy to understand! What a waste of fix, sheesh ;-) My favourite is fibs = 0:1:zipWith (+) fibs (tail fibs) clear, elegant, accessible.  But I also like the other one, precisely because, unless one is very experienced, one has to do a few rounds of "Wait, how on earth does this work?" before it clicks. > > Replace 0 by 1, if you want to exclude it from the sequence.  I prefer > to include it. Yep. Much more natural if the powers match the index. > > > Greets, > Ertugrul. Cheers, Daniel
Open this post in threaded view
|

## Re: Understanding cached fibonnacci function

 In reply to this post by Ertugrul Söylemez >> 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...). Thanks, Patrick -- ===================== Patrick LeBoutillier Rosem?re, Qu?bec, Canada
Open this post in threaded view
|

## Re: Understanding cached fibonnacci function

 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