譯者序

如果真有一門(mén)絕世武功，“招式”和“內(nèi)功”孰輕孰重？如果說(shuō)這個(gè)問(wèn)題真有答案，那么在我講授C語(yǔ)言程序設(shè)計(jì)多年之后，開(kāi)始與本書(shū)相遇相知時(shí)似乎逐漸找到了。
長(zhǎng)久以來(lái)，函數(shù)式編程因?yàn)閭?cè)重原理而被認(rèn)為更接近于“內(nèi)功”。由于某些情況下的性能問(wèn)題以及學(xué)習(xí)資料的缺乏，函數(shù)式編程一直沒(méi)有成為主導(dǎo)。近年來(lái)，計(jì)算機(jī)硬件性能的提升帶來(lái)了轉(zhuǎn)機(jī)，我們看到舊語(yǔ)言逐漸引入函數(shù)式的特性、新語(yǔ)言在構(gòu)建之初就考慮更多函數(shù)式的設(shè)計(jì)。
在這本書(shū)里，當(dāng)分而治之、貪心算法、減而治之、動(dòng)態(tài)規(guī)劃、窮舉搜索這些算法用Haskell純函數(shù)式語(yǔ)言來(lái)實(shí)現(xiàn)時(shí)，簡(jiǎn)短的代碼體現(xiàn)出了科學(xué)思想與工程優(yōu)雅。外化于形、內(nèi)化于心的交相輝映令人沉醉！無(wú)論對(duì)于Haskell程序設(shè)計(jì)，還是對(duì)于C語(yǔ)言程序設(shè)計(jì)，“招式”和“內(nèi)功”的兼收并蓄都是一個(gè)更高的境界！
本書(shū)的作者是牛津大學(xué)的Richard Bird和Jeremy Gibbons教授。令人遺憾的是，Richard Bird教授在2022年4月4日離開(kāi)了我們，他一生致力于推廣函數(shù)式編程，對(duì)算法和程序設(shè)計(jì)做出了偉大貢獻(xiàn)。在翻譯這本書(shū)的過(guò)程中，我深感他文字之魅力和思想之深邃。大家在閱讀此書(shū)時(shí)產(chǎn)生不同編程思維碰撞的電光火石是對(duì)Richard最好的緬懷。

萬(wàn)琳

前言

本書(shū)的目的是使用純函數(shù)方法來(lái)介紹算法設(shè)計(jì)的原理。我們選擇的語(yǔ)言是Haskell，所以我們?cè)O(shè)計(jì)的所有算法都將用Haskell函數(shù)來(lái)表示。Haskell有很多結(jié)構(gòu)化函數(shù)定義的特性，但是我們只會(huì)使用其中的一小部分。
使用函數(shù)代替循環(huán)和賦值語(yǔ)句來(lái)表達(dá)算法會(huì)改變一切。首先，以函數(shù)形式表達(dá)的算法會(huì)由其他更基本的函數(shù)組成，而這些基本函數(shù)可以被單獨(dú)研究并重用在其他算法中。例如，排序算法可以通過(guò)構(gòu)建并使用某種樹(shù)的結(jié)構(gòu)來(lái)實(shí)現(xiàn)，而我們可以將構(gòu)建樹(shù)的函數(shù)與使用樹(shù)的函數(shù)分開(kāi)研究。此外，可以使用簡(jiǎn)單的等式屬性來(lái)捕獲這些基本函數(shù)中每個(gè)函數(shù)的特性以及它們與其他函數(shù)的關(guān)系。在此基礎(chǔ)上，人們可以用一種命令式代碼不容易實(shí)現(xiàn)的方式來(lái)探討和推理算法的“深度”結(jié)構(gòu)�？梢钥隙ǖ氖�，我們可以通過(guò)在謂詞演算中形式化命令程序的規(guī)范并使用循環(huán)不變式來(lái)證明它們是正確的，從而對(duì)命令程序進(jìn)行形式化推理。但這同時(shí)也是函數(shù)式編程的關(guān)鍵所在，即不能輕松地直接根據(jù)命令代碼的語(yǔ)言來(lái)推斷命令式程序的屬性。因此，關(guān)于形式化程序設(shè)計(jì)的書(shū)與關(guān)于算法設(shè)計(jì)的書(shū)有很大的不同：它們要求人們精通謂詞演算和必要的命令性術(shù)語(yǔ)。相比之下，許多關(guān)于算法設(shè)計(jì)的書(shū)通常都會(huì)對(duì)算法進(jìn)行逐步介紹，并使用非形式化陳述的循環(huán)不變式來(lái)幫助人們理解為什么算法是正確的。
函數(shù)式編程使得我們不再需要考慮兩種獨(dú)立的語(yǔ)言，可以通過(guò)簡(jiǎn)單的等式推理過(guò)程愉快地計(jì)算出更好的算法版本，或算法的一部分，而這也許就是本書(shū)的主要貢獻(xiàn)。盡管本書(shū)包含了相當(dāng)多的等式推理，但我們會(huì)盡量簡(jiǎn)化以保證閱讀體驗(yàn)。實(shí)際情況往往是，計(jì)算做起來(lái)很有趣，但大量的公式讀起來(lái)會(huì)很無(wú)聊。盡管命令式算法是用C、Java還是偽代碼來(lái)表示并不是很重要，但如果用函數(shù)式來(lái)表示算法，那情況就完全不同了。
本書(shū)討論的許多問(wèn)題，特別是在后面的部分中，都會(huì)從任務(wù)的規(guī)范開(kāi)始，表示為標(biāo)準(zhǔn)函數(shù)的組合，如映射、過(guò)濾器和折疊，以及其他函數(shù)，如用于計(jì)算列表所有排列的perms、用于計(jì)算所有分區(qū)的parts和用于構(gòu)建特定種類(lèi)的樹(shù)的mktrees。然后以各種方式將這些組件函數(shù)進(jìn)行組合或融合，以構(gòu)建具有所需時(shí)間復(fù)雜性的最終算法。最終排序算法可能不會(huì)涉及底層樹(shù)，但是樹(shù)仍然存在于算法的結(jié)構(gòu)中。融合的概念主導(dǎo)了設(shè)計(jì)過(guò)程的技術(shù)和數(shù)學(xué)方面，同時(shí)也是這本書(shū)真正的驅(qū)動(dòng)力。
對(duì)于任何采用函數(shù)式方法的作者來(lái)說(shuō)，像Haskell這樣的函數(shù)式語(yǔ)言的缺點(diǎn)是，它們不像主流的過(guò)程式語(yǔ)言那樣廣為人知，所以必須花時(shí)間來(lái)解釋它們。這也會(huì)大大增加本書(shū)的篇幅。這個(gè)問(wèn)題的簡(jiǎn)單解決辦法就是假設(shè)讀者已經(jīng)掌握了必要的知識(shí)。關(guān)于Haskell等語(yǔ)言的教材越來(lái)越多，包括我們自己的Thinking Functionally with Haskell（劍橋大學(xué)出版社，2014），我們假設(shè)讀者已經(jīng)讀過(guò)相關(guān)內(nèi)容。事實(shí)上，這本書(shū)是作為前一本書(shū)的姊妹篇設(shè)計(jì)的。在第1章中，我們會(huì)簡(jiǎn)要概述我們的假設(shè)，并簡(jiǎn)要回顧一些基本思想，但是你可能無(wú)法從第1章了解到足夠的Haskell知識(shí)來(lái)理解本書(shū)其余部分的內(nèi)容。即使你對(duì)函數(shù)式編程有所了解，但并不了解等式推理是如何進(jìn)入這一領(lǐng)域的（一些關(guān)于函數(shù)式編程的書(shū)籍根本就沒(méi)有提到等式推理），你可能仍然需要參考我們的前一本書(shū)。在任何情況下，等式推理所涉及的數(shù)學(xué)既不新鮮，也不算困難。
關(guān)于算法設(shè)計(jì)的書(shū)籍傳統(tǒng)上涵蓋3個(gè)廣泛的領(lǐng)域：設(shè)計(jì)原則的集合、有用數(shù)據(jù)結(jié)構(gòu)的研究，以及幾個(gè)世紀(jì)以來(lái)發(fā)現(xiàn)的一些有趣的算法。有時(shí)這些書(shū)的內(nèi)容是按照原則組織的，有時(shí)是按照主題（如圖算法，或文本算法）組織的，有時(shí)是混合使用兩種方式。本書(shū)主要采用第一種方法，專(zhuān)注于許多有效算法背后的五大主要設(shè)計(jì)策略：分而治之、貪心算法、減而治之、動(dòng)態(tài)規(guī)劃和窮舉搜索。這些是每個(gè)認(rèn)真的程序員都應(yīng)該知道的設(shè)計(jì)策略。其中減而治之這一策略較為新穎，并在許多問(wèn)題中被視為動(dòng)態(tài)規(guī)劃的替代方案。
在本書(shū)中，每種設(shè)計(jì)策略都有專(zhuān)門(mén)一部分與之對(duì)應(yīng)，每部分都涵蓋相關(guān)策略的各種已知算法和新算法。本書(shū)沒(méi)有過(guò)多介紹數(shù)據(jù)結(jié)構(gòu)方面的內(nèi)容，雖然在本書(shū)的第一部分中，我們會(huì)討論一些基本的數(shù)據(jù)結(jié)構(gòu)，但我們將結(jié)合一些實(shí)用的Haskell數(shù)據(jù)結(jié)構(gòu)庫(kù)進(jìn)行介紹。這樣做的一個(gè)原因是我們希望控制這本書(shū)的篇幅，另一個(gè)原因是Chris Okasaki的著作Purely Functional Data Structures（劍橋大學(xué)出版社，1998）已涵蓋大量相關(guān)內(nèi)容。自我們開(kāi)始寫(xiě)這本書(shū)以來(lái)，其他關(guān)于函數(shù)式數(shù)據(jù)結(jié)構(gòu)的書(shū)籍已經(jīng)相繼出版，更多的相關(guān)書(shū)籍也在籌備之中。
本書(shū)的另一個(gè)特點(diǎn)是，不僅描述了一些受歡迎的算法，還描述了一些通常不會(huì)出現(xiàn)在算法設(shè)計(jì)類(lèi)書(shū)籍中的算法。其中一些算法改編自Pearls of Functional Algorithm Design（2010）。引入這些新穎的算法是為了讓這本書(shū)更加有趣，同時(shí)也更有教育意義。一般來(lái)說(shuō)，有三種人會(huì)閱讀算法設(shè)計(jì)方面的書(shū)籍：需要參考資料的學(xué)者、正在學(xué)門(mén)課程的本科生或研究生，以及對(duì)算法感興趣的專(zhuān)業(yè)程序員。大多數(shù)專(zhuān)業(yè)程序員并不設(shè)計(jì)算法，而只是從庫(kù)中獲取它們。盡管如此，他們也是本書(shū)的目標(biāo)讀者，因?yàn)橛袝r(shí)專(zhuān)業(yè)程序員會(huì)想了解更多關(guān)于構(gòu)建優(yōu)秀算法的方法和思路。
現(xiàn)實(shí)生活中的算法要比這本書(shū)中介紹的復(fù)雜得多。衛(wèi)星導(dǎo)航系統(tǒng)中的最短路徑算法也比算法設(shè)計(jì)教材中的最短路徑算法復(fù)雜得多�，F(xiàn)實(shí)生活中的算法必須處理規(guī)模問(wèn)題，有效地使用計(jì)算機(jī)硬件、用戶(hù)界面，并考慮許多其他與設(shè)計(jì)良好且實(shí)用的產(chǎn)品相關(guān)的因素。本書(shū)不會(huì)涉及這些方面的內(nèi)容，實(shí)際上，大多數(shù)專(zhuān)門(mén)討論算法設(shè)計(jì)原則的書(shū)也不會(huì)涉及這些方面的內(nèi)容。
本書(shū)還有一個(gè)值得一提的特點(diǎn)：所有的練習(xí)都附有答案，即使有的答案比較簡(jiǎn)短。練習(xí)是本書(shū)的重要組成部分，即使不做練習(xí)，也要閱讀問(wèn)題和答案。本書(shū)沒(méi)有在全書(shū)的最后提供完整的參考書(shū)目，而是在每一章的結(jié)尾列出與該章相關(guān)的一些書(shū)籍和文章等參考文獻(xiàn)。
本書(shū)的大部分主要程序都可以在網(wǎng)站www.cs.ox.ac.uk/publications/books/adwh上找到。你還可以通過(guò)這個(gè)網(wǎng)站查看勘誤表，并報(bào)告新的錯(cuò)誤。我們也歡迎讀者提出改進(jìn)建議，包括有關(guān)新練習(xí)的想法。
致謝
本書(shū)的編寫(xiě)得益于Sue Gibbons、Hsiang�睸hang Ko與 Nicolas Wu的仔細(xì)審閱。手稿是使用Ralf Hinze和Andres L�塰的lhs2TEX系統(tǒng)編寫(xiě)的，該系統(tǒng)完美地呈現(xiàn)了Haskell代碼，并允許進(jìn)行提取和類(lèi)型檢查。然后我們使用Koen Claessen和John Hughes開(kāi)發(fā)的QuickCheck工具對(duì)提取的代碼進(jìn)行測(cè)試。代碼的類(lèi)型檢查和快速檢查幫我們減少了許多錯(cuò)誤，當(dāng)然，限于作者水平，書(shū)中疏漏在所難免，任何遺留的錯(cuò)誤都是我們自己的責(zé)任。
我們也要感謝劍橋大學(xué)出版社的David Tranah和他的團(tuán)隊(duì)，他們的建議和辛勤工作促成了本書(shū)的最終出版。

Richard BirdJeremy Gibbons