前 言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和ShinCheng Mu，谢谢他们慷慨地允许我修订这些材料。Jeremy Gibbons还阅读了最后阶段的草稿并提出了大量有助于提高行文质量的宝贵意见。有些珠玑也得到牛津大学编程代数研究组会议的仔细讨论。尽管很多瑕疵和错误已经消除，但是毫无疑问，新的瑕疵和错误也会被引入。除了上面提到的人员，还要感谢Stephen Drape、Tom Harper、Daniel James、Jeffrey Lake、Meng Wang和Nicholas Wu，他们给出了很多正面意见，提高了文稿质量。 我也要感谢Lambert Meertens和Oege de Moor，与他们多年的合作带来了丰富的成果。最后，感谢剑桥大学出版社的编辑David Tranah ，他给予我鼓励和支持，包括在准备终稿时有用的技术建议。
Richard Bird
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
