第十章 Haskell函數(shù)式解決問題

函數(shù)式地思考來解決問題

在這一章中，我們會(huì)查看幾個(gè)有趣的問題，并嘗試用函數(shù)式的方式來漂亮地解決他們。我們并不會(huì)介紹新的概念，我們只是練習(xí)我們剛學(xué)到的寫程序的技巧。每一節(jié)都會(huì)探討不同的問題。會(huì)先描述問題，然后用最好的方式解決他。

運(yùn)算逆波蘭表示法(Reverse Polish notation form)

我們?cè)趯W(xué)校學(xué)習(xí)數(shù)學(xué)的時(shí)候，我們多半都是用中置(infix)的方式來寫數(shù)學(xué)式。例如說，我們會(huì)寫 10 - (4 + 3) * 2。+, *, - 是中置運(yùn)算子(infix operators)。在 Haskell 中就像是 + 或 elem 一樣。這種寫法對(duì)于人類來說很容易閱讀與理解，但缺點(diǎn)是我們必須用括號(hào)來描述運(yùn)算的優(yōu)先級(jí)。

逆波蘭表示法是另外一種數(shù)學(xué)式的描述方法。乍看之下顯得怪異，但他其實(shí)很容易理解并使用。因?yàn)槲覀儾恍枰ɑ砻枋觯埠苋菀追胚M(jìn)計(jì)算機(jī)里面運(yùn)算。盡管現(xiàn)在的計(jì)算機(jī)都是用中置的方式讓你輸入，有些人仍堅(jiān)持用 RPN 的計(jì)算機(jī)。前述的算式如果表達(dá)成 RPN 的話會(huì)是 10 4 3 + 2 * -。我們要如何計(jì)算他的結(jié)果呢？可以想想堆疊，基本上你是從左向右閱讀算式。每當(dāng)碰到一個(gè)數(shù)值，就把他堆上堆疊。當(dāng)我們碰到一個(gè)運(yùn)算子。就把兩個(gè)數(shù)值從堆疊上拿下來，用運(yùn)算子運(yùn)算兩個(gè)數(shù)值然后把結(jié)果推回堆疊中。當(dāng)你消耗完整個(gè)算式的時(shí)候，而且假設(shè)你的算式是合法的，那你就應(yīng)該只剩一個(gè)數(shù)值在堆疊中，

我們?cè)俳又?nbsp;10 4 3 + 2 * -。首先我們把 10 推到堆疊上，所以堆疊現(xiàn)在是 10。下一個(gè)接著的輸入是 4，我們也把他推上堆疊。堆疊的狀態(tài)便變成 10, 4。接著也對(duì)下一個(gè)輸入 3 做同樣的事，所以堆疊變成 10, 4, 3。然后便碰到了第一個(gè)運(yùn)算子 +。我們把堆疊最上層的兩個(gè)數(shù)值取下來（所以堆疊變成 10）把兩個(gè)數(shù)值加起來然后推回堆疊上。堆疊的狀態(tài)便變成 10, 7。我們?cè)侔演斎?nbsp;2 推上堆疊，堆疊變成 10, 7, 2。我們又碰到另一個(gè)運(yùn)算子，所以把 7 跟 2 取下，把他們相乘起來然后推回堆疊上。7 跟 2 相乘的結(jié)果是 14，所以堆疊的狀態(tài)是 10, 14。最后我們碰到了 -。我們把 10 跟 14 取下，將他們相減然后推回堆疊上。所以現(xiàn)在堆疊的狀態(tài)變成 -4。而我們已經(jīng)把所有數(shù)值跟運(yùn)算子的消耗完了，所以 -4 便是我們的結(jié)果。

現(xiàn)在我們知道我們?nèi)绾问炙?RPN 運(yùn)算式了，接下來可以思考一下我們寫一個(gè) Haskell 的函數(shù)，當(dāng)他接到一個(gè) RPN 運(yùn)算式，像是 "10 4 3 + 2 * -" 時(shí)，他可以給出結(jié)果。

這個(gè)函數(shù)的型別會(huì)是什么樣呢？我們希望他接受一個(gè)字串當(dāng)作參數(shù)，并產(chǎn)出一個(gè)數(shù)值作為結(jié)果。所以應(yīng)該會(huì)是 solveRPN :: (Num a) => String -> a。

小建議：在你去實(shí)作函數(shù)之前，先想一下你會(huì)怎么宣告這個(gè)函數(shù)的型別能夠幫助你厘清問題。在 Haskell 中由于我們有夠強(qiáng)的型別系統(tǒng)，光從函數(shù)的宣告就可以得到許多信息。

當(dāng)我們要實(shí)作一個(gè)問題的解法時(shí)，你可以先動(dòng)手一步一步解看看，嘗試從里面得到一些靈感。我們這邊把每一個(gè)用空白隔開的數(shù)值或運(yùn)算子都當(dāng)作獨(dú)立的一項(xiàng)。所以把 "10 4 3 + 2 * -" 這樣一個(gè)字串?dāng)喑梢淮?list ["10","4","3","+","2","*","-"] 應(yīng)該會(huì)有幫助。

接下來我們要如何應(yīng)用這個(gè)斷好的 list 呢？我們從左至右來走一遍，并保存一個(gè)工作用的堆疊。這樣有讓你想到些什么可以用的嗎？沒錯(cuò)，在 folds 的那一章里面，我們提到基本上當(dāng)你需要從左至右或由右至左走過一遍 list 的時(shí)候并產(chǎn)生些結(jié)果的時(shí)候。我們都能用 fold 來實(shí)作他。

在這個(gè) case 中由于我們是從左邊走到右邊，所以我們采取 left fold。accumulator 則是選用堆疊，而 fold 的結(jié)果也會(huì)是一個(gè)堆疊，只是里面只有一個(gè)元素而已。

另外要多考慮一件事是我們用什么來代表我們的堆疊？我們可以用 list 來代替，list 的 head 就可以當(dāng)作是堆疊的頂端。畢竟要把一個(gè)元素加到 list 的 head 要比加到最后要有效率多。所以如果我們有一個(gè)堆疊，里面有 10, 4, 3，那我們可以用 [3,4,10] 來代表他。

現(xiàn)在我們有了足夠的信息來寫出我們的函數(shù)。他會(huì)接受一個(gè)字串 "10 4 3 + 2 * -"，隨即用 words 來斷成 list ["10","4","3","+","2","*","-"]。接下來我們做一個(gè) left fold 來產(chǎn)生出只有一個(gè)元素的堆疊，也就是 [-4]。我們把這個(gè)元素從 list 取出便是最后的結(jié)果。

來看看我們的實(shí)作：

import Data.List  
  
solveRPN :: (Num a) => String -> a  
solveRPN expression = head (foldl foldingFunction [] (words expression))  
    where   foldingFunction stack item = ...  

我們接受一個(gè)運(yùn)算式并把他斷成一串 List。然后我們用一個(gè) folding 函數(shù)來 fold 這串 list。注意到我們用 [] 來當(dāng)作起始的 accumulator。這個(gè) accumulator 就是我們的堆疊，所以 [] 代表一個(gè)空的堆疊。在運(yùn)算之后我們得到一個(gè)只有一個(gè)元素的堆疊，我們調(diào)用 head 來取出他并用 read 來轉(zhuǎn)換他。

所以我們現(xiàn)在只缺一個(gè)接受堆疊的 folding 函數(shù)，像是可以接受 [4,10] 跟 "3"，然后得到 [3,4,10]。如果是 [4,10] 跟 "*"，那就會(huì)得到 [40]。但在實(shí)作之前，我們先把我們的函數(shù)改寫成 point-free style，這樣可以省下許多括號(hào)。

import Data.List  
  
solveRPN :: (Num a) => String -> a  
solveRPN = head . foldl foldingFunction [] . words  
      where   foldingFunction stack item = ...  

看起來好多了。我們的 folding 函數(shù)會(huì)接受一個(gè)堆疊、新的項(xiàng)，并回傳一個(gè)新的堆疊。我們使用模式匹配的方式來取出堆疊最上層的元素，然后對(duì) "*" 跟 "-" 做匹配。

solveRPN :: (Num a, Read a) => String -> a  
solveRPN = head . foldl foldingFunction [] . words  
    where   foldingFunction (x:y:ys) "*" = (x * y):ys  
            foldingFunction (x:y:ys) "+" = (x + y):ys  
            foldingFunction (x:y:ys) "-" = (y - x):ys  
            foldingFunction xs numberString = read numberString:xs  

我們用展開成四個(gè)模式匹配。模式會(huì)從第一個(gè)開始嘗試匹配。所以 folding 函數(shù)會(huì)看看目前的項(xiàng)是否是 "*"。如果是，那就會(huì)將 [3,4,9,3] 的頭兩個(gè)元素綁定到 x，y 兩個(gè)名稱。所以 x 會(huì)是 3 而 y 等于 4。ys 便會(huì)是 [9,3]。他會(huì)回傳一個(gè) list，只差在 x 跟 y 相乘的結(jié)果為第一個(gè)元素。也就是說會(huì)把最上層兩個(gè)元素取出，相乘后再放回去。如果第一個(gè)元素不是 "*"，那模式匹配就會(huì)比對(duì)到 "+"，以此類推。

如果項(xiàng)并未匹配到任何一個(gè)運(yùn)算子，那我們就會(huì)假設(shè)這個(gè)字串是一個(gè)數(shù)值。如果他是一個(gè)數(shù)值，我們會(huì)用 read 來把字串轉(zhuǎn)換成數(shù)值。并把這個(gè)數(shù)值推到堆疊上。

另外注意到我們加了 Read a 這像 class constraint，畢竟我們要使用到 read 來轉(zhuǎn)換成數(shù)值。所以我們必須要宣告成他要屬于 Num 跟 Read 兩種 typeclass。（譬如說 Int,Float 等）

我們是從左至右走過 ["2","3","+"]。一開始堆疊的狀態(tài)是 []。首先他會(huì)用 [] 跟 "2" 來喂給 folding 函數(shù)。由于此項(xiàng)并不是一個(gè)運(yùn)算子。他會(huì)用 read 讀取后加到 [] 的開頭。所以堆疊的狀態(tài)變成 [2]。接下來就是用 [2] 跟 ["3"] 來喂給 folding 函數(shù)，而得到 [3,2]。最后再用 [3,2] 跟 "+" 來調(diào)用 folding 函數(shù)。這會(huì)堆疊頂端的兩個(gè)數(shù)值，加起來后推回堆疊。最后堆疊變成 [5]，這就是我們回傳的數(shù)值。

我們來試試看我們新寫的函數(shù)：

ghci> solveRPN "10 4 3 + 2 * -"  
-4  
ghci> solveRPN "2 3 +"  
5  
ghci> solveRPN "90 34 12 33 55 66 + * - +"  
-3947  
ghci> solveRPN "90 34 12 33 55 66 + * - + -"  
4037  
ghci> solveRPN "90 34 12 33 55 66 + * - + -"  
4037  
ghci> solveRPN "90 3 -"  
87  

看起來運(yùn)作良好。這個(gè)函數(shù)有一個(gè)特色就是他很容易改寫來支持額外的運(yùn)算子。他們也不一定要是二元運(yùn)算子。例如說我們可以寫一個(gè)運(yùn)算子叫做 "log"，他會(huì)從堆疊取出一個(gè)數(shù)值算出他的 log 后推回堆疊。我們也可以用三元運(yùn)算子來從堆疊取出三個(gè)數(shù)值，并把結(jié)果放回堆疊。甚至是像是 "sum" 這樣的運(yùn)算子，取出所有數(shù)值并把他們的和推回堆疊。

我們來改寫一下我們的函數(shù)讓他多支持幾個(gè)運(yùn)算子。為了簡單起見，我們改寫宣告讓他回傳 Float 型別。

import Data.List  
  
solveRPN :: String -> Float  
solveRPN = head . foldl foldingFunction [] . words  
where   foldingFunction (x:y:ys) "*" = (x * y):ys  
        foldingFunction (x:y:ys) "+" = (x + y):ys  
        foldingFunction (x:y:ys) "-" = (y - x):ys  
        foldingFunction (x:y:ys) "/" = (y / x):ys  
        foldingFunction (x:y:ys) "^" = (y ** x):ys  
        foldingFunction (x:xs) "ln" = log x:xs  
        foldingFunction xs "sum" = [sum xs]  
        foldingFunction xs numberString = read numberString:xs  

看起來不錯(cuò)，沒有疑問地 / 是除法而 ** 是取 exponential。至于 log 運(yùn)算子，我們只需要模式匹配一個(gè)元素，畢竟 log 只需要一個(gè)元素。而 sum 運(yùn)算子，我們只回傳一個(gè)僅有一個(gè)元素的堆疊，包含了所有元素的和。

ghci> solveRPN "2.7 ln"  
0.9932518  
ghci> solveRPN "10 10 10 10 sum 4 /"  
10.0  
ghci> solveRPN "10 10 10 10 10 sum 4 /"  
12.5  
ghci> solveRPN "10 2 ^"  
100.0  

由于 read 知道如何轉(zhuǎn)換浮點(diǎn)數(shù)，我們也可在運(yùn)算適中使用他。

ghci> solveRPN "43.2425 0.5 ^"  
6.575903  

有這樣一個(gè)容易拓展到浮點(diǎn)數(shù)而且動(dòng)到的代碼又在十行以內(nèi)的函數(shù)，我想是非常棒的。

有一件事要留意的是這個(gè)函數(shù)對(duì)于錯(cuò)誤處理并不好。當(dāng)我們碰到非法輸入的時(shí)候，他就會(huì)直接當(dāng)?shù)?。之后我們碰?Monad 的時(shí)候我們會(huì)寫一個(gè)容錯(cuò)的版本，他的型別會(huì)是 solveRPN :: String -> Maybe Float。當(dāng)然我們現(xiàn)在也可以寫一個(gè)，不過那會(huì)有點(diǎn)麻煩，因?yàn)闀?huì)有一大堆檢查 Nothing 的動(dòng)作。如果你希望挑戰(zhàn)的話，也可以盡管嘗試。（提示：你可以用 reads 來看看一次 read 是否會(huì)成功）

路徑規(guī)劃

我們接下來的問題是：你的飛機(jī)剛剛降落在英格蘭的希思羅機(jī)場(chǎng)。你接下來有一個(gè)會(huì)議，你租了一臺(tái)車希望盡速從機(jī)場(chǎng)前往倫敦市中心。

從希思羅機(jī)場(chǎng)到倫敦有兩條主要道路，他們中間有很多小路連接彼此。如果你要走小路的話都會(huì)花掉一定的時(shí)間。你的問題就是要選一條最佳路徑讓你可以盡快前往倫敦。你從圖的最左邊出發(fā)，中間可能穿越小路來前往右邊。

你可以從圖中看到，從希思羅機(jī)場(chǎng)到倫敦在這個(gè)路徑配置下的最短路徑是先選主要道路 B，經(jīng)由小路到 A 之后，再走一小段，轉(zhuǎn)到 B 之后繼續(xù)往前走。如果采取這個(gè)路徑的話，會(huì)花去 75 分鐘。如果選其他道路的話，就會(huì)花更多時(shí)間。

我們?nèi)蝿?wù)就是要寫一個(gè)程序，他接受道路配置的輸入，然后印出對(duì)應(yīng)的最短路徑。我們的輸入看起來像是這樣：

50  
10  
30  
5  
90  
20  
40  
2  
25  
10  
8  
0  

我們?cè)谛闹锌梢园演斎氲臄?shù)值三個(gè)三個(gè)看作一組。每一組由道路 A,道路 B,還有交叉的小路組成。而要能夠這樣組成，我們必須讓最后有一條虛擬的交叉小路，只需要走 0 分鐘就可以穿越他。因?yàn)槲覀儾⒉粫?huì)在意在倫敦里面開車的成本，畢竟我們已經(jīng)到達(dá)倫敦了。

正如我們?cè)诮?RPN 計(jì)算機(jī)的問題的時(shí)候，我們是用三步驟來解題：

• 首先忘掉 Haskell，想想我們自己是怎么一步步解題的。
• 想想如何在 Haskell 中表達(dá)我們的數(shù)據(jù)。
• 在 Haskell 中要如何對(duì)這些數(shù)據(jù)做運(yùn)算來產(chǎn)生出解答。

在介紹 RPN 計(jì)算機(jī)的章節(jié)中，我們首先自己用人腦計(jì)算表達(dá)式，在心中維持一個(gè)堆疊然后一項(xiàng)一項(xiàng)處理。我們決定用一個(gè)字串來表達(dá)我們的表達(dá)式。最后，我們用 left fold 來走過我們這一串 list，并算出結(jié)果。

究竟我們要怎么用手算出從希思羅機(jī)場(chǎng)到倫敦的最短路徑呢？我們可以觀察整章圖片，猜測(cè)哪一條是最短路徑然后希望我們有猜對(duì)。這樣的作法對(duì)于很小的輸入可以成功，但如果我們的路徑超過 10000 組呢？這樣我們不知道我們的解法是不是最佳解，我們只能說可能是。

所以那并不是一個(gè)好作法。這邊有一張簡化過后的圖。

你能想出來到道路 A 上第一個(gè)交叉點(diǎn)的最短路徑嗎？（標(biāo)記成 A1 的點(diǎn)）這太容易了。我們只要看看從道路 A 出發(fā)或是從道路 B 出發(fā)穿越至道路 A 兩種作法哪種比較短就好。很明顯的，從道路 B 出發(fā)的比較短，只要花費(fèi) 40 分鐘，然而從道路 A 則要花費(fèi) 50 分鐘。那到交叉點(diǎn) B1 呢？同樣的作法可以看出從道路 B 出發(fā)只要花費(fèi) 10 分鐘，遠(yuǎn)比從道路 A 出發(fā)然后穿越小路要花費(fèi)少，后者要花費(fèi) 80 分鐘！

現(xiàn)在我們知道要到達(dá) A1 的最短路徑是經(jīng)由 B 然后鄒小路到達(dá)，共花費(fèi) 40。而我們知道要達(dá)到 B1 的最短路徑則是直接走 B，花費(fèi) 10。這樣的知識(shí)有辦法幫助我們得知到下一個(gè)交叉點(diǎn)的最短路徑嗎？可以的。

我們來看看到達(dá) A2 的最短路徑是什么。要到達(dá) A2，我們必須要從 A1 走到 A2 或是從 B1 走小路。由于我們知道到達(dá) A1 跟 B1 的成本，我們可以很容易的想出到達(dá) A2 的最佳路徑。到達(dá) A1 要花費(fèi) 40，而從 A1 到 A2 需要 5。所以 B, C, A 總共要 45。而要到達(dá) B1 只要 10，但需要額外花費(fèi) 110 分鐘來到達(dá) B2 然后走小路到達(dá) A2。所以最佳路徑就是 B, C, A。同樣地到達(dá) B2 最好的方式就是走 A1 然后走小路。

也許你會(huì)問如果先在 B1 跨到道路 A 然后走到 A2 的情況呢？我們已經(jīng)考慮過了從 B1 到 A1 的情況，所以我們不需要再把他考慮進(jìn)去。

現(xiàn)在我們有了至 A2 跟 B2 的最佳路徑，我們可以一直重復(fù)這個(gè)過程直到最右邊。一旦我們到達(dá)了 A4 跟 B4，那其中比較短的就是我們的最佳路徑了。

基本上對(duì)于第二組而言，我們只是不斷地重復(fù)之前的步驟，只是我們考慮進(jìn)在前面的最佳路徑而已。當(dāng)然我們也可以說在第一步就考慮進(jìn)了前面的最佳路徑，只是他們都是 0 而已。

總結(jié)一下。要得到從希思羅機(jī)場(chǎng)到倫敦的最短路徑。我們首先看看到達(dá)下一個(gè)道路 A 上的交叉點(diǎn)的最短路徑。共有兩種選擇的路徑，一是直接從道路 A 出發(fā)然后走到交叉點(diǎn)，要不然就是從道路 B 出發(fā)，走到第一個(gè)交叉點(diǎn)然后走小路。得到結(jié)果后記住結(jié)果。接著再用同樣的方法來得到走到道路 B 上下一個(gè)交叉點(diǎn)的最短路徑，并也記住結(jié)果。然后我們看看要走到再下一個(gè)道路 A 上的交叉點(diǎn)，究竟是從這個(gè)道路 A 上的交叉點(diǎn)往前走，或是從對(duì)應(yīng)的道路 B 上的交叉點(diǎn)往前走再走到對(duì)面，兩種選擇哪種比較好。記下比較好的選擇，然后也對(duì)對(duì)應(yīng)的道路 B 上的交叉點(diǎn)做一次這個(gè)過程。做完全部組之后就到達(dá)最右邊。一旦到達(dá)最右邊，最佳的選擇就是我們的最短路徑了。

基本上當(dāng)我們到達(dá)最右邊的時(shí)候，我們記下了最后停在道路 A 的最短路徑跟最后停在道路 B 的最短路徑。其中比較短的是我們真正的最短路徑?，F(xiàn)在我們已經(jīng)知道怎么用手算出答案。如果你有閑工夫，你可以拿紙筆對(duì)于任何一組道路配置算出他的最短路徑。

接下來的問題是，我們要如何用 Haskell 的型別來代表這里的道路配置呢？一種方式就是把起始點(diǎn)跟交叉點(diǎn)都當(dāng)作圖的節(jié)點(diǎn)，并連到其他的交叉點(diǎn)。如果我們想像其實(shí)起點(diǎn)也有一條長度為 1 的虛擬道路連接彼此，那每個(gè)交叉點(diǎn)或是節(jié)點(diǎn)就都連接對(duì)面的節(jié)點(diǎn)了。同時(shí)他們也連到下一個(gè)交叉點(diǎn)。唯一的例外是最后一個(gè)節(jié)點(diǎn)，他們只連接到對(duì)面。

data Node = Node Road Road | EndNode Road  
data Road = Road Int Node 

一個(gè)節(jié)點(diǎn)要碼是一個(gè)普通的節(jié)點(diǎn)，他包含有通往下一個(gè)交叉點(diǎn)的路徑信息，還有往對(duì)面道路的信息?；蚴且粋€(gè)終端點(diǎn)，只包含往對(duì)面節(jié)點(diǎn)的道路信息。一條道路包含他多長，還有他指向哪里。例如說，道路 A 的第一個(gè)部份就可寫成 Road 50 a1。其中 a1 是 Node x y 這樣一個(gè)節(jié)點(diǎn)。而 x 跟 y 則分別指向 B1 跟 A2。

另一種方式就是用 Maybe 來代表往下一個(gè)交叉點(diǎn)走的路。每個(gè)節(jié)點(diǎn)有指到對(duì)面節(jié)點(diǎn)的路徑部份，但只有不是終端節(jié)點(diǎn)的節(jié)點(diǎn)才有指向下一個(gè)交叉點(diǎn)的路。

data Node = Node Road (Maybe Road)  
data Road = Road Int Node  

這些是用 Haskell 來代表道路系統(tǒng)的方式，而我們也能靠他們來解決問題。但也許我們可以想出更簡單的模型？如果我們想想之前手算的方式，我們每次檢查都只有檢查三條路徑的長度而已。在道路 A 的部份，跟在道路 B 的部份，還有接觸兩個(gè)部份并將他們連接起來的部份。當(dāng)我們觀察到 A1 跟 B1 的最短路徑時(shí)，我們只考慮第一組的三個(gè)部份，他們分別花費(fèi) 50, 10 跟 30。所以道路系統(tǒng)可以用四組來表示：50, 10, 30，5, 90, 20，40, 2, 25 跟 10, 8, 0。

讓我們數(shù)據(jù)型別越簡單越好，不過這樣已經(jīng)是極限了。

data Section = Section { getA :: Int, getB :: Int, getC :: Int } deriving (Show)  
type RoadSystem = [Section]  

這樣很完美，而且對(duì)于我們的實(shí)作也有幫助。Section 是一個(gè) algebraic data type，包含三個(gè)整數(shù)，分別代表三個(gè)不同部份的道路長。我們也定義了型別同義字，說 RoadSystem 代表包含 section 的 list。

當(dāng)然我們也可以用一個(gè) tuple ``(Int, Int, Int)`` 來代表一個(gè) section。使用 tuple 對(duì)于一些簡單的情況是比較方便，但對(duì)于比較復(fù)雜的情況定義自己的 algebraic data type 會(huì)比較好。他讓型別系統(tǒng)獲得比較多的信息。``(Int, Int, Int)`` 畢竟也可能被使用在定義三維空間中的一個(gè)矢量，只用 tuple 讓我們可能把這兩種情形混雜起來使用。如果我們用 ``Section`` 跟 ``Vector`` 的話就不會(huì)不小心搞混了。

從希思羅機(jī)場(chǎng)到倫敦的道路系統(tǒng)便可以這樣表示：

heathrowToLondon :: RoadSystem  
heathrowToLondon = [Section 50 10 30, Section 5 90 20, Section 40 2 25, Section 10 8 0]  

我們現(xiàn)在要做的就是用 Haskell 實(shí)作我們先前的解法。所以我們應(yīng)該怎樣宣告我們計(jì)算最短路徑函數(shù)的型別呢？他應(yīng)該接受一個(gè)道路系統(tǒng)作為參數(shù)，然后回傳一個(gè)路徑。我們會(huì)用一個(gè) list 來代表我們的路徑。我們定義了 Label 來表示 A, B 或 C。并且也定義一個(gè)同義詞 Path：

data Label = A | B | C deriving (Show)  
type Path = [(Label, Int)] 

而我們的函數(shù) optimalPath 應(yīng)該要有 optimalPath :: RoadSystem -> Path 這樣的型別。如果被喂給 heathrowToLondon 這樣的道路系統(tǒng)，他應(yīng)該要回傳下列的路徑：

[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8)]      

我們接下來就從左至右來走一遍 list，并沿路上記下 A 的最佳路徑跟 B 的最佳路徑。我們會(huì) accumulate 我們的最佳路徑。這聽起來有沒有很熟悉？沒錯(cuò)！就是 left fold。

當(dāng)我們手動(dòng)做解答的時(shí)候，有一個(gè)步驟是我們不斷重復(fù)的。就是檢查現(xiàn)有 A 跟 B 的最佳路徑以及目前的 section，產(chǎn)生出新的 A 跟 B 的最佳路徑。舉例來說，最開始我們的最佳路徑是 [] 跟 []。我們看過 Section 50 10 30 后就得到新的到 A1 的最佳路徑為 [(B,10),(C,30)]，而到 B1 的最佳路徑是 [(B,10)]。如果你們把這個(gè)步驟看作是一個(gè)函數(shù)，他接受一對(duì)路徑跟一個(gè) section，并產(chǎn)生出新的一對(duì)路徑。所以型別是 (Path, Path) -> Section -> (Path, Path)。我們接下來繼續(xù)實(shí)作這個(gè)函數(shù)。

提示：把 ``(Path, Path) -> Section -> (Path, Path)`` 當(dāng)作 left fold 用的二元函數(shù)，fold 要求的型態(tài)是 ``a -> b -> a``。

roadStep :: (Path, Path) -> Section -> (Path, Path)  
roadStep (pathA, pathB) (Section a b c) =   
    let priceA = sum $ map snd pathA  
        priceB = sum $ map snd pathB  
        forwardPriceToA = priceA + a  
        crossPriceToA = priceB + b + c  
        forwardPriceToB = priceB + b  
        crossPriceToB = priceA + a + c  
        newPathToA = if forwardPriceToA <= crossPriceToA  
                        then (A,a):pathA  
                        else (C,c):(B,b):pathB  
        newPathToB = if forwardPriceToB <= crossPriceToB  
                        then (B,b):pathB  
                        else (C,c):(A,a):pathA  
    in  (newPathToA, newPathToB)  

上面的程序究竟寫了些什么？首先他根據(jù)先前 A 的最佳解計(jì)算出道路 A 的最佳解，之后也如法炮制計(jì)算 B 的最佳解。使用 sum $ map snd pathA，所以如果 pathA 是 [(A,100),(C,20)]。priceA 就是 120。forwardPriceToA 就會(huì)是我們要付的成本。如果我們是從先前在 A 上的交叉點(diǎn)前往。那他就會(huì)等于我們至先前交叉點(diǎn)的最佳解加上目前 section 中 A 的部份。crossPriceToA 則是我們從先前在 B 上的交叉點(diǎn)前往 A 所要付出的代價(jià)。他是先前 B 的最佳解加上 section 中 B 的部份加上 C 的長。同樣地方式也可以決定 forwardPriceToB 跟 crossPriceToB。

現(xiàn)在我們知道了到 A 跟 B 的最佳路徑，我們需要根據(jù)這些信息來構(gòu)造到 A 跟 B 的整體路徑。如果直接走到 A 耗費(fèi)較少的話，我們就把 newPathToA 設(shè)置成 (A,a):pathA。這樣做的事就是把 Label A 跟 section 的長度 a 接到最佳路徑的前面。要記得 A 是一個(gè) label，而 a 的型別是 Int。我們?yōu)槭裁匆釉谇懊娑皇?nbsp;pathA ++ [(A,a)] 呢？因?yàn)榻釉?list 的前面比起接在后端要有效率多了。不過這樣產(chǎn)生出來的 list 就會(huì)相反。但要把 list 再反過來并不難。如果先走到 B 再穿越小路走到 A 比較短的話，那 newPathToA 就會(huì)包含這樣走的路線。同樣的道理也可以套用在 newPathToB 上。

最后我們回傳 newPathToA 跟 newPathToB 這一對(duì)結(jié)果。

我們把 heathrowToLondon 的第一個(gè) section 喂給我們的函數(shù)。由于他是第一個(gè) section，所以到 A 跟 B 的最佳路徑就是一對(duì)空的 list。

ghci> roadStep ([], []) (head heathrowToLondon)  
([(C,30),(B,10)],[(B,10)])  

要記住包含的路徑是反過來的，要從右邊往左邊讀。所以到 A 的最佳路徑可以解讀成從 B 出發(fā)，然后穿越到道路 A。而 B 的最佳路徑則是直接從 B 出發(fā)走到下一個(gè)交叉點(diǎn)。

優(yōu)化小技巧：當(dāng)我們寫 ``priceA = sum $ map snd pathA`` 的時(shí)候。我們是在計(jì)算每步的成本。如果我們實(shí)作 ``roadStep`` 成 ``(Path, Path, Int, Int) -> Section -> (Path, Path, Int, Int)`` 的話就可以不必那么做。其中的整數(shù)型別代表 A 跟 B 上的最小成本。

現(xiàn)在我們有了一個(gè)函數(shù)他接受一對(duì)路徑跟一個(gè) section，并產(chǎn)生新的最佳路徑。我們可以用一個(gè) left fold 來做。我們用 ([],[]) 跟第一個(gè) section 來喂給 roadStep 并得到一對(duì)最佳路徑。然后他又被喂給這個(gè)新得到的最佳路徑跟下一個(gè) section。以此類推。當(dāng)我們走過全部的 section 的時(shí)候，我們就會(huì)得到一對(duì)最佳路徑，而其中比較短的那個(gè)就是解答。有了這樣的想法，我們便可以實(shí)作 optimalPath。

optimalPath :: RoadSystem -> Path  
optimalPath roadSystem = 
    let (bestAPath, bestBPath) = foldl roadStep ([],[]) roadSystem  
    in  if sum (map snd bestAPath) <= sum (map snd bestBPath)  
                then reverse bestAPath  
                else reverse bestBPath  

我們對(duì) roadSystem 做 left fold。而用的起始 accumulator 是一對(duì)空的路徑。fold 的結(jié)果也是一對(duì)路徑，我們用模式匹配的方式來把路徑從結(jié)果取出。然后我們檢查哪一個(gè)路徑比較短便回傳他。而且在回傳之前也順便把整個(gè)結(jié)果反過來。因?yàn)槲覀兿惹疤岬降奈覀兪怯媒釉谇邦^的方式來構(gòu)造結(jié)果的。

我們來測(cè)試一下吧！

ghci> optimalPath heathrowToLondon  
[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]  

這正是我們應(yīng)該得到的結(jié)果！不過跟我們預(yù)期的結(jié)果仍有點(diǎn)差異，在最后有一步 (C,0)，那代表我們已經(jīng)在倫敦了仍然跨越小路。不過由于他的成本是 0，所以依然可以算做正確的結(jié)果。

我們找出最佳路徑的函數(shù)，現(xiàn)在要做的只需要從標(biāo)準(zhǔn)輸入讀取文本形式道路系統(tǒng)，并把他轉(zhuǎn)成 RoadSystem，然后用 optimalPath 來把他跑一遍就好了。

首先，我們寫一個(gè)函數(shù)，他接受一串 list 并把他切成同樣大小的 group。我們命名他為 groupOf。當(dāng)參數(shù)是 [1..10] 時(shí)，groupOf 3 應(yīng)該回傳 [[1,2,3],[4,5,6],[7,8,9],[10]]。

groupsOf :: Int -> [a] -> [[a]]  
groupsOf 0 _ = undefined  
groupsOf _ [] = []  
groupsOf n xs = take n xs : groupsOf n (drop n xs)

一個(gè)標(biāo)準(zhǔn)的遞歸函數(shù)。對(duì)于 xs 等于 [1..10] 且 n 等于 3，這可以寫成 [1,2,3] : groupsOf 3 [4,5,6,7,8,9,10]。當(dāng)這個(gè)遞歸結(jié)束的時(shí)候，我們的 list 就三個(gè)三個(gè)分好組。而下列是我們的 main 函數(shù)，他從標(biāo)準(zhǔn)輸入讀取數(shù)據(jù)，構(gòu)造 RoadSystem 并印出最短路徑。

import Data.List  
  
main = do  
    contents <- getContents  
    let threes = groupsOf 3 (map read $ lines contents)  
        roadSystem = map (\[a,b,c] -> Section a b c) threes  
        path = optimalPath roadSystem  
        pathString = concat $ map (show . fst) path  
        pathPrice = sum $ map snd path  
    putStrLn $ "The best path to take is: " ++ pathString  
    putStrLn $ "The price is: " ++ show pathPrice  

首先，我們從標(biāo)準(zhǔn)輸入獲取所有的數(shù)據(jù)。然后我們調(diào)用 lines 來把 "50\n10\n30\n... 轉(zhuǎn)換成 ["50","10","30"..，然后我們 map read 來把這些轉(zhuǎn)成包含數(shù)值的 list。我們調(diào)用 groupsOf 3 來把 list 的 list，其中子 list 長度為 3。我們接著對(duì)這個(gè) list 來 map 一個(gè) lambda (\[a,b,c] -> Section a b c)。正如你看到的，這個(gè) lambda 接受一個(gè)長度為 3 的 list 然后把他變成 Section。所以 roadSystem 現(xiàn)在就是我們的道路配置，而且是正確的型別 RoadSystem。我們調(diào)用 optimalPath 而得到一個(gè)路徑跟對(duì)應(yīng)的代價(jià)，之后再印出來。

我們將下列文本存成文件。

50  
10  
30  
5  
90  
20  
40  
2  
25  
10  
8  
0  

存成一個(gè)叫 paths.txt 的文件然后喂給我們的程序。

$ cat paths.txt | runhaskell heathrow.hs  
The best path to take is: BCACBBC  
The price is: 75  

執(zhí)行成功！你可以用你對(duì) Data.Random 的了解來產(chǎn)生一個(gè)比較大的路徑配置，然后你可以把產(chǎn)生的亂數(shù)數(shù)據(jù)喂給你的程序。如果你碰到堆疊溢出，試試看用 foldl' 而不要用 foldl。foldl' 是 strict 的可以減少內(nèi)存消耗。