函数式算法设计珠玑

本书采用完全崭新的方式介绍算法设计。全书由30个珠玑构成，每个珠玑单独列为一章，用于解决一个特定编程问题。这些问题的出处五花八门，有的来自游戏或拼图，有的是有趣的组合任务，还有的是散落于数据压缩及字串匹配等领域的更为熟悉的算法。每个珠玑以使用函数式编程语言Haskell对问题进行描述作为开始，每个解答均是诉诸于函数式编程法则从问题表述中计算得到。本书适用于那些喜欢学习算法设计思想的函数式编程人员、学生和老师，同样适用于那些期望以数学推理方式处理程序的人员。

Pearls of Functional Algorithm Design
出版者的话
译者序
前言
第1章　最小未出现数1
第2章　优胜问题6
第3章　优化马鞍峰搜索算法10
第4章　一个选择问题17
第5章　排序成对的加和22
第6章　合成10027
第7章　构建最小高度树34
第8章　拆分的贪心算法41
第9章　找出名人46
第10章　删除重复项52
第11章　最大非段和59
第12章　后缀排序问题64
第13章　BurrowsWheeler变换73
第14章　最末尾部82
第15章　所有的公共前缀90
第16章　BoyerMoore算法94
第17章　KnuthMorrisPratt算法102
第18章　规划算法解决Rush Hour问题109
第19章　一个简单的数独求解机117
第20章　Countdown问题124
第21章　hylomorphism和nexus133
第22章　计算行列式的三种方法142
第23章　凸包148
第24章　有理数算术编码156
第25章　整数算术编码164
第26章　SchorrWaite算法175
第27章　有序插入183
第28章　无回路函数式算法192
第29章　JohnsonTrotter算法199
第30章　蜘蛛纺丝问题完全解析205
索引218

Pearls of Functional Algorithm Design1990年，《函数式编程期刊》（Journal of Functional Programming，JFP）正处于筹划阶段。我受到两位编辑Simon Peyton Jones和Philip Wadler之邀，定期撰写名为“函数式珠玑”（Functional Pearls）的专栏。 他们内心的想法是模仿John Bentley曾经在20世纪80年代所撰写的 “编程珠玑”（Programming Pearls）连载，这些珠玑为《ACM通讯》（Communications of the ACM）期刊所写，获得了极大的成功。Bentley在他的珠玑中写道：
正像天然的珍珠产生自刺激了牡蛎的砂粒，编程珠玑产生自刺激了程序员的实际问题。这些程序充满趣味，同时教给我们重要的编程技巧和基本的设计原理。
两位编辑为什么会选择我来承担这项工作呢？我觉得应该是我当时正对与此相关的特定任务感兴趣。这些任务先使用清晰却低效的函数式程序进行问题的表述，然后使用数学推理进一步计算出更高效的程序。20世纪90年代，对函数式编程语言的关注不断增加，原因之一在于这些语言很适合进行数学推理。实际上，函数式编程语言GOFER（全称为GOod For Equational Reasoning)由Mark Jones发明，正如它的首字母缩略词所表达的那样，擅长数学推理。GOFER是推动Haskell发展的语言之一，后者正是本书使用的语言。数学推理是本书的主导主题。
在最近20年里，大约有80个珠玑发表在JFP上，另外有少量珠玑出现在函数式编程国际会议（International Conference of Functional Programming ，ICFP)和程序构造数学会议（Mathematics of Program Construction Conference，MPC)上。我大概撰写了其中的四分之一，更多的是由其他研究者撰写的。这些珠玑的主题包括有趣的程序计算、新颖的数据结构和为特殊应用而基于Haskell和ML构建的小而妙的特殊领域语言。
我的研究兴趣一直是算法和算法设计，因此本书的书名是函数式算法设计珠玑而不是函数式珠玑。很多珠玑以Haskell表述作为开始，继而通过计算得出一个更高效的版本。在写作这些珠玑时，我的目的是看一看算法设计可以在多大程度上沿袭我们熟悉的数学传统：通过已有的数学原理、定理和法则计算出结果。数学中的计算通常是为了对复杂的事物进行简化，而在算法设计中，它表现为另一种形态：把简易却低效的程序转化为完全不透明的高效的版本。珠玑所指的并非是最终的程序，而是指产生这一结果的计算。剩下的珠玑致力于为有趣且巧妙的算法提供简单易懂的解释，其中的一部分珠玑可能涉及不多的计算。从函数式角度解释算法背后的思想要比从过程式角度解释简单得多：函数式程序中作为构建块的函数可以非常容易地分离出来，这些函数很简短，但刻画计算模式的能力很强大。
本书中的一些珠玑虽然已经在JFP或者其他地方出版过，但这里对它们进行了精心打磨。实际上，很多珠玑已经跟原始版本大相径庭了。即使这样，它们肯定还有进一步打磨和优化的空间。对于数学之美的黄金标准是Aigner和Ziegler撰写的《数学天书中的证明》（Proofs from The Book）（第3版，Springer出版社，2003），书中包含了一些数学定理的完美证明。我一直把该书当作目标，努力向它的标准看齐。
接近三分之一的珠玑是全新的。虽然本书的章节在一定意义上是按主题组织的，例如分治法、贪心算法、穷举搜索等，但除非明确指出，所有的珠玑可以按任何顺序阅读。珠玑中存在一些重复材料，多数与我们使用的库函数的属性有关，或者与更一般的法则（例如融合法则的多种叠加）有关。
最后，很多人为本书提供了素材。实际上，有几个珠玑最初是跟其他作者合写的。在此感谢我的合作者Sharon Curtis、Jeremy Gibbons、Ralf Hinze、Geraint Jones和ShinCheng Mu，谢谢他们慷慨地允许我修订这些材料。Jeremy Gibbons还阅读了最后阶段的草稿并提出了大量有助于提高行文质量的宝贵意见。有些珠玑也得到牛津大学编程代数研究组会议的仔细讨论。尽管很多瑕疵和错误已经消除，但是毫无疑问，新的瑕疵和错误也会被引入。除了上面提到的人员，还要感谢Stephen Drape、Tom Harper、Daniel James、Jeffrey Lake、Meng Wang和Nicholas Wu，他们给出了很多正面意见，提高了文稿质量。 我也要感谢Lambert Meertens和Oege de Moor，与他们多年的合作带来了丰富的成果。最后，感谢剑桥大学出版社的编辑David Tranah ，他给予我鼓励和支持，包括在准备终稿时有用的技术建议。
Richard Bird
译者序Pearls of Functional Algorithm Design当前的算法设计主要涵盖的是命令式编程，对函数式编程言之甚少。从知识的发展角度看，这是极其危险的。我们承接这本书翻译任务的初衷，就是为了把本书关于函数式程序设计的深邃思想介绍给国人，同时也希望读者能够构建出更为完整的算法设计知识体系。
多年来，函数式编程一直没有得到应有的重视和普及。这种不幸可能根源于早期研究者没能使用简单易懂、务实有效的方式解释抽象的数学概念。实际上，函数式程序具有命令式程序的全部计算能力。命令式程序基于图灵机模型（更具体点是冯·诺伊曼模型），函数式程序则基于λ演算，两者在数学意义上具有能力等效性。对于冯·诺伊曼架构的计算机的一些不足，函数式编程思想具有天然的优势。我们不断看到最近的一些分布式计算框架常常引入函数式程序的一些特性，甚至它的很多思想正在不断融入如Java、C#或C++等命令式语言中。John Backus在其1977年的图灵奖演讲中就具有先见之明地指出，函数式程序设计思想是解决冯·诺伊曼模型计算瓶颈的替代方案。这一趋势已经发生。同时函数式编程语言也在不断迭代更新中，我们可以在越来越多的工程应用中看到它的威力（请参考Haskell in industry）。更可喜的是，国内某些公司也有一些项目组一直在实际产品中使用Haskell。
本书的内容取材自作者近三十年来的研究成果和深刻思考，每一章围绕一个经典问题，如同在讲述一个引人入胜的故事，不断扫清迷雾，找出事物的本质。每个珠玑在处理方式上，都首先诉诸于Haskell，对问题进行正确的表述，然后继续做一些数学推理，计算出更有效的解法。这种由粗到细不断深化的思想非常具有启发性，是难得的珍珠！
本书作者Bird是牛津大学计算机科学系教授，并担任过系主任一职，也是牛津林肯学院的兼职研究员。Bird长期从事函数式程序设计的研究和教学工作，在代数、算法、Haskell语言等方面均有建树，深受学界敬爱。其中BirdMeertens形式体系（BirdMeertens Formalism）就是他和合作者提出的。Bird也撰写了多本专著和教材，颇受读者推崇。
本书是函数式编程书架上必备的参考书，通过本书的学习，相信会提高你的函数式编程功力。本书可以用作大学教材，也适合程序员在实践过程中参考。本书需要读者具有一定的Haskell编程经验，本书作者撰写的《Haskell函数式程序设计》（已由机械工业出版社引进出版，ISBN 978 7 111 52932 3，定价69.00元），可以用来补足Haskell方面的欠缺。
这本书很薄，但耗费了我们一年零九个月的时间才得以翻译完成。翻译过程也是深入学习和品味函数式编程之美的过程。希望读者在研读本书时，也可以细细品味，静静思考，勤于练习，必然能够不断精进。由于本书的很多术语较新，对应的中文资料较少，再加上一些术语含义深邃，有的甚至是新造的英文单词，翻译难度很大。限于译者水平，翻译中难免存在不当之处，欢迎读者批评指正。
感谢机械工业出版社的姚蕾编辑在整个翻译过程中精心的组织和及时的帮助。
苏统华哈尔滨工业大学软件学院2017年2月