程式設計科學/現在讓我們來點完全不同的東西
夠了，不要再求導了！是時候嘗試點新的了。新的，但並不完全不同。一旦你學習了微積分中的求導，你肯定會開始學習積分。正如早先所說，積分就是將曲線的所有微小（無窮小）部分加起來。所以如果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]- ↑ 假設你不相信那個神奇的營銷術語*協同效應*。
- ↑ 我們之前在將常數看起來像一個項時看到了這一點。
- ↑ 列表適合遞迴解決方案，陣列適合迭代解決方案。
- ↑ 不要在其他語言中嘗試！在幾乎所有其他語言中，用於分解列表的運算子/函式與分解陣列的運算子/函式不同。
- ↑ 這一點非常重要。說服自己確實如此。