Trying to understand “let” in scheme

Question

I'm trying to expand a simple fibonacci function, and I need to use the values for each term more than once. So, I figured I'd use let to hold onto the values. But, I'm not getting what I think I should out of the function.

Here is the original fib function:

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

Here is my attempt at doing the same thing, but with let:

(define (fib-with-let n)
  (if (< n 2)
      0
      (let ((f1 (fib-with-let (- n 1)))
            (f2 (fib-with-let (- n 2))))
        (+ f1 f2))))

Results:

> (fib 10)
55
> (fib-with-let 10)
0

Thanks!

Answer 1

You made a typo:

(if (< n 2)
    0
    ...)

You mean n.

Answer 2

You mistyped your base case. In the first version you had:

(if (< n 2)
      n

But then in your latter version you wrote:

(if (< n 2)
      0

So just change 0 to n.

Answer 3

Your let is not really doing anything. You are still doing all of the extra calculations. Just because you define f1 as (fib-with-let (- n 1)) doesn't mean you won't compute the fib of n-1 again. f2 does not use f1. If you wanted f2 to see f1 you would use let*. However, even this is not really what you want.

As evidence of this, here are the running times for fib(35) and fib-with-let(35):

(time (fib 35))
cpu time: 6824 real time: 6880 gc time: 0
(time (fib-with-let 35))
cpu time: 6779 real time: 6862 gc time: 0

What you really want to do to avoid extra computations is use dynamic programming and recurse in a bottom-up fashion.

What you want is the following code:

(define (dynprog-fib n)
  (if (< n 2)
      n
      (dynprog-fib-helper 1 1 2 n)))

(define (dynprog-fib-helper n1 n2 current target)
  (if (= current target)
      n2
      (dynprog-fib-helper n2 (+ n1 n2) (add1 current) target)))

(time (dynprog-fib 35))
cpu time: 0 real time: 0 gc time: 0
(time (dynprog-fib 150000))
cpu time: 2336 real time: 2471 gc time: 644

As you can see, you can do the first 150,000 fibs in a third of the time the naive approach takes.

---

Since it looks like you are confused about what let does let me illustrate better:

When you say:

(let ((a 1)
      (b 2))
  (+ a b))

What you are saying is, let a be 1, and b be 2, add them together. If you instead said:

(let ((a 1)
      (b (+ a 1))
  (+ a b))

Can you guess what you'd get? Not 3. It would be blow up with expand: unbound identifier in module in: a

In simple let, your assignments cannot see each other. If you wanted to write the above you would have to use let*:

(let* ((a 1)
      (b (+ a 1))
  (+ a b))

That would give you the 3 you expect. let* essentially expands to:

(let ((a 1))
     (let ((b (+ a 1)))
          (+ a b)))

---

What you thought you were doing with the lets is called memoization. It's a technique where you store intermediate values so you don't have to repeat them. Let, however, does not do that for you.

Answer 4

Although your problem is a typo in your fib-with-let function, in its simplest form, let is "syntatic-sugar" for an anonymous lambda followed by the arguments that are then evaluated and passed to the lamba, which is then evaluated and a final value returned. So

(let ((f1 (fib-with-let (- n 1)))
      (f2 (fib-with-let (- n 2))))
        (+ f1 f2))

would be re-written without let to look like

((lambda (f1 f2) (+ f1 f2))(fib-with-let (- n 1))(fib-with-let (- n 2)))