编程科学/现在让我们来点完全不同的东西
够了，不要再求导了！是时候尝试点新的了。新的，但并不完全不同。一旦你学习了微积分中的求导，你肯定会开始学习积分。正如早先所说，积分就是将曲线的所有微小（无穷小）部分加起来。所以如果dy表示曲线y的（无穷多个）微小部分之一，那么
事实上，如果你把一个事物的全部部分加起来，你就会得到这个事物本身。 [1]
与求导类似，积分也有两种，数值积分和符号积分。与求导一样，数值积分给出近似结果，而符号积分给出精确结果。由于数值积分涉及对许多小部分进行实际求和，让我们练习一下求和。
以下式子的和是多少：
其中有无穷多个分数遵循这种模式。在我们编写代码来给出答案之前，我们需要解决两个问题。第一个是，这个和似乎由两个不同的东西组成，一个整数 (1) 和一堆分数。
当所有事物都一样时，生活就容易多了；如果是这样，我们就不需要用if表达式来决定我们正在处理什么类型的事物。 [2] 一般来说，如果我们希望对两种不同的事物进行相同处理，我们需要要么使第一个看起来像第二个，要么使第二个看起来像第一个，或者使两者都看起来像第三种事物。在本例中，我们需要要么
- 使分数看起来像整数，
- 使整数看起来像分数，或者
- 使整数和分数看起来像第三种事物
在这三种策略中，第二种似乎是最简单的途径，因为可以通过在分母中放置一个 1 来轻松地将整数表示为分数
我们需要解决的最后一个问题是如何构建我们的代码。很明显，我们需要某种循环（递归或迭代），来添加尽可能多的分数。为了使用循环，我们通常需要使我们循环的项目看起来相同，或者至少是循环计数器的函数。在我们的例子中，我们如何使每个分数看起来相同？
如果我们看分母，我们会发现每个分母都可以描述为 2 的幂
似乎我们可以使用一个循环计数器（从零开始）作为每个分数分母中的指数。解决了这两个问题之后，我们可以开始编写一些代码。让我们首先尝试递归方法。
我们将使用n作为我们的循环计数器
function total(n)
{
1 / (2 ^ n) + total(n + 1);
}
如果我们用n的初始值为零调用total，我们应该得到
1 / (2 ^ 0) + total(1)
在下一个递归调用中，我们应该得到
1 / (2 ^ 0) + [1 / (2 ^ 1) + total(2)]
然后
1 / (2 ^ 0) + [1 / (2 ^ 1) + [1 / (2 ^ 2) + total(3)]]
这正是我们想要的，但最终我们将对无穷多个项求和。我们忽略了递归停止的基准情况。让我们将我们要加起来的项数作为max传递进去
function total(n,max)
{
if (n == max)
{
0;
}
else
{
1 / (2 ^ n) + total(n + 1,max);
}
}
当n达到max时，递归停止。
如果我们加起来五个分数，我们会得到什么？
sway> total(0,5); REAL_NUMBER: 1.9375000000
这是正确的吗？让我们显式地加起来五个分数
sway> 1.0 / 1 + (1.0 / 2) + (1.0 / 4) + (1.0 / 8) + (1.0 / 16); REAL_NUMBER: 1.9375000000
似乎是正确的。十个分数呢？
sway> total(0,10); REAL_NUMBER: 1.9980468750
五十个分数呢？
sway> total(0,50); REAL_NUMBER: 2.0000000000
一百个分数呢？
sway> total(0,100); REAL_NUMBER: 2.0000000000
这些结果让我们相信，如果我们将这些分数加到无穷大，总和将为 2。当然，由于我们的结果是实数，我们需要谨慎对待其绝对可靠性，但在这种情况下，我敢打赌结果是正确的。
我们可以在这个函数中添加一些可视化内容吗？我们可能应该先这样做，以确保我们的代码按预期执行
function total(n,max)
{
if (n == max)
{
println("0");
0;
}
else
{
var denom = 2 ^ n;
print("1/",integer(denom)," + ");
1 / denom + total(n + 1,max);
}
}
请注意，我们“预先计算”了分母，因为我们需要它两次，一次用于可视化，一次用于实际计算。我们还使用integer函数将指数产生的实数转换回整数。
sway>total(0,5); 1/1 + 1/2 + 1/4 + 1/8 + 1/16 + 0 REAL_NUMBER: 1.9375000000
看起来不错！当然，我们的可视化没有生成有效的 Sway 表达式（空格和优先级问题），但这对于可视化来说很少有必要。
让我们尝试使用迭代循环。将递归循环转换为迭代循环有一个标准方法。第一步是初始化一个局部变量，例如result，使其等于递归循环的基准情况返回值（然后返回它）。在本例中，返回值为零
function total(n,max)
{
var result = 0;
return result;
}
现在我们添加一个 while 循环，其中包含与递归循环if表达式中找到的测试相反的内容
function total(n,max)
{
var result = 0;
while (not(n == max)) //better is n != max)
{
}
return result;
}
在循环体中，我们放置递归情况计算
function total(n,max)
{
var result = 0;
while (n != max))
{
var denom = 2 ^ n;
1 / denom + total(n + 1,max);
}
return result;
}
用result替换递归调用
function total(n,max)
{
var result = 0;
while (n != max))
{
var denom = 2 ^ n;
1 / denom + result; //was total(n + 1,max)
}
}
并将整个表达式赋值回result
function total(n,max)
{
var result = 0;
while (n != max))
{
var denom = 2 ^ n;
result = 1 / denom + result; //was total(n + 1,max)
}
return result;
}
最后，如果在原始递归调用中更新了任何变量，请使用赋值在循环底部更新该变量
function total(n,max)
{
var result = 0;
while (n != max))
{
var denom = 2 ^ n;
result = 1 / denom + result;
n = n + 1;
}
return result;
}
瞧！我们完成了。这种技术通常效果很好，即使存在多个基准情况和多个递归情况，它也能正常工作。但是，有时转换会遇到一些问题。以下是一个例子；让我们转换最大公约数函数的递归版本
function gcd(n,d)
{
if (d == 0)
{
n;
}
else
{
gcd(d,n % d);
}
}
我们从基准情况返回值开始
function gcd(n,d)
{
var result = n;
return result;
}
接下来，我们添加一个 while 循环
function gcd(n,d)
{
var result = n;
while (d != 0)
{
}
return result;
}
然后我们复制递归情况计算
function gcd(n,d)
{
var result = n;
while (d != 0)
{
gcd(d,n % d);
}
return result;
}
我们在计算中用result替换递归调用
function gcd(n,d)
{
var result = n;
while (d != 0)
{
result; //was gcd(d,n % d);
}
return result;
}
现在我们更新在递归调用中发生更改的变量
function gcd(n,d)
{
var result = n;
while (d != 0)
{
result; //was gcd(d,n % d);
n = d;
d = n % d;
}
return result;
}
我们应该在此时完成，但我们仍然遇到几个问题。第一个问题是语句
result;
在 while 循环体中没有执行任何有用的操作。这是我们第一个发现问题所在的地方。现在，让我们删除它
function gcd(n,d)
{
var result = n;
while (d != 0)
{
n = d;
d = n % d;
}
return result;
}
第二个问题是，在递归调用中，对变量d的更新使用了n的旧值，但在我们的转换中，对d的更新使用了n的新值。我们需要保存旧值，并使用临时变量来做到这一点
function gcd(n,d)
{
var result = n;
while (d != 0)
{
var temp = n;
n = d;
d = temp % d;
}
return result;
}
最后一个问题是result从未改变。这是因为我们最初将result设置为n的原始值，而不是n的最后一个值。请注意，递归版本使用了n的最后一个值，如预期的那样。因此，我们在 while 循环终止后更新result，以获得n的最后一个值。
function gcd(n,d)
{
var result = n;
while (d != 0)
{
var temp = n;
n = d;
d = temp % d;
}
result = n;
return result;
}
当然，我们可以通过意识到result根本没有执行任何操作来稍微清理一下我们的函数；我们可以直接返回n的最后一个值
function gcd(n,d)
{
while (d != 0)
{
var temp = n;
n = d;
d = temp % d;
}
return n;
}
这种技术充其量能让你得到正确答案。最糟糕的是，它能让你接近正确答案。
请注意，在我们对原始求和的递归和迭代解决方案中，我们都硬编码了计算序列中下一个元素的函数（即反向求幂）。编写计算机程序的一个重要设计策略称为*关注点分离*。使用此策略，我们尝试编写函数或函数集，以便每个函数执行单个任务。在我们的解决方案中，下一个分数的生成（一个关注点）和这些分数的求和（另一个关注点）都在单个函数中找到，我们可以将这些关注点分离到单独的函数中。一个函数生成要求和的分数；另一个函数在给定先前生成的分数集合的情况下执行实际求和。因此，我们的第一个任务是生成分数集合。我们将研究两种收集集合的方法，*数组*和*列表*。
此时，您应该熟悉数组和列表。
以下是生成所需分数列表的代码
function invPowOfTwo(n,max)
{
if (n == max)
{
:null;
}
else
{
1 / (2 ^ n) join invPowOfTwo(n + 1,max);
}
}
如果我想要数组而不是列表，我可以将函数写成：[3]
function invPowOfTwo(n,max)
{
var a = allocate(max);
while (n < max)
{
a[n] = 1 / (2 ^ n);
n = n + 1;
}
a;
}
无论哪种方式，一旦我有了分数集合，我就可以使用通用求和器对其进行求和
function sum(items)
{
if (items == :null)
{
0;
}
else
{
head(items) + sum(tail(items);
}
}
无论我将数组还是列表传递给sum，我都会得到集合中所有项目的总和。 [4]
我也可以迭代地编写sum
include("basics");
function sum(items)
{
var i;
var total = 0;
for-each(i,items)
{
total = total + i;
}
total;
}
此版本也将对列表或数组形式的项目集合进行求和，但对于其中一种形式，该过程相当缓慢（参见练习）。
将元素生成与求和过程分离的优势在于：一旦我们有了元素列表，我们就可以做更多的事情，而不仅仅是求和。我们可以可视化它们、反转它们、（反转后）找到是梅森素数加 1 的那些等等。同样，我们可以使用我们的求和函数来对其他类型的集合进行求和。
伪无限序列
[edit | edit source]如果我们费尽心思生成了一组元素以某种方式进行求和或处理，却忽略了生成足够大的集合怎么办？我们被迫再次重新生成集合，丢弃之前完成的所有工作。
问题是我们必须在执行求和之前指定max
function invPowOfTwo(n,max)
{
if (n == max)
{
:null;
}
else
{
1 / (2 ^ n) join invPowOfTwo(n + 1,max);
}
}
如果我们不必预先指定集合的大小，那就太好了。不需要max 也会简化代码
function invPowOfTwo(n)
{
1 / (2 ^ n) join invPowOfTwo(n + 1);
}
问题是，如果没有基本情况，我们将陷入无限的递归循环。但是，我们可以通过*延迟*或*惰性求值*来避免这个陷阱。
此时，您应该熟悉惰性求值。
让我们编写一个invPowOfTwo版本，该版本延迟递归调用的求值
function invPowOfTwo(n)
{
1 / (2 ^ n) join delay(invPowOfTwo(n + 1));
}
请注意，我们使用了delay 函数包装递归调用。delay 所做的是保存计算递归调用所需的一切，而无需实际进行调用。实际调用可以在稍后使用delay 保存的信息进行。
让我们看一下调用新函数的结果
sway> var items = invPowOfTwo(0); LIST: (1.0000000000 # <THUNK 11167>)
我们看到列表的第一个元素是 1.0，正如预期的那样。但是，我们没有看到列表的其余部分，而是看到一个thunk 作为列表的尾部粘贴了（尖锐符号表示列表的尾部不是正确的列表）。我们可以检查thunk
sway> var t = tail(items);
THUNK: <THUNK 11167>
sway> pp(t);
<THUNK 11086>:
context: <OBJECT 11071>
code: invPowOfTwo(n + 1)
THUNK: <THUNK 11086>
我们看到 thunk 对象的code 字段保存了实际调用。context 字段保存了一个包含n 和invPowOfTwo 值的环境，这些是进行实际调用所需的一切。
这种列表被称为延迟流或简称为流。使用流的隐喻，因为只要有水源（内存），流就不会干涸。
我们如何从流中获得除第一个元素之外的其他元素？使用force 函数。force 函数在给定 thunk 作为参数时，会执行最初延迟的求值
sway> head(items);
REAL_NUMBER: 1.0000000000
sway> tail(items):
THUNK: <THUNK 11167>
sway> force(tail(items)); LIST: (0.5000000000 # <THUNK 11193>)
通过强制原始列表的尾部，我们最终得到一个由调用生成的新的列表invPowOfTwo(n + 1). 当此调用被延迟时，n 的值为零。现在此调用正在进行，invPowOfTwo 被传递了一个值为 1 的值。这将生成一个新的列表，其头部为，另一个延迟的递归调用。这次，delay 会记住n 的值为 1 而不是 0。
让我们定义一个函数来获取流中的任何元素。我们将传入索引，然后连续强制列表的尾部，直到我们到达正确的元素
function streamIndex(s,i)
{
if (index == 0) // the head of the stream is desired
{
head(s);
}
else
{
streamIndex(force(tail(s)),i - 1);
}
}
请注意，如果我们想要具有超过i 个元素的列表的第i 个元素，则这与想要列表尾部的第i - 1 个元素相同。当我们取列表的尾部时，所需的元素似乎向列表的前面移动了一步。 [5]
现在我们可以对流进行求和
function sumStream(s,count)
{
if (count == 0)
{
0;
}
else
{
head(s) + sumStream(force(tail(s)),count - 1);
}
}
无需担心最初生成了多少个元素。迭代地，对流求和可能看起来像
function sumStream(s,count)
{
var total = 0;
while (count > 0)
{
total = total + head(s);
s = force(tail(s));
count = count + 1;
}
total;
}
问题
[edit | edit source]脚注
[edit | edit source]- ↑ 假设你不相信那个神奇的营销术语*协同效应*。
- ↑ 我们之前在将常数看起来像一个项时看到了这一点。
- ↑ 列表适合递归解决方案，数组适合迭代解决方案。
- ↑ 不要在其他语言中尝试！在几乎所有其他语言中，用于分解列表的操作符/函数与分解数组的操作符/函数不同。
- ↑ 这一点非常重要。说服自己确实如此。