Haskell 门 第2版 函数式编程 第1卷 张 淞 刘长生◎编著 宋方睿 李超亚◎审阅 异步社区会员 railway([email protected]) 专享 尊重版权 异步社区会员 railway([email protected]) 专享 尊重版权 览群书始觉自愚，阅千人而惜知己，写给今生知己张骞文。 ——张淞 异步社区会员 railway([email protected]) 专享 尊重版权 异步社区会员 railway([email protected]) 专享 尊重版权 Foreword As one of the designers of Haskell, and the author of its main compiler, I am delighted to see the second edition of this book. Haskell is a purely functional programming language. Thatis,computationisprimarilydonebyfunctions(asinmathematics)ratherthanbya"do this and then do that" sequence of imperative actions (as in mainstream programming). At firstitisamazingthatyoucandoanythinguseful,givensuchlimitations,buttheexactoppo- site turns out to be the case. With higher order functions, lazy evaluation, and a remarkably expressive type system, Haskell lets you re-imagine your whole attitude to programming. Haskellhasdevelopedrapidlyinrecentyears. Itsincreasinglypowerfultypesystemallows ustoexpressandenforcesophisticatedprogramproperties. Itstemplatemeta-programming, and generic programming features allow us to eliminate masses of boilerplate code. With the insights of modern mathematical theories, more abstract, reusable and highly composable code can be expressed in it. These ideas and features will bring you new perspectives on programming. In this book, you will see how programming is liberated from mutating registers and memory or heap block by using variable assignments, loops and other statements in imperative programming languages. Ultimately, you'll achieve more elegant, type safe and maintainable projects. Expanding your mind by reading this book will, I hope, make you not only a good Haskell programmer but also a good programmer in any languages. Enjoy your reading! ——Simon Peyton Jones 序 作为 Haskell 语言的设计者与其主要编译器的作者之一，我很高兴看见这本书的第二版。 Haskell 是一门纯的函数式语言。也就是说计算机主要是通过函数来完成的（像在数学中一 样），而不是通过“先做这个，再做那个”的命令式操作顺序进行的（像在主流的编程语言 中一样）。首先让人惊奇的是，即便有这样的限制，你也可以做所有你想做的事情，这一点 与没有这些限制的顺序式语言完全一样。Haskell 中的高阶函数、惰性求值和表达能力极强的 类型系统会让你重新塑造你对编程的态度。 Haskell 近些年来一直在快速的开发之中。越来越强大的类型系统可以让我们表达十分精 妙的程序的性质。它的模板元编程与通用编程的特性可以化简掉非常多的重复的、机械的代 码。借助现代数学理论的指引，更加抽象、复用性更强且高度可组合的代码能被表达出来。 这些想法与特性会带给你全新的视角来审视编程。在这本书中你会看到编程是如何从使 用赋值、循环与其它语句更改寄存器、内存或堆中解放出来的。最终你会得到更加优雅、类 型安全并且可维护的项目。通过阅读这本书会开阔你的思维的同时不仅会让你成为一个好的 Haskell 使用者，而且还会让你成为更好的程序员，无论你用的是何种语言，祝你阅读愉快！ ——西蒙·佩顿·琼斯 异步社区会员 railway([email protected]) 专享 尊重版权 异步社区会员 railway([email protected]) 专享 尊重版权 致谢 感谢我在诺丁汉大学的学长，Henrik Nilsson 教授的学生 Neil Sculthorpe 博士对我提出 的关于函数反应式编程问题的耐心解答，还把博士论文中的部分图表的源文件授予我使用， 这对我向读者解释 Haskell 中 Arrow 以及函数式反应编程的概念等方面帮助非常大。 感谢爱丁堡大学的研究员陈炜博士对于书篇幅中范畴论部分的内容给出的宝贵意见。 感谢我的学长冯元龙兄弟一直以来对我著书的支持与鼓励。 感谢联想公司的刘长生对于范畴论一章中部分小节的编写与对我的部分提出的意见，这 些小节十分抽象，如果没有你的帮助这些知识可能很难在书中与读者见面。 感谢来自浙江大学的同事李超亚对本书内容的建议以及为审校工作做出的贡献，有这样 一位对文字与语句锱铢必较的懂 Haskell 朋友帮我审阅书稿让我对书的质量放心了很多。 感谢耶鲁 Paul Hudak 教授的学生，现任职于英特尔公司的刘海 (Paul Liu) 博士在我编 著这本书过程中产生的问题给予的解答。 感谢凌辉对 Haskell 云计算部分的编写，能遇到你这样一位专精 Haskell 的高中生帮我编 写这本书，我在感觉到惊讶的同时还有幸运。 感谢我在诺丁汉大学的学长，Thorsten Altenkirch 教授的学生，李诺博士对我在写书过 程中遇到的很多理论部分的问题提供的帮助。 感谢来自武汉大学的同事罗宸对于书稿中代数类型通用编程以及其他部分提出的问题与 对书中部分内容的质疑，有时使我对问题有了更深入的认识，也使我意识到了一些小节中内 容的遗漏。 感谢来自清华大学的朋友邵成一直以来对本书的关注与支持，你的意见对于本书的出版 特别重要。此外也谢谢你帮助我对 Haskell 相关的各种书籍还有资料的收集和整理，这些最 后都作为了本书比较重要的参考文献。 特别感谢来自清华大学的朋友宋方睿对于本书校对工作。本书有相当多的错误被你发现， 其中包括相当多的细节比如类型签名中少了括号以及代码的实现前后不一致等等，如果没有 你的审阅相信有很多错误将藏匿非常久，这将会非常困扰我的读者朋友。 感谢来自深圳华为公司的朋友孙奇辉对我书一直以来的关注与支持。 我想特别感谢本书的编辑，来自人民邮电出版社的杨海玲老师。由于我的语言表达能力 比较有限，对于部分概念的表达可能有些拉杂、繁复，有多年 IT 书籍编辑出版经验的杨老师 帮我对本书润色、修订相信会让读者阅读起来顺畅很多。 感谢我在宁波诺丁汉大学的学生，现就读于剑桥大学的原宗喆对本书认真的校对。 感谢来自渣打银行的张钊对于本书书稿给出的建议还有部分错误的修正。 最后我想感谢中国 Haskell 社区以及 QQ 群 72874436 中对本书一直关注和支持的朋友， 在与你们讨论 Haskell 过程中让我找到了对很多概念更加合理，对初学者更加友好、深刻的 解释。 7 异步社区会员 railway([email protected]) 专享 尊重版权 第⼀版致谢 在这里，我想衷心地感谢诺丁汉大学和那些曾经无私地帮助过我的人们。正因为有你们 的关怀与教导才使我学到越来越多关于计算机科学的知识，并且让我看到了计算机科学的前 景并意识到了在中国有关函数式编程中文书籍的缺乏，致使我萌生了写一本关于函数式编程 的书的念头，正是并且由于你们不断地支持我，最后促使我完成这本书的编写。 首先感谢 Graham Hutton 教授在我学习高级函数式编程课的时候给予我的详细讲解和 对我本科的 Haskell 程序毕业设计的悉心指导。 感谢 JP Moresmau 先生对 EclipseFP 的无偿开发与在 EclipseFP Github 论坛上对 EclipseFP 的使用中出现的问题给予的耐心解决。 这里，我想特别感谢 Nilsson Henrik 教授在百忙之中抽出时间对本书撰写的关注、支持， 以及对我在编写本书中遇到的疑问的解答。是您的编译原理和编程基础两门课让我对 Haskell 与函数式编程有了更为深入的了解和认识。同时，我也非常荣幸能经常与您在诺丁汉大学 Jubilee 校园里的 Amenities Cafe 一起讨论函数式编程和 Haskell。 感谢我的私人导师RolandBackhouse教授在算法课上对于一些算法构造的细致讲解，以 及对于我提出的有关算法构造与复杂度问题的耐心解答，也谢谢您在生活上给予我的帮助。 此外，也感谢您为我研究生申请提供的推荐信，成为你您的学生我感到无比的荣幸。 感谢 Thomas Anberree 讲师的函数式编程课，正是这门课使我了解了一种全新的编程方 式。此外，我很感激您对学习函数式编程有困难的学生进行了课外辅导并且给出了更多的练 习题，还有您在教师公寓楼下单独为我讲解复合函数的类型。 此外，我十分感谢 Roland Backhouse 教授的学生陈炜博士，感谢您在大学课后组织的数 学和算法问题的讨论课，虽然范围很宽松，涉及排列组合、命题逻辑证明、机器学习和 RSA 加密等，但是让我学到了课堂以外的更多内容。同时，我也十分高兴在平时常常能有机会和 您一起运动和讨论问题。 感谢 Haskell 中文论坛 http://www.haskellcn.org 的创始人吴海生为喜欢 Haskell 与函数 式编程的朋友提供了一个非常好的平台。 感谢来自中国科技大学的朋友在博士在读期间帮忙编写函数响应式编程等章节，虽然函 数响应式编程一章的内容由于结构与内容的问题最终未出现在本书中，但还是特别感谢。 最后，我还想感谢曾经教过我的老师们，他们是费继娟老师、李丹老师、李加福老师和 于华民老师。谢谢您们给我的关心与帮助，伴我一点一滴地从一个孩子成长起来。谢谢您们 带我走入这个充满挑战的学科，让我踏上了一条充满奇幻色彩的路。 8 异步社区会员 railway([email protected]) 专享 尊重版权 前⾔ 当今的计算机编程语言发展函数式语言开始占有越来越重要的地位了，更多的命令语言 中也开始增加了函数式编程语言的特性，比如lambda 表达式、代数类型等等。我相信随着时 间的推移函数式编程语言会在现代的软件工程中扮演越来越重要的角色，而无论是在工程开 发实践还是在编程理论学术研究方面 Haskell 都算得上是走在时代与探索最前沿的语言。所 以学习 Haskell 并不只是学习语法、库的使用等表层的东西，而是学习背后更重要的思想与 技术，比如它的类型系统、它组织代码的方式以及构造算法、优化代码、解决问题的方式。学 习了 Haskell 后当我们在使用其他语言时潜移默化地受到了这些思想的影响写出了更好的代 码时我们学习 Haskell 的目的就达到了；当其他语言的设计中越来越多地受到了 Haskell 的影 响，了解过 Haskell 知识会让我们对这些特性的本质洞若观火，如果我们能做到这点就算是 帮助 Haskell 完成了它的历史使命了。 我在接触 Haskell 时是在 2009 年的年末与陈炜博士聊天时他向我演示使用 Hugs 来写 Haskell 了，当我在起草这本书第一版的时候还是在 2011 年的 5 月，当我还在英国读大三的 时候。在第一版的时候对于 Haskell 很多部分的认识还是比较粗浅，对于 Haskell 很多精深的 部分并没有办法给出比较好的诠释。随着学习与研究的不段深入发现 Haskell 的设计有越来 越多的精妙的地方，于是就越来越想把它们写下来。 全书分为一、二两卷，共有六篇，其中每卷各包含三篇的内容。第一卷中包括基础篇、入 门篇与中级篇。第二卷包括进阶篇、工程篇与理论篇。本卷是全书的第一卷。基础篇将会介 绍一些 Haskell 中十分基础的内容，比如什么是类型、什么是类型类还有什么是函数等等。这 一篇的末尾会使用一些库函数写一些的小程序，希望可以加深读者对这些概念的理解。 在初级篇部分读者将会学习到递归、列表内包、高阶函数以及定义类型和类型类。了解 了这些内容就对如何写 Haskell 的函数、代码的组织有了一个比较初步的认识了。尤其重要 的是读者会了解到函子、可应用函子、单位半群等类型类，了解这些相对理论一些的定义是 如何在实践编程中使用的十分重要。 中级篇主要讨论的是 Haskell 中的 Monad。Monad 在 Haskell 中是非常普遍的内容，尤 其是在处理 IO 时用到的 IO Monad，可以说如果不会使用 Monad 是无法使用 Haskell 写出 应用程序的。但是 Monad 的使用也并没有想像的那么难，其实只是一个类似于接口的定义， 难的地方是从数学的角度上理解它并且知道他是如何被引入到 Haskell 中的，这些内容在本 书最后的理论篇会有讨论。在 Monad 的基础上还有 Monad 转换器，使用 Monad 转换器可 以组合多个 Monad 得到功能多的 Monad。只有当完全理解了 Monad 才能得心应手地使用 Haskell。所以这一部分特别重要。 进阶篇会讨论惰性求值、类型推断，我们在本书的开始就提到了惰性求值，但是并没有 解释 Haskell 中的惰性求值是以何种机制实现的，这一部分就会介绍惰性求值。Haskell 中另 外一部分重要的内容就是类型推断，类型在 Haskell 实在是太重要了，而在这一部分之前我 们并没有系统地介绍它，了解了类型推断系统会更加深入地了解 Haskell 的工作原理。另外 这一部分中还包括通用编程、模板元编程以及宏。这几章的内容都是为了让程序员写更少的 代码完成更多的工作而发明的概念，在通用编程中我们会学习讲解代数类型通用编程，到时 读者就会看到一些数学概念在 Haskell 中是如何指导我们的编程实践的。模板元编程与宏都 是用代码来写代码的机制，但是 Haskell 的强类型让元编程的代码更为安全。 异步社区会员 railway([email protected]) 专享 尊重版权 10 最后两篇分别是工程篇与理论篇，工程篇中我们会介绍一些现实开发中比较常用的库， 比如并发、网络访问、测试等等。虽然内容比较杂乱并且例子都比较简单，但是希望能够在 现实的开发中帮到读者。理论篇中的几章内容相对比较独立，主要包括 Arrow、函数反应式 编程、范畴论，这些都是比较理论的内容，函数反应式编程在 Haskell 这样一门纯的语言中可 以建立非常漂亮的模拟现实世界方式，其中 Arrow 做为一种较好的抽象值得我们了解一下； 最后一章是范畴论，我们用到的函子、Monad 等概念就是从这一个数学分支中得到的，相信 看到这一章内容会让你对 Haskell 有全新的认识。 在阅读这本书的过程中如果遇到任何问题或者有好的建议欢迎通过我的微博　＠阅千人 而惜知己或发送邮件到[email protected]与我讨论，你也可以加入72874436 QQ 群与其他程序员朋友分享你的心得。如果你阅读完了全书并且完全地理解了其中的内容 请务必要发邮件写一篇读后感给我，我将非常乐意与你讨论学习 Haskell。 张淞 2017 年 12 月于杭州网易 异步社区会员 railway([email protected]) 专享 尊重版权