Using fix to generate Fibonacci numbers recursively - how does this example work?-CodePudding

Good morning everyone!

Stackoverflow, being the rabbithole that it is, lead me to fix (the one that's contained in Data.Fuction), and since I'm already in the process of going through some of the more common Haskell libraries, and since fix seems to be a study subject all of it's own, I started reading up on it, first on Haskell Wiki (https://en.m.wikibooks.org/wiki/Haskell/Fix_and_recursion) and then on this post (https://www.vex.net/~trebla/haskell/fix.xhtml), suggested by comments on a relevant thread.

In the latter, the writer presents four recursion examples and then goes through a couple of iterations to transform them in a form that's suitable for use with fix. I understand the thought process and I understand the final result. I also come to the conclusion, that the first two functions (zeroes and fibs) are examples of divergent computations, since they don't terminate, while the other two (factorial and mapeven) converge to a certain fixed point.

What really trips me up is the way the second function works, fibs.

It's pretty clear to me how zeroes works, since fix f = let x = f x in x. So, ghci, knowing it has to compute 0:x, will display 0 and then try to work out what x is, which turn out to be, again, 0:x, so it will display that 0 and then again try to compute what x is, ad infinitum. In other words, it goes from 0:x to 0:(0:x) to 0:(0:(0:x)) etc, chasing it's own tail.

In the case of fibs, recursion seems to work kind of backwards. The function is 0:scanl ( ) 1 x, which is actually 0:scanl ( ) 1 (0:scanl ( ) 1 x). So what should ghci do? First of all, display 0, since that's a given, and then work out what the result of scanl is. Well, for the first element that's easy, it should be the accumulator, or 1, already provided for scanl. But then it should really work out what x actually is, in order to continue the computation, and x is 0:scanl ( ) 1 x, which is of course a list starting with 0, so the first scanl will add it's acc of 1 with 0 and give 1 as the third element of the computation, then add that 1 with the acc of the nested scanl function, again 1, so, 2 becomes the fourth element of that chain of computations. But then the second scanl should really work out what x is, and that again turns out to be 0:scanl ( ) 1 x, so shouldn't the fifth element of that list be again 2, which is the accumulator value of the second scanl function, plus 0, as the first element of the newly evaluated x? How is it exactly that this computation goes on to output fibonacci numbers?. It seems to me like it should hang there forever (like, say fix id), because it should compute what x is in the first place.

If anyone can make heads or tails of this one (every pun intended), and explain it in a way that makes sense for the rest of us, I would very much aprreciate it.

Thanks!

CodePudding user response：

A good way to make sense of how Haskell programs are evaluated is rewriting. Haskell programs consist of equations, and those are used to unfold a main expression and enable further simplifications. The relevant equations here come from the definitions of fix and scanl.

x = 0 : scanl ( ) 1 x

scanl ( ) n (y : ys) = n : scanl ( ) (n   y) ys

We want to evaluate x. Start by unfolding x

x = 0 : scanl ( ) 1 x                           -- (1)
  = 0 : scanl ( ) 1 (0 : scanl ( ) 1 x)

This lets us use the scanl equation with y = 0 and ys = scanl ( ) 1 x.

x = 0 : 1 : scanl ( ) (1   0) (scanl ( ) 1 x)
  = 0 : 1 : scanl ( ) 1 (scanl ( ) 1 x)         -- (2)

Next we need to unfold scanl ( ) 1 x, and if we look above, we already did that work, deducing the following equation from those marked (1) and (2)

scanl ( ) 1 x = 1 : scanl ( ) 1 (scanl ( ) 1 x)

which lets us not repeat the work to unfold that latest occurrence of scanl ( ) 1 x.

x = 0 : 1 : scanl ( ) 1 (1 : scanl ( ) 1 (scanl ( ) 1 x)))

Unfold scanl:

x = 0 : 1 : 1 : scanl ( ) (1   1) (scanl ( ) 1 (scanl ( ) 1 x))
  = 0 : 1 : 1 : scanl ( ) 2 (scanl ( ) 1 (scanl ( ) 1 x))         -- (3)

Again, we want to unfold scanl ( ) 1 (scanl ( ) 1 x), which we've already seen before (in (2)), and the result can be read in that last equation (3).

x = 0 : 1 : 1 : scanl ( ) 2 (1 : scanl ( ) 2 (scanl ( ) 1 (scanl ( ) 1 x)))
  = 0 : 1 : 1 : 2 : scanl ( ) 3 (scanl ( ) 2 (scanl ( ) 1 (scanl ( ) 1)))

And now we can see the accumulator 3 appear.

I tried to be smart and avoid doing work that was already done in some form. A more systematic method is to associate a variable to every new expression. In fact, this is quite close to how lazy evaluation is implemented in GHC: every variable is a memory location containing either an unevaluated expression, or a constructor applied to variables.

x = 0 : scanl ( ) 1 x

Name the tail of the list.

x = 0 : x1
x1 = scanl ( ) 1 x

Substitute and simplify

x1 = scanl ( ) 1 (0 : x1)
   = 0 : scanl ( ) 1 x1

Name the tail of the list

x1 = 0 : x2
x2 = scanl ( ) 1 x1

etc.

x2 = scanl ( ) 1 (0 : x2)
   = 1 : scanl ( ) 1 x2
   = 1 : x3
x3 = scanl ( ) 1 x2
   = scanl ( ) 1 (1 : x3)
   = 1 : scanl ( ) 2 x3
   = 1 : x4
x4 = 2 : x5
x5 = 3 : x6
x6 = 5 : x7
x7 = ...