Understanding cached fibonnacci function

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Understanding cached fibonnacci function

Patrick LeBoutillier-2
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
Reply | Threaded
Open this post in threaded view
|

Understanding cached fibonnacci function

Thomas Davie

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

Reply | Threaded
Open this post in threaded view
|

Understanding cached fibonnacci function

Daniel Fischer-4
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

Reply | Threaded
Open this post in threaded view
|

Re: Understanding cached fibonnacci function

Ertugrul Söylemez
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/


Reply | Threaded
Open this post in threaded view
|

Re: Understanding cached fibonnacci function

Daniel Fischer-4
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
Reply | Threaded
Open this post in threaded view
|

Re: Understanding cached fibonnacci function

Patrick LeBoutillier-2
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
Reply | Threaded
Open this post in threaded view
|

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
Reply | Threaded
Open this post in threaded view
|

Re: Understanding cached fibonnacci function

Heinrich Apfelmus
In reply to this post by Patrick LeBoutillier-2
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

Reply | Threaded
Open this post in threaded view
|

Re: Understanding cached fibonnacci function

Ertugrul Söylemez
In reply to this post by Thomas Davie
Thomas Davie <[hidden email]> wrote:

> >> 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!

Beware that 'fix' doesn't simply return an arbitrary fixed point.  It
gives you _the_ least-defined fixed point, which is bottom for 'fix id'.
By the way, it's a very aggressive implementation of bottom.  Trying to
evaluate 'fix id' may crash your system, unless you set proper memory
limits.


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

It does have a fixed point.  Every function has a fixed point.  Its
fixed point is 1+1+1+1+...  It's easy to verify:

  (+1) (1+1+1+1+...) = 1+1+1+1+...

However, the fixed point has the least possible definedness, which means
it's bottom.


> 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.

Same story here, but (1:) is not strict in its argument, so you get
higher definedness than bottom.


> 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.

I find it easier to explain in terms of typed lambda calculus.  The
problem with it is that you can't express recursion directly in raw
lambda notation.  The fixed point operator 'fix' gives you the power to
do this:

  fix f = f (fix f)

If you pass a lambda to 'fix', then it results in a function, which gets
itself as its first argument, so you can express recursion.  Say, you
would like to write the greatest common divisor algorithm, which is:

  gcd x 0 = x
  gcd x y = gcd y (x `mod` y)

Now in raw lambda calculus, you can't write equations like above.  You
can only express functions in terms of their lambdas:

  (\x y -> if y == 0 then x else ...)

The problem should be clear:  There is no way for the function to call
itself.  Now the fixed point operator comes into play.  It turns the
first argument of the function into a recursive reference to itself:

  fix (\recurse x y -> if y == 0 then x else recurse y (x `mod` y))

Of course, with all the expressive power you've got in Haskell, it's
never necessary and seldomly useful to use the fixed point operator.
You would write the GCD function just in the usual style.  But
sometimes, particularly for infinite unfolds, it's more convenient than
'unfoldr' or 'iterate', without making code incomprehensible.


Greets,
Ertugrul.


--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/