Haskell函数式编程入门（第2版）第2卷 (张淞 刘长生) (z-library.sk, 1lib.sk, z-lib.sk)

Haskell 函数式编程 门 张 淞 刘长生◎编著 宋方睿 李超亚◎审阅 第2版 第2卷 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

异步社区会员 railway(darkis07@163.com) 专享 尊重版权

览群书始觉自愚，阅千人而惜知己，写给今生知己张骞文。 ——张淞 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

异步社区会员 railway(darkis07@163.com) 专享 尊重版权

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. That is, computation is primarily done by functions (as in mathematics) rather than by a "do this and then do that" sequence of imperative actions (as in mainstream programming). At first it is amazing that you can do anything useful, given such limitations, but the exact oppo- 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. Haskell has developed rapidly in recent years. Its increasingly powerful type system allows us to express and enforce sophisticated program properties. Its template meta-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(darkis07@163.com) 专享 尊重版权

异步社区会员 railway(darkis07@163.com) 专享 尊重版权

致谢 感谢我在诺丁汉大学的学长，Henrik Nilsson 教授的学生 Neil Sculthorpe 博士对我提出 的关于函数反应式编程问题的耐心解答，还把博士论文中的部分图表的源文件授予我使用， 这对我向读者解释 Haskell 中 Arrow 以及函数式反应编程的概念等方面帮助非常大。 感谢爱丁堡大学的研究员陈炜博士对于书篇幅中范畴论部分的内容给出的宝贵意见。 感谢我的学长冯元龙兄弟一直以来对我著书的支持与鼓励。 感谢联想公司的刘长生对于范畴论一章中部分小节的编写与对我的部分提出的意见，这 些小节十分抽象，如果没有你的帮助这些知识可能很难在书中与读者见面。 感谢来自浙江大学的同事李超亚对本书内容的建议以及为审校工作做出的贡献，有这样 一位对文字与语句锱铢必较的懂 Haskell 朋友帮我审阅书稿让我对书的质量放心了很多。 感谢耶鲁 Paul Hudak 教授的学生，现任职于英特尔公司的刘海 (Paul Liu) 博士在我编 著这本书过程中产生的问题给予的解答。 感谢凌辉对 Haskell 云计算部分的编写，能遇到你这样一位专精 Haskell 的高中生帮我编 写这本书，我在感觉到惊讶的同时还有幸运。 感谢我在诺丁汉大学的学长，Thorsten Altenkirch 教授的学生，李诺博士对我在写书过 程中遇到的很多理论部分的问题提供的帮助。 感谢来自武汉大学的同事罗宸对于书稿中代数类型通用编程以及其他部分提出的问题与 对书中部分内容的质疑，有时使我对问题有了更深入的认识，也使我意识到了一些小节中内 容的遗漏。 感谢来自清华大学的朋友邵成一直以来对本书的关注与支持，你的意见对于本书的出版 特别重要。此外也谢谢你帮助我对 Haskell 相关的各种书籍还有资料的收集和整理，这些最 后都作为了本书比较重要的参考文献。 特别感谢来自清华大学的朋友宋方睿对于本书校对工作。本书有相当多的错误被你发现， 其中包括相当多的细节比如类型签名中少了括号以及代码的实现前后不一致等等，如果没有 你的审阅相信有很多错误将藏匿非常久，这将会非常困扰我的读者朋友。 感谢来自深圳华为公司的朋友孙奇辉对我书一直以来的关注与支持。 我想特别感谢本书的编辑，来自人民邮电出版社的杨海玲老师。由于我的语言表达能力 比较有限，对于部分概念的表达可能有些拉杂、繁复，有多年 IT 书籍编辑出版经验的杨老师 帮我对本书润色、修订相信会让读者阅读起来顺畅很多。 感谢我在宁波诺丁汉大学的学生，现就读于剑桥大学的原宗喆对本书认真的校对。 感谢来自渣打银行的张钊对于本书书稿给出的建议还有部分错误的修正。 最后我想感谢中国 Haskell 社区以及 QQ 群 72874436 中对本书一直关注和支持的朋友， 在与你们讨论 Haskell 过程中让我找到了对很多概念更加合理，对初学者更加友好、深刻的 解释。 7 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

第⼀版致谢 在这里，我想衷心地感谢诺丁汉大学和那些曾经无私地帮助过我的人们。正因为有你们 的关怀与教导才使我学到越来越多关于计算机科学的知识，并且让我看到了计算机科学的前 景并意识到了在中国有关函数式编程中文书籍的缺乏，致使我萌生了写一本关于函数式编程 的书的念头，正是并且由于你们不断地支持我，最后促使我完成这本书的编写。 首先感谢 Graham Hutton 教授在我学习高级函数式编程课的时候给予我的详细讲解和 对我本科的 Haskell 程序毕业设计的悉心指导。 感谢 JP Moresmau 先生对 EclipseFP 的无偿开发与在 EclipseFP Github 论坛上对 EclipseFP 的使用中出现的问题给予的耐心解决。 这里，我想特别感谢 Nilsson Henrik 教授在百忙之中抽出时间对本书撰写的关注、支持， 以及对我在编写本书中遇到的疑问的解答。是您的编译原理和编程基础两门课让我对 Haskell 与函数式编程有了更为深入的了解和认识。同时，我也非常荣幸能经常与您在诺丁汉大学 Jubilee 校园里的 Amenities Cafe 一起讨论函数式编程和 Haskell。 感谢我的私人导师 Roland Backhouse教授在算法课上对于一些算法构造的细致讲解，以 及对于我提出的有关算法构造与复杂度问题的耐心解答，也谢谢您在生活上给予我的帮助。 此外，也感谢您为我研究生申请提供的推荐信，成为你您的学生我感到无比的荣幸。 感谢 Thomas Anberree 讲师的函数式编程课，正是这门课使我了解了一种全新的编程方 式。此外，我很感激您对学习函数式编程有困难的学生进行了课外辅导并且给出了更多的练 习题，还有您在教师公寓楼下单独为我讲解复合函数的类型。 此外，我十分感谢 Roland Backhouse 教授的学生陈炜博士，感谢您在大学课后组织的数 学和算法问题的讨论课，虽然范围很宽松，涉及排列组合、命题逻辑证明、机器学习和 RSA 加密等，但是让我学到了课堂以外的更多内容。同时，我也十分高兴在平时常常能有机会和 您一起运动和讨论问题。 感谢 Haskell 中文论坛 http://www.haskellcn.org 的创始人吴海生为喜欢 Haskell 与函数 式编程的朋友提供了一个非常好的平台。 感谢来自中国科技大学的朋友在博士在读期间帮忙编写函数响应式编程等章节，虽然函 数响应式编程一章的内容由于结构与内容的问题最终未出现在本书中，但还是特别感谢。 最后，我还想感谢曾经教过我的老师们，他们是费继娟老师、李丹老师、李加福老师和 于华民老师。谢谢您们给我的关心与帮助，伴我一点一滴地从一个孩子成长起来。谢谢您们 带我走入这个充满挑战的学科，让我踏上了一条充满奇幻色彩的路。 8 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

前⾔ 当今的计算机编程语言发展函数式语言开始占有越来越重要的地位了，更多的命令语言 中也开始增加了函数式编程语言的特性，比如 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(darkis07@163.com) 专享 尊重版权

10 最后两篇分别是工程篇与理论篇，工程篇中我们会介绍一些现实开发中比较常用的库， 比如并发、网络访问、测试等等。虽然内容比较杂乱并且例子都比较简单，但是希望能够在 现实的开发中帮到读者。理论篇中的几章内容相对比较独立，主要包括 Arrow、函数反应式 编程、范畴论，这些都是比较理论的内容，函数反应式编程在 Haskell 这样一门纯的语言中可 以建立非常漂亮的模拟现实世界方式，其中 Arrow 做为一种较好的抽象值得我们了解一下； 最后一章是范畴论，我们用到的函子、Monad 等概念就是从这一个数学分支中得到的，相信 看到这一章内容会让你对 Haskell 有全新的认识。 在阅读这本书的过程中如果遇到任何问题或者有好的建议欢迎通过我的微博　＠阅千人 而惜知己或发送邮件到 Haskell.Zhang.Song@hotmail.com与我讨论，你也可以加入 72874436 QQ 群与其他程序员朋友分享你的心得。如果你阅读完了全书并且完全地理解了其中的内容 请务必要发邮件写一篇读后感给我，我将非常乐意与你讨论学习 Haskell。 张淞 2017 年 12 月于杭州网易 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

第⼀版前⾔ 高级计算机语言的诞生大约是在 20 世纪 50 年代。虽然那时电子计算机的发展才刚刚起 步，但计算机语言的设计却逐渐分成了两个阵营。 第一个阵营的设计直接基于计算机硬件的基本结构。这些语言的理念主要是让它们对计 算机的内存、磁盘以及其他硬件的存储状态进行直接的操作，如 Pascal、C 语言等。它们常 常被称为命令式（imperative）、顺序式（sequential）或者过程式（procedural）编程语言。在 语句执行过程中，各个语句的先后顺序十分重要。 而另外一个阵营是希望计算机语言的设计直接从数学函数的角度出发，将计算过程抽象 成函数运算，这种编程方式是对程序的一种更高层次的抽象。虽然起初在运行效率上并不是 很高，但表达起来十分简洁，并且设计者也在努力，逐步使这类程序编译后更适应计算机的 底层硬件以获得更高的运行效率，这一类语言就是函数式编程语言。 在顺序式计算机语言的发展进程中，它们的流行程度大致可以分成两种极端情况：一部 分是像 C、C++、Java、C# 这样的语言，一举成名，成为现在计算机编程语言的主流；另 外是一些“冷门”的语言，可能是一些失败的实验探索性语言，也可能是一些未被很好地商 业化的语言。但是，函数式编程语言在顺序式编程语言取得发展并广泛应用或者消失的几十 年当中，被应用的程度却一直处于不温不火的状态————虽然没有取得广泛的商业化应用， 但是有关的研究和发展从未间断。而软件行业发展到今天，由于顺序式语言在解决一些特定 问题时会引起程序复杂度倍增和可靠程度降低等问题，人们的视角渐渐投向了函数式编程语 言，这使得函数式编程语言在逐步兴起。 函数式编程语言的诞生可以追溯到 20 世纪 50 年代的 Lisp。那时的计算机处理器不是很 强大，函数式编程语言程序的效率要差一些，所以在当时一直没有变成主流。而如今的处理 器速度的提升以及编译器的优化，使得函数式编程语言运行的效率已经不再是一个困扰性的 问题。可是，顺序式语言也在发展，并且还加入了很多新的吸引人的特性，在软件工程的发 展中占据了绝对的优势。即便这样，函数式编程仍然有着其他语言不可能有的优势，所以它 的热度在一点一点地上升，比如微软公司就增强了自家.NET Framework 的函数式编程语言 F# 的功能，并且也能在除 Windows 之外的其他操作系统上使用。除此之外，Java、C++、 C# 在新的版本中也引入了 λ 表达式，这个想法其实就是源于函数式编程的。其他的语言 （如 Python、Ruby、Scala 等）中同样可以看到函数式编程思想的体现。 函数式编程语言有哪些呢？函数式编程语言其实也是一个很大的家族，它是一类语言，就 像命令式编程语言并不单单指 C 语言或 Java 一样，一些常见的函数式编程语言有：Lisp1 、 Scheme、Ocaml、ML（Meta-Language）、Coq2 、Erlang3 、Haskell、Agda4 、F#、Clojure5 等。函数式语言表达程序十分精炼，但是这些并不说明像 Java 这样面向对象的顺序式编程语 言冗长，各种语言在计算机发展进程中百花齐放，各有各的长处与用途。面向对象语言有很 1被认为是首个函数式编程语言，其他函数式编程语言的鼻祖，1958 由斯坦福大学教授 John McCarthy 开发。 2基于 Ocaml，主要用于辅助定理证明，是一个证明辅助工具（proof assistant）。 3Erlang 是由瑞典爱立信计算机实验室为开发实时系统、高并发、分布式系统还有，提高软件安全与稳定性而研 发的语言。 4Agda 是基于 Haskell 的一门依赖类型的函数式编程语言，与 Coq 相似，也是主要用于辅助定义证明的工具。 5Clojure 为 Lisp 的变种，由 Rich Hickey 开发，可运行于 Java 虚拟机之上，具有良好的可移植性。 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

12 大的优势，各种设计模式在商业开发的路上也发展得非常成熟，而函数式编程的优势在于程 序的严谨与可靠性，程序正确性的证明与测试时的简易性，另外，还有开发周期相对短，编 写并发程序十分简洁且运行稳定。函数式编程的应用虽然在很长时间内都处于不温不火的状 态，但它们的用途却非常广泛，常见的领域有人工智能、定理证明、无线通信、金融数据分 析系统等。 另外值得一提的是，在 Matlab 和 Wolfram Mathematica 这类理工科、工程学软件中， 也常常能见到函数式编程的身影与思想的体现，很多基本的函数应用其实都是基于函数 式编程的思想。例如，在《Mathematica Cookbook》一书中，第 2 章讲的便是 Functional Programming，即函数式编程，并且书中说学习函数式编程是掌握 Mathematica 最重要的部 分。所以，学习函数式编程不仅仅是学习一种新的编程语言，而是在更好地体会另外一种编 程思想，这种编程思想在日后的学习与工作中可能会尤为重要。 本书通过 Haskell 这样一门语法经过精心设计和锤炼的纯函数式编程语言来讲解函数式 编程的方法与思想。虽然很多例子都是解决数学与算法问题的，但也有一些例子是对 Haskell 在实际当中应用的展示，旨在说明函数式编程语言不单单是另外一种编程方式或者只是在 教学与研究中使用的语言，同时也是一门可以解决现实编程问题的、非常务实的编程语言。 Haskell 实现了很多软件中的精品，如窗口管理器 XMonad、Perl 6 的 Haskell 实现 Pugs 以 及高性能的网页框架 Yesod、Snap 等。 书中的例子都尽量保证以短小为主，以方便读者根据需要做跳跃、选择性的阅读。 前半部分将简单介绍函数式编程在解决数学与算法问题时精简与直观的特色，使一些不 熟悉 Haskell 的读者对其建立初步的了解，通过解决一些数学算法问题，比如斐波那契数列、 八皇后问题、排序问题、24 点等，引发一些对这种新的编程方式的思考。 中间部分则是一些关于 Haskell 略为深入的介绍，包括函子、monoid、IO 与 monad 转 换器等。其中，monad 的概念在 Haskell 中十分重要，所以建议读者可以花相对比较长的时 间来实践、理解并做一些其他相关的阅读。这里值得说明的是，由于 Haskell 语言的特殊性， 笔者将处理输入与输出的内容安排在了中间这一部分，也就是说，在第 11 章以前，读者将不 会见到可在操作系统上直接运行的程序。 这本书最后几章的主题则是关于快速测试、惰性求值还有并行与并发编程的。这几章的 内容相对零散，但是都讨论的是关于 Haskell 的非常重要的内容。其中，快速测试一章将讨论 如何使用 QuickCheck 库来测试函数的正确性。测试这一课题在软件开发中非常重要而且是 比较困难的，而我们会看到 Haskell 却能以一种较好的方式处理。惰性求值是 Haskell 最重要 的特性之一，也就是说，在函数估值计算时，仅仅计算需要计算的部分。这在某些情况下是 个好主意，但是在另外一些情形下可能会严重降低程序的效率，所以了解它并且正确地用好 它很重要。最后一章将讨论如何在 Haskell 中写可以并发运行的函数。由于 Haskell 的纯函数 特性，它可以随意地并发多个线程来计算纯函数，因为纯函数计算不会互相干扰。当需要共 享变量时，可以使用另外一种非常好的处理并发的机制就是软件事务内存（STM）。经过多 年的研究，STM 已成为了一种使用简单、运行高效、易于扩展的处理并发计算的方式。 有些章节后会有一些开放性的思考题，但并不是很难，读者可以试着独立完成，也可以 在 Haskell 的中文论坛上与其他读者讨论，得到解决问题的思路或者更好的解决方法。书的 大部分是由笔者在课余时间以及假期完成的，但其中部分章节是由来自安徽的中国科技大学 不愿透露姓名的博士朋友执笔撰写的。这些部分是 9.5 节的定长列表以及 9.6 节的运行时重 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

13 载，还有 11.3 节中的实现 printf 函数。但是笔者对其原稿的一些内容做了适当的调整与修 改，以保证全书风格的一致和内容的连贯与顺畅，在此感谢他的帮助与支持。 如果读者没有学过任何编程语言，那么以 Haskell 函数式语言作为第一语言就不必对思 维进行转换了，我想说你非常幸运。如果读者有一些其他函数式编程语言的基础，那么想再 了解一下 Haskell 那就再好不过了。了解其他顺序式语言的读者在学习 Haskell 时需要注意， 由于 Haskell 中是没有内存变量和循环的，因此不会出现变量的赋值、循环。所以，如果读者 已经深谙 C 语言或者 Java 等顺序式编程之道的话，那么在开始学习函数式编程时可能会产 生一些不适应，毕竟没有 for、while 循环还有内存变量的编程方式不太容易一开始就能让熟 练使用 C 语言与 Java 的人所接受。但是，一旦适应了 Haskell 函数式编程的这种方式，读 者可能会发现这种编程方式的效率是相当高的，也有助于看清与理解程序算法的本质。另外， 值得再次指出的是，由于 Haskell 的纯函数特性，输入/输出是在 IO Monad 中处理的，所以 笔者决定等读者对 Monad 有了一定的了解之后再讨论，因此，在学习 IO Monad 以前，只 能在解释器（GHCi）中运行程序。有些读者可能会因此感觉单调，但是了解了 IO Monad 以 后，读者会发现这种设计是很有道理的。此外，有一些理论部分可能看上去有些枯燥，读者 也没有在其他编程语言中涉及过，并且乍看上去感觉并没有什么用途，但是在编程实践中却 恰恰相反，所以读者一定要看懂理论部分，让理论来指导编程实践。 相信读者已经感觉到本书虽然是用中文编写，但在阅读的过程当中却少不了谈论一些英 文术语。有些术语是无法生硬地一对一翻译的，所以笔者给出了自己的翻译的同时保留了其 英文术语，也有的术语并未做出任何翻译，因为生硬的翻译并不会帮助读者理解，所以保留 了原有的英文，以便读者参阅相关的英文资料。 本书编写的目的是希望可以让越来越多的计算机专业的同学以及其他计算机行业的人只 需要花费相对较少的时间就对函数式编程有一定的了解，同时也希望能够达到抛砖引玉的效 果。因为本书的编写是从笔者自己对 Haskell 和函数式编程了解不多之时开始的，希望这能 成为本书的优点，因为非常熟悉了解 Haskell 的人可能很难再以一个初学者的角度来阐述它。 当然，这样的缺点则使书的内容会局限于我对 Haskell 的理解程度。如果读者对有些内容有 更深入的理解或者认为书中有解释不合理或者内容性的错误，欢迎发邮件同我探讨。最后， 当然无论作者与编辑多么努力，总还是会有一些错误藏匿书中，希望广大读者指出。读者有 任何问题欢迎通过Haskell.Zhang.Song@hotmail.com与我联系。 张淞 2013 年 10 月于诺丁汉 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

异步社区会员 railway(darkis07@163.com) 专享 尊重版权

⽬录 I 基础篇 33 1 Haskell 简介 35 1.1 Haskell 的由来 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.2 Haskell 编译器的安装以及编写环境 . . . . . . . . . . . . . . . . . . . . . . . 37 1.2.1 GHCi 的使用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.3 .hs 和.lhs 文件、注释与库函数 . . . . . . . . . . . . . . . . . . . . . . . . 40 1.4 第一个 Haskell 程序——HelloWorld . . . . . . . . . . . . . . . . . . . . . . 40 2 类型系统和函数 43 2.1 Haskell 的类型与数据 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.1 Haskell 常用数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.2 函数类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.1.3 类型的别名 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.1.4 类型的重要性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2 Haskell 中的类型类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.1 相等类型类：Eq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.2.2 有序类型类：Ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.2.3 枚举类型类：Enum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.2.4 有界类型类：Bounded . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.2.5 数类型类：Num . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.3 Haskell 中的函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.3.1 Haskell 中的值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.3.2 函数思想入门 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.3.3 函数的基本定义格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.4 λ 表达式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 2.4.1 λ 表达式的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 2.4.2 参数的绑定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 2.5 Haskell 中的表达式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2.5.1 条件表达式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2.5.2 情形分析表达式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 2.5.3 守卫表达式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 2.5.4 模式匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 15 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

16 目录 2.5.5 运算符与函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.5.6 运算符与自定义运算符 . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.6 在 GHCi 中定义函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3 基于布尔值的函数 85 3.1 关键字 module 与 import 简介 . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.2 简易布尔值的函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.3 与非门和或非门 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4 库函数及其应⽤ 93 4.1 预加载库函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.1.1 常用函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.1.2 基于列表的函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.2 定义历法公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.3 字符串处理的函数 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.4 常用模块简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.4.1 Data.Char . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.4.2 Data.List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.4.3 Data.Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 II 初级篇 111 5 递归函数 113 5.1 递归函数的概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.2 简单递归函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.3 扩展递归与尾递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.4 互调递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.5 麦卡锡的 91 函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.6 斐波那契数列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.7 十进制数字转成罗马数字 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.8 二分搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.9 汉诺塔 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 5.10 排序算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.10.1 插入排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.10.2 冒泡排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.10.3 选择排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 5.10.4 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 5.10.5 归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 5.11 递归基本条件与程序终止 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 5.12 递归与不动点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 5.12.1 牛顿法开方 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 5.13 无基本条件递归和惰性求值 . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 5.13.1 变得懒惰 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

目录 17 6 列表内包 151 6.1 列表生成器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.1.1 并列的列表内包与一般化的列表内包 . . . . . . . . . . . . . . . . . . . 153 6.2 素数相关趣题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.2.1 埃拉托斯特尼筛法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6.3 凯撒加密 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6.3.1 解密 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 6.4 排列与组合问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.4.1 排列问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 6.4.2 错位排列问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6.4.3 组合问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 6.5 八皇后问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 6.6 计算矩阵乘法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 6.6.1 斐波那契数列与矩阵乘法 . . . . . . . . . . . . . . . . . . . . . . . . . 168 6.7 最短路径与矩阵乘法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 7 ⾼阶函数 175 7.1 简单高阶函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 7.2 折叠函数 foldr 与 foldl . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 7.2.1 右折叠函数 foldr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 7.2.2 左折叠函数 foldl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.3 mapAccumL 与 mapAccumR 函数 . . . . . . . . . . . . . . . . . . . . . . . . . . 184 7.4 复合函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 8 定义数据类型 189 8.1 数据类型的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 8.1.1 枚举类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 8.1.2 构造类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 8.1.3 参数化类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 8.1.4 递归类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 8.1.5 杂合定义类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 8.2 类型的同构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 8.3 多分支条件、模式匹配守卫、观察模式表达式与模式的别名 . . . . . . . . . 210 8.3.1 多分支条件表达式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 8.3.2 模式匹配守卫表达式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 8.3.3 观察模式表达式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 8.3.4 模式的的别名 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 8.4 使用 newtype 定义类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 8.5 数学归纳法的有效性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 8.6 树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 8.7 卡塔兰数问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 8.8 霍夫曼编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 8.9 解 24 点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 8.10 Zipper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

18 目录 8.10.1 Zipper 的应用 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 8.11 一般化的代数数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 8.11.1 简易谓词逻辑计算器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 8.12 类型的 kind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 8.12.1 类型的 kind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 8.13 空类型的声明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 9 类型类简介 243 9.1 定义类型类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 9.2 Haskell 中常见类型类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 9.2.1 有序类型类 Ord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 9.2.2 有界类型类 Bounded . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 9.2.3 枚举类型类 Enum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 9.2.4 索引类型类 Ix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 9.2.5 可显示类型类 Show . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 9.2.6 函子类型类 Functor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 9.2.7 可应用函子 Applicative . . . . . . . . . . . . . . . . . . . . . . . . . 253 9.2.8 选择可应用函子 Alternative . . . . . . . . . . . . . . . . . . . . . . 260 9.2.9 简易字符解析器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 9.2.10 可读类型类 Read . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 9.2.11 字符串类型类 IsString . . . . . . . . . . . . . . . . . . . . . . . . . . 266 9.3 类型类实例的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 9.3.1 使用 deriving 关键字 . . . . . . . . . . . . . . . . . . . . . . . . . . 268 9.3.2 使用 instance 关键字 . . . . . . . . . . . . . . . . . . . . . . . . . . 268 9.3.3 空 instance 与 DeriveAnyClasses 语言扩展 . . . . . . . . . . . . . . 270 9.3.4 newtype 定义类型的类型类实例导出 . . . . . . . . . . . . . . . . . . . 271 9.3.5 为类型的别名实现类型类的实例 . . . . . . . . . . . . . . . . . . . . . 272 9.3.6 独立的类型类实例导出 . . . . . . . . . . . . . . . . . . . . . . . . . . 272 9.3.7 deriving 的导出策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 9.3.8 derive 库 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 9.3.9 DriFT 工具 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 9.4 Haskell 中其他常见的类型类 . . . . . . . . . . . . . . . . . . . . . . . . . . 277 9.4.1 单位半群类型类 Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . 277 9.4.2 半群类型类 Semigroup . . . . . . . . . . . . . . . . . . . . . . . . . . 281 9.4.3 默认值类型类 Default . . . . . . . . . . . . . . . . . . . . . . . . . . 282 9.4.4 可折叠类型类 Foldable . . . . . . . . . . . . . . . . . . . . . . . . . . 283 9.4.5 可游历类型类 Traversable . . . . . . . . . . . . . . . . . . . . . . . . 288 9.4.6 二函子类型类 Bifunctor* . . . . . . . . . . . . . . . . . . . . . . . . 292 9.4.7 数类型类 Num . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 9.5 类型类中的类型依赖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 9.6 零参数类型类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 9.7 类型类中的关联类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 9.7.1 重载的列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

目录 19 9.8 运行时重载 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 9.9 Existential 类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 III 中级篇 311 10 Monad 初步 313 10.1 Monad 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 10.2 从 Identity monad 开始 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 10.3 Maybe monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 10.4 Monad 定律 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 10.5 列表 monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 10.6 Monad 相关函数与运算符 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 10.6.1 MonadPlus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 10.6.2 Monad 相关函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 10.7 Functor、Applicative 与 Monad 的关系 . . . . . . . . . . . . . . . . . . . . 328 10.7.1 Monad 的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 10.7.2 Applicative 与 Monad 的差异 . . . . . . . . . . . . . . . . . . . . . . 331 10.7.3 GHC 中 Applicative 与 Monad 的历史问题 . . . . . . . . . . . . . . 332 10.7.4 AMP 问题的未来 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 11 系统编程及输⼊/输出 339 11.1 不纯函数与副作用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 11.2 IO monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 11.3 输入/输出处理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 11.3.1 Control.Monad 中的函数 . . . . . . . . . . . . . . . . . . . . . . . . . 345 11.3.2 系统环境变量与命令行参数 . . . . . . . . . . . . . . . . . . . . . . . . 348 11.3.3 数据的读写 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 11.4 格式化输出 printf 函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 11.4.1 printf 函数的简易实现 . . . . . . . . . . . . . . . . . . . . . . . . . . 353 11.5 星际译王词典 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 11.6 系统编程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 11.6.1 目录与文件操作的 API . . . . . . . . . . . . . . . . . . . . . . . . . . 360 11.6.2 系统进程的相关 API . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 11.7 不安全的 IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 11.8 Haskell 中的时间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 12 记录器 monad、读取器 monad、状态 monad 369 12.1 记录器 monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 12.1.1 MonadWriter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 12.1.2 记录归并排序过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 12.2 读取器 monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 12.2.1 MonadReader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 12.2.2 变量环境的引用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 异步社区会员 railway(darkis07@163.com) 专享 尊重版权

20 目录 12.3 状态 monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 12.3.1 状态 monad 标签器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 12.3.2 用状态 monad 实现栈结构 . . . . . . . . . . . . . . . . . . . . . . . . 380 12.3.3 状态 monad、FunApp 单位半群和读取器 monad 的关系 . . . . . . . . 382 12.3.4 MonadState . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383 12.3.5 基于栈的计算器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 12.4 随机数的生成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396 12.4.1 mwc-random 库 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398 13 Monad 转换器 401 13.1 从 IdentityT monad 转换器开始 . . . . . . . . . . . . . . . . . . . . . . . . 401 13.2 Monad 转换器组合与复合 Monad 的区别 . . . . . . . . . . . . . . . . . . . 405 13.2.1 Monad 转换器的组合顺序 . . . . . . . . . . . . . . . . . . . . . . . . . 407 13.3 lift、liftIO 与 liftBase . . . . . . . . . . . . . . . . . . . . . . . . . . . 410 13.3.1 MonadTrans 类型类与 lift . . . . . . . . . . . . . . . . . . . . . . . . 410 13.3.2 MonadIO 类型类与 liftIO . . . . . . . . . . . . . . . . . . . . . . . . . 411 13.3.3 MonadBase 与 liftBase . . . . . . . . . . . . . . . . . . . . . . . . . . 413 13.4 简易 monad 编译器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 13.5 语法分析 monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 13.6 本章小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421 14 更多 Monad 423 14.1 语法分析器 Monad 组合子 . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 14.1.1 简易语法分析器的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . 423 14.2 Parsec 库简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 14.3 上下文无关文法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 14.4 基于语法分析器的计算器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437 14.5 Stream monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442 14.6 Free monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443 14.7 续延 monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 14.7.1 续延 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 14.7.2 定义续延 monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452 14.7.3 调用当前续延的函数 callCC . . . . . . . . . . . . . . . . . . . . . . . 454 14.8 数据流处理 Monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458 14.9 pipes 与 conduit 库简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469 14.9.1 conduit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469 14.9.2 pipes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 IV 进阶篇 477 15 惰性求值简介 479 15.1 λ 演算简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 15.2 ⊥ Bottom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 异步社区会员 railway(darkis07@163.com) 专享 尊重版权