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 -----
From: Yue Wang
Date: Tue, 5 Oct 2010 21:23:57 -0400
To: Brent Yorgey
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?
