[Haskell-cafe] Eta-expansion destroys memoization?

[Brent Yorgey]

Hi all,

See below for this message from one of my students which has me
stumped.  Just when you think you understand Haskell... ;)

I've cc'ed him on this message; please include him on any replies as I
don't think he is subscribed to -cafe.

-Brent

----- Forwarded message from Yue Wang <yulewang at gmail.com> -----

From: Yue Wang <yulewang at gmail.com>
Date: Tue, 5 Oct 2010 21:23:57 -0400
To: Brent Yorgey <byorgey at seas.upenn.edu>
Subject: store evaluated values

Hi, Anthony (or Brent):

Last time (in Anthony's TA office hour) we talked about how to store evaluated values in the program for later used. 
I googled for a while and wrote some code. But I still encountered two problems. Can you take a look? Thanks.

First, let's write the naive fib function:

naive_fib 0 = 0
naive_fib 1 = 1
naive_fib n = trace(show(n))
              naive_fib (n - 1) + naive_fib (n - 2)

this works good except it tries to calculate the same expression many times. So when we evaluate it ghci will show the following:
*Main> naive_fib 5
5
4
3
2
2
3
2
5

Then there is a clever way to do that on haskell wiki:

fib = ((map fib' [0 ..]) !!)
    where
      fib' 0 = 0
      fib' 1 = 1
      fib' n =trace(show(n)) fib (n - 1) + fib (n - 2)

When we evaluate the same expression we can see it does not evaluate the redundant expression over and over:
*Main> fib 5
5
4
3
2
5

The source code seems to be easy to read, but I don't think I understand that. For me I think if I change the first line from 
fib = ((map fib' [0 ..]) !!)
to
fib x = ((map fib' [0 ..]) !!) x
It should do the same thing since I think the previous version is just an abbreviation  for the second one. But After I change that, 
*Main> fib 5
5
4
3
2
2
3
2
5

So why does the x here matters?