试图理解“让”计划中

Question

我正在尝试扩展一个简单的斐波那契函数，并且需要多次使用每个项的值。所以，我想我应该使用 let 来保留这些值。但是，我没有从该函数中得到我认为应该得到的东西。

这是原始的 fib 函数：

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

这是我尝试做同样的事情，但使用 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))))

结果：

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

谢谢！

Answer 1

您打错了：

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

您的意思是n。

Answer 2

您输入的基本情况错误。在第一个版本中，您有：

(if (< n 2)
      n

但在后一个版本中，您写道：

(if (< n 2)
      0

所以只需将 0 更改为 n 即可。

Answer 3

你的 let 并没有真正做任何事情。您仍在进行所有额外的计算。仅仅因为您将 f1 定义为 (fib-with-let (- n 1)) 并不意味着您不会再次计算 n-1 的 fib。 f2 不使用f1。如果您希望 f2 看到 f1，您可以使用 let*。然而，即使这也不是您真正想要的。

作为这一点的证据，以下是 fib(35) 和 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

为了避免额外的计算，您真正想要做的是使用动态编程并在自下而上的时尚。

您想要的是以下代码：

(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

正如您所看到的，您可以用朴素方法所需时间的三分之一来完成前 150,000 个小纤维。

---

因为看起来你对 let 的内容感到困惑，让我更好地说明一下：

当你说：

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

你所说的是，让 a 为 1，b 为 2，将它们加在一起。
如果你说：

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

你能猜一下你会得到什么吗？不是 3. 它会被 expand: unbound identifier in module in: a 炸毁。

在简单的 let 中，您的分配不能彼此看到。
如果你想写上面的内容，你必须使用 let*：

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

这会给你你期望的 3 。 let* 本质上扩展为：

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

---

你认为你用 let 所做的事情被称为记忆化。这是一种存储中间值的技术，因此您不必重复它们。然而，Let 不会为你做到这一点。

Answer 4

虽然您的问题是 fib-with-let 函数中的拼写错误，但在最简单的形式中，let 是匿名 lambda 的“syntatic-sugar”，后跟参数然后评估并传递给lambda，然后评估并返回最终值。所以

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

会在没有 let 的情况下重写，看起来像

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