[Haskell-beginners] Re: Understanding cached fibonnacci function

[Ertugrul Soeylemez]

Thomas Davie <tom.davie at gmail.com> 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/