【试读】《函数式编程思维》


图灵程序设计丛书 人 民 邮 电 出 版 社 北  京 Functional Thinking [美]Neal Ford 著 郭晓刚 译 函数式编程思维 Beijing • Cambridge • Farnham • Köln • Sebastopol • Tokyo O’Reilly Media, Inc.授权人民邮电出版社出版 内 容 提 要 本书脱离特定的语言特性,关注各种 OOP 语言的共同实践做法,展示如何通过函数式编程 解决问题。知名软件架构师 Neal Ford 展示了不同的编程范式,帮助我们完成从 Java 命令式编程 人员,到使用 Java、Clojure、Scala 的函数式编程人员的完美转变,建立对函数式语言的语法和语 义的良好理解。 本书适合 Java、Clojure、Scala 及其他想要提高工作效率、关注函数式编程的程序员阅读。 定价:49.00元 读者服务热线:(010)51095186转600 印装质量热线:(010)81055316 反盗版热线:(010)81055315 广告经营许可证:京崇工商广字第 0021 号 著    [美] Neal Ford 译    郭晓刚 责任编辑 岳新欣 执行编辑 冯雪松 责任印制 杨林杰 人民邮电出版社出版发行  北京市丰台区成寿寺路11号 邮编 100164  电子邮件 315@ptpress.com.cn 网址 http://www.ptpress.com.cn 北京      印刷 开本:800×1000 1/16 印张:10.25 字数:242千字 2015年 8 月第 1 版 印数:1 — 3 500册 2015年 8 月北京第 1次印刷 著作权合同登记号 图字:01-2015-2577号 ◆ ◆ ◆ iii 版权声明 © 2014 by Neal Ford. Simplified Chinese Edition, jointly published by O’Reilly M edia, Inc. and Posts & Telecom Press, 2015. Authorized translation of the English edition, 2015 O’Reilly Media, Inc., the owner of all rights to publish and sell the same. All rights reserved including the rights of reproduction in whole or in part in any form. 英文原版由 O’Reilly Media, Inc. 出版,2014。 简体中文版由人民邮电出版社出版,2015。英文原版的翻译得到 O’Reilly Media, Inc. 的 授权。此简体中文版的出版和销售得到出版权和销售权的所有者——O’Reilly Media, Inc. 的许可。 版权所有,未得书面许可,本书的任何部分和全部不得以任何形式重制。 iv O’Reilly M edia 通过图书、杂志、在线服务、调查研究和会议等方式传播创新知识。 自 1978 年开始,O’Reilly 一直都是前沿发展的见证者和推动者。超级极客们正在开创 着未来 ,而我们关注真正重要的技术趋势——通过放大那些“细微的信号”来刺激社 会对新科技的应用。作为技术社区中活跃的参与者,O’Reilly 的发展充满了对创新的 倡导、创造和发扬光大。 O’Reilly 为软件开发人员带来革命性的“动物书”;创建第一个商业网站( GNN);组 织了影响深远的开放源代码峰会,以至于开源软件运动以此命名;创立了 Make 杂志, 从而成为 DIY 革命的主要先锋;公司一如既往地通过多种形式缔结信息与人的纽带。 O’Reilly 的会议和峰会集聚了众多超级极客和高瞻远瞩的商业领袖,共同描绘出开创 新产业的革命性思想。作为技术人士获取信息的选择,O’Reilly 现在还将先锋专家的 知识传递给普通的计算机用户。无论是通过书籍出版,在线服务或者面授课程,每一 项 O’Reilly 的产品都反映了公司不可动摇的理念——信息是激发创新的力量。 业界评论 “O’Reilly Radar 博客有口皆碑。” ——Wired “O’Reilly 凭 借一系列(真希望当初我也想到了)非凡想法建立了数百万美元的业务。” ——Business 2.0 “O’Reilly Conference 是聚集关键思想领袖的绝对典范。” ——CRN “一本 O’Reilly 的 书就代表一个有用、有前途、需要学习的主题。” ——Irish Times “Tim 是位特立独行的商人,他不光放眼于最长远、最广阔的视野并且切实地按照 Yo gi Berra 的建议去做了:‘如果你在路上遇到岔路口,走小路(岔路)。’回顾过去 Tim 似乎每一次都选择了小路,而且有几次都是一闪即逝的机会,尽管大路也不错。” ——Linux Journal O’Reilly Media, Inc.介绍 v 目录 译者序 .....................................................................................................................................................ix 前言 ..........................................................................................................................................................xi 第 1 章 为什么 ....................................................................................................................................1 1.1 范式转变 . ....................................................................................................................................2 1.2 跟上语言发展的潮流 . ................................................................................................................4 1.3 把控制权让渡给语言 / 运行时 . .................................................................................................4 1.4 简洁 . ............................................................................................................................................5 第 2 章 转变思维 ................................................................................................................................9 2.1 普通的例子 . ................................................................................................................................9 2.1.1 命令式解法 . ...................................................................................................................9 2.1.2 函数式解法 . .................................................................................................................10 2.2 案例研究:完美数的分类问题 . ..............................................................................................15 2.2.1 完美数分类的命令式解法 . .........................................................................................15 2.2.2 稍微向函数式靠拢的完美数分类解法 . .....................................................................16 2.2.3 完美数分类的 Java 8 实现 . .........................................................................................18 2.2.4 完美数分类的 Functional Java 实现 . ..........................................................................19 2.3 具有普遍意义的基本构造单元 . ..............................................................................................21 2.3.1 筛选 . .............................................................................................................................22 2.3.2 映射 . .............................................................................................................................23 2.3.3 折叠 / 化约 . ..................................................................................................................25 2.4 函数的同义异名问题 . ..............................................................................................................28 2.4.1 筛选 . .............................................................................................................................28 vi | 目录 2.4.2 映射 . .............................................................................................................................31 2.4.3 折叠 / 化约 . ..................................................................................................................33 第 3 章 权责让渡 ..............................................................................................................................37 3.1 迭代让位于高阶函数 . ..............................................................................................................37 3.2 闭包 . ..........................................................................................................................................38 3.3 柯里化和函数的部分施用 . ......................................................................................................41 3.3.1 定义与辨析 . .................................................................................................................41 3.3.2 Groovy 的情况 . ............................................................................................................42 3.3.3 Clojure 的情况 . ............................................................................................................44 3.3.4 Scala 的情况 . ................................................................................................................44 3.3.5 一般用途 . .....................................................................................................................47 3.4 递归 . ..........................................................................................................................................48 3.5 Stream 和作业顺序重排 . .........................................................................................................53 第 4 章 用巧不用蛮 .........................................................................................................................55 4.1 记忆 . ..........................................................................................................................................55 4.1.1 缓存 . .............................................................................................................................56 4.1.2 引入“记忆” . ...............................................................................................................59 4.2 缓求值 . ......................................................................................................................................65 4.2.1 Java 语言下的缓求值迭代子 . .....................................................................................65 4.2.2 使用 Totally Lazy 框架的完美数分类实现 . ...............................................................67 4.2.3 Groovy 语言的缓求值列表 . ........................................................................................69 4.2.4 构造缓求值列表 . .........................................................................................................72 4.2.5 缓求值的好处 . .............................................................................................................74 4.2.6 缓求值的字段初始化 . .................................................................................................76 第 5 章 演化的语言 .........................................................................................................................79 5.1 少量的数据结构搭配大量的操作 . ..........................................................................................79 5.2 让语言去迎合问题 . ..................................................................................................................81 5.3 对分发机制的再思考 . ..............................................................................................................82 5.3.1 Groovy 对分发机制的改进 . ........................................................................................82 5.3.2 “ 身段柔软”的 Clojure 语言 . .....................................................................................83 5.3.3 Clojure 的多重方法和基于任意特征的多态 . ............................................................85 5.4 运算符重载 . ..............................................................................................................................87 5.4.1 Groovy . .........................................................................................................................87 5.4.2 Scala . .............................................................................................................................89 5.5 函数式的数据结构 . ..................................................................................................................91 5.5.1 函数式的错误处理 . .....................................................................................................91 5.5.2 Either 类 . .....................................................................................................................92 目录 | vii 5.5.3 Option 类 . ...................................................................................................................100 5.5.4 Either 树和模式匹配 . ...............................................................................................100 第 6 章 模式与重用 .......................................................................................................................107 6.1 函数式语言中的设计模式 . ....................................................................................................107 6.2 函数级别的重用 . ....................................................................................................................108 6.2.1 Te mplate Method 模式 . ..............................................................................................109 6.2.2 Strategy 模式 . .............................................................................................................111 6.2.3 Flyweight 模式和记忆 . ..............................................................................................113 6.2.4 Factory 模式和柯里化 . ..............................................................................................116 6.3 结构化重用和函数式重用的对比 . ........................................................................................117 第 7 章 现实应用 ............................................................................................................................125 7.1 J ava 8 . ......................................................................................................................................125 7.1.1 函数式接口 . ...............................................................................................................126 7.1.2 Optional 类型 . ...........................................................................................................128 7.1.3 Java 8 的 stream . .........................................................................................................128 7.2 函数式的基础设施 . ................................................................................................................129 7.2.1 架构 . ...........................................................................................................................129 7.2.2 Web 框架 . ...................................................................................................................132 7.2.3 数据库 . .......................................................................................................................133 第 8 章 多语言与多范式 ..............................................................................................................135 8.1 函数式与元编程的结合 . ........................................................................................................136 8.2 利用元编程在数据类型之间建立映射 . ................................................................................137 8.3 多范式语言的后顾之忧 . ........................................................................................................140 8.4 上下文型抽象与复合型抽象的对比 . ....................................................................................141 8.5 函数式金字塔 . ........................................................................................................................143 作者简介 ..............................................................................................................................................147 封面介绍 ..............................................................................................................................................147 ix 译者序 函数式编程不是屠龙技。过去在一般开发者的认识里,函数式编程是一种仅仅存在于某些 偏门语言里的学究气的概念。然而我们观察当今的主流语言,会发现函数式编程已经成为 了标配,唯其存在形式发生了变化,从固执于“纯”函数式语言,转变为让一些关键的函 数式特征或深或浅地融入到各式语言中去。 函数式编程的普及趋势,我以为主要应该归因于纯函数、一等函数、高阶函数等特征迎 合了人们提高语法表现力和解决大规模并发问题的需要。函数式编程进入主流语言,意 味着我们实际上已经在不同程度地使用着函数式编程。比如,你不一定用 F#,但 LINQ 实在是太方便了;你可能觉得 Clojure 太怪异,但 map、filter、reduce 任何时候都是必备的 利器。 不同语言的函数式能力可以有很大的差别。那么在一些只能迂回模拟个别函数式特征的语 言里面,去谈论函数式编程是否有意义?我对同行提到这本书用 Java 8 来解说函数式编 程的时候,立即被编出了“只有这样才能写一本书”的笑话。笑点显然是因为用 Haskell、 Lisp 来解说的话,写一章就够了。作者 Neal Ford 大概有不一样的看法,因为他故意用了 Scala、Clojure、Groovy、Java 8 这些函数式程度各异的语言,乃至在 Java 5 的极端环境 下的 Functional Java 框架来证明,即使只是函数式编程的一个很小的子集,已经能够满足 很大一部分需要,发挥很大的作用。毕竟,不管语法和实现上如何笨拙,函数式编程为我 们开启的是另一个广阔的思考维度。不负责任地说,就算只学到了 map、filter、reduce 三 板斧,你花在这本书上的时间都是值得的。 那么,要不要来学一学函数式编程呢?我想,开发者总不能比 Java 进步得还慢吧。 我把这本书翻译完了,而且,我敢保证,书里面没有一句话是你看不懂需要去翻原文的。 把一本书从头到尾好好地译完,这件事情就算做过再多次,仍然值得我大大地夸一下自 己,特别是我同时还要照顾两岁的郭寄傲小朋友。我的孩子要尝试 10 次、20 次才肯接受 一种新的食物。我们接受一种新的范式,大概不会比这个简单。 x | 译者序 绕了一个大圈子,我其实想说:靡不有初,鲜克有终。请不要只是买了这本书,而是真的 学会函数式思维吧! 郭晓刚 2015 年 7 月 xi 前言 我第一次认真研究函数式编程是在 2004 年。当时我受到 .NET 平台上一些非常规语言的 吸引,开始摆弄 Haskell 和若干早于 F# 的 ML 家族语言。到了 2005 年,我开始在一些会 议上做关于“.NET 和函数式语言”的演讲,不过那时候的语言多半还只是概念性的,即 使说成是“玩具”也不为过。但不管怎么说,能够试探在一种新的编程思维范式下推演铺 陈的可能性,已然令我乐在其中,而且这段经历改变了我在常规语言里对一些问题的处理 方法。 2010 年我再次涉足这个研究领域,是因为目睹当时崛起的一批语言,例如 Java 生态圈里的 Clojure 和 Scala,一下子让我重温了五年前亲历的那些函数式世界的精妙所在。于是我在一 个午后打开维基百科,顺着链接一页一页地翻阅着,半天时间下来,我已经完全沉迷其中。 就这样,我一头钻入函数式编程的世界,开始了走遍各种思维分枝的探索历程。作为研究 的成果,我于 2011 年在波兰举办的“33rd Degree Conference”大会(http://33degree.org/) 上第一次做了题为“函数式编程思维”的演讲,又在 IBM developerWorks 网站上开设了同 名的系列文章(http://dwz.cn/dev-works-ft-series)。在接下来的两年时间里,我按照每个月写 一篇文章的进度,制订对函数式编程的研究和探索计划,并且坚持了下来。至今,我的函 数式编程思维的演讲仍在继续,并且根据反馈不断完善。 这本书是对“函数式编程思维”演讲和系列文章中所有观点的总结。我发觉磨砺素材最好 的办法是将之反复地呈现给观众,因为我每次做演讲或者写文章都会学到一些新东西。有 些关联或者共性只有深入研究和被迫思考(截稿时间特别能让人集中精神!)之后,才会 发现。 我在上一本书 Presentation Patterns(http://presentationpatterns.com/)中说过视觉象征对于 会议演讲的重要性。因此我在做“函数式编程思维”演讲的时候,特意用了黑板和粉笔的 形象 (来引申出与函数式编程概念的数学联系)。到演讲结束的时候,我会呈现一张半截 粉笔摆在黑板下方的图片,暗示观众自己拿起这半截粉笔,继续探索演讲中提到的观点。 xii | 前言 我做的演讲,写的系列文章以及这本书,目的都是想针对那些在命令式的、面向对象的语 言中浸淫已久的开发者,用一种他们能够理解的方式来介绍函数式编程的核心观点。希望 我提炼的这些观点能引发你的兴致,并且拿起粉笔来继续你自己的探索。 ——Neal Ford,2014 年 6 月于亚特兰大 本书结构 本书每一章都会演示函数式思维的例子。第 1 章“为什么”提供了概述和若干贯穿全书 的思维转换的例子。第 2 章“转变思维”为程序员描绘了一个渐进的转变过程,让你从 面向对象、命令式的观察角度过渡到函数式的观察角度。为了形象地展示这种思维转变, 我分别用命令式风格和函数式风格来解决同一个常见问题以作对比。然后又通过一个详 尽的案例分析来说明函数式的观察角度(以及若干辅助语法)如何帮助你向函数式的思 维方式转变。 第 3 章 “权责让渡”列举了一些可以放心托付给语言或运行时去处理的日常杂务。状态是 Michael F eathers 所谓的“不确定因素”之一,通常在非函数式的语言里需要直接明确地进 行管理 。闭包(closure)允许我们将一部分状态管理工作交托给运行时;我举了一些例子 来说明这个状态处理机制背后的工作原理。这一章还会展示如何按照函数式思维在一些细 节方面放权,例如把集合操作交给递归。这些思路将对代码重用的粒度产生影响。 第 4 章 “用巧不用蛮”着重讨论两个延续“消灭不确定因素”精神的例子,它们利用运行 时来缓存函数的结果,从而获得缓求值(laziness)的特性。很多函数式语言都包含“记 忆”(memoization)特性(可能直接支持,也可能通过库,或者用一点小技巧就能实现), 可以作为一种常用的性能优化手段。我在第 2 章“完全数分类器”例子的基础上比较了几 种不同层次的优化手段,有手工进行的,也有利用语言提供的记忆特性来完成的。如果你 想提前知道比赛的结果,记忆特性是最后的赢家。缓求值( lazy)的数据结构把运算推迟 到最后时刻才去执行,这个特点让我们有机会换一个角度来看待各种数据结构。我演示了 如何实现缓求值数据结构(甚至可以用非函数式语言来实现),以及如何利用语言已经具 备的缓求值特性。 第 5 章“演化的语言”反映各种语言是怎样朝着加强函数式特征的方向演变的。本章还 会讨论若干革命性的语言发展趋势,如操作符重载和方法调用之外的新的分派(dispatch) 方式,讨论让语言去迎合问题(而不是反过来)的观点,以及 Option 等常见的函数式数 据结构。 第 6 章 “模式与重用”通过一些例子来展示解决问题的一般思路。我分析了传统的设计模 式在函数式编程的世界里是怎样蜕变(或者消失)的。我还详细对比了通过继承和通过组 合这两种代码重用方式,并从耦合的角度对它们进行了由表及里的分析。 前言 | xiii 第 7 章“现实应用”详细展示了 Java 开发工具包(JDK)新增的几项人们期待已久的函数 式特性 。从分析中可以看到,Java 8 也像别的语言一样接纳了函数式思维,它的高阶函数 (即 lambda 块)用法就是表现之一。我还讨论了 Java 8 在保持向后兼容上使用的一些巧妙 而优雅的手法。Stream API 是特别提到的一个发扬了函数式思维的亮点,它能够以描述性 的语言简洁明了地表达工作流。最后我介绍了 Java 8 新增的 Option 结构,它解决了 null 返 回值含义模糊的潜在问题。我还用了一些篇幅来讨论函数式架构和数据库的主题,分析函 数式的视角怎样改变了它们的设计。 第 8 章 “多语言与多范式”叙述了函数式编程对于当前这个多语言世界的影响。我们一直 在各种项目中遭遇和容纳越来越多的语言。很多新的语言都是多范式(polyparadigm)的, 同时支持若干种不同的编程模型。例如 Scala 支持面向对象编程和函数式编程。作为最后 一章,我们探讨了活在一个有更多范式可以选择的世界里有什么好处和坏处。 排版约定 本书使用了下列排版约定。 • 楷体 表示新术语或突出强调的内容。 • 等宽字体(constant width) 表示程序片段,以及正文中出现的变量、函数名、数据库、数据类型、环境变量、语 句和关键字等。 • 加粗等宽字体(constant width bold) 表示应该由用户输入的命令或其他文本。 该图标表示一般注记。 使用代码示例 补充材料(示例代码、练习等)可以从 https://github.com/oreillymedia/functional_thinking 下载。 本书是要帮你完成工作的。一般来说,如果本书提供了示例代码,你可以把它用在你的程 序或文档中。除非你使用了很大一部分代码,否则无需联系我们获得许可。比如,用本书 的几个代码片段写一个程序就无需获得许可,销售或分发 O’Reilly 图书的示例光盘则需要 获得许可 ;引用本书中的示例代码回答问题无需获得许可,将书中大量的代码放到你的产 xiv | 前言 品文档中则需要获得许可。 我们很希望但并不强制要求你在引用本书内容时加上引用说明。引用说明一般包括书名、 作者、出版社和 ISBN。比如:“ Functional Thinking b y Neal Ford (O’Reilly). C opyright 2014 Neal Ford, 978-1-449-36551-6.” 如果你觉得自己对示例代码的用法超出了上述许可的范围,欢迎你通过 permissions@ oreilly.com 与我们联系。 Safari® Books Online Safari Books Online(http://www.safaribooksonline.com)是应运 而生的数字图书馆。它同时以图书和视频的形式出版世界顶级 技术和商务作家的专业作品。技术专家、软件开发人员、 Web 设计师 、商务人士和创意专家等,在开展调研、解决问题、学 习和认证培训时,都将 Safari Books Online 视作获取资料的首选渠道。 对于组织团体、政府机构和个人,Safari Books Online 提供各种产品组合和灵活的定 价 策 略 。用户可通过一个功能完备的数据库检索系统访问O’Reilly M edia、Prentice Hall Professional、Addison-Wesley Professional、Microsoft Press、Sams、Que、Peachpit Press、Focal Press、Cisco Press、John Wiley & Sons、Syngress、Morgan Kaufmann、IBM Redbooks、Packt、Adobe Press、FT Press、Apress、Manning、New Riders、McGraw-Hill、 Jones & Bartlett、Course Technology 以及其他几十家出版社的上千种图书、培训视频和正 式出版之前的书稿。要了解 Safari Books Online 的更多信息,我们网上见。 联系我们 请把对本书的评价和问题发给出版社。 美国: O’Reilly Media, Inc. 1005 Gravenstein Highway North Sebastopol, CA 95472 中国: 北京市西城区西直门南大街 2 号成铭大厦 C 座 807 室(100035) 奥莱利技术咨询(北京)有限公司 O’Reilly 的每一本书都有专属网页,你可以在那儿找到本书的相关信息,包括勘误表、示 例代码以及其他信息。本书的网站地址是:http://dwz.cn/functional-thinking。 前言 | xv 对于本书的评论和技术性问题,请发送电子邮件到:bookquestions@oreilly.com。 要了解更多 O’Reilly 图书、培训课程、会议和新闻的信息,请访问以下网站: http://www.oreilly.com 我们在 Facebook 的地址如下:http://facebook.com/oreilly。 请关注我们的 Twitter 动态:http://twitter.com/oreillymedia。 我们的 YouTube 视频地址如下:http://www.youtube.com/oreillymedia。 致谢 感谢 ThoughtWorks 大家庭,这是我能找到的最好的工作环境。感谢和我一起参加各种会 议的讲师们,尤其是“No Fluff, Just Stuff”会议的讲师们,给了我许多思想的碰撞。感谢 这些年来出席“函数式编程思维”演讲的观众,你们的反馈帮我磨砺了本书的素材。特别 感谢本书的技术审阅人,他们给出了中肯的实质性建议。尤其感谢那些花时间提交勘误的 早期读者 ,你们为我揭示了许多视而不见的晦涩之处。感谢数不清的朋友和家人充当了我 坚实的后盾,特别感谢 John Drescher 在我们离家的时候帮忙照顾猫咪们。当然,还要感谢 一直忍耐包容我的夫人 Candy,她早就不指望我能放下对编程的迷恋了。 1 第 1 章 为什么 我们用几分钟来想象一下自己是一名伐木工人,手里有林场里最好的斧子,因此你是工作 效率最高的。突然有一天场里来了个推销的,他把一种新的砍树工具—— 链锯——给夸到 了天上去 。这人很有说服力,所以你也买了一把,不过你不懂得怎么用。你估摸着按照自 己原来擅长的砍树方法,把链锯大力地挥向树干——不知道要先发动它。“链锯不过是时 髦的样子货罢了”,没砍几下你就得出了这样的结论,于是把它丢到一边重新捡起用惯了 的斧子。就在这个时候,有人在你面前把链锯给发动了…… 学习一种全新的编程范式,困难并不在于掌握新的语言。毕竟能拿起这本书的读者,学过 的编程语言少说也有一箩筐——语法不过是些小细节罢了。真正考验人的,是怎么学会用 另一种方式去思考。 本书探讨函数式编程的话题,但重点并不放在函数式编程语言上。请别误会,我并不打算 空谈理论 ,书里会有用很多种语言写成的大量代码,实际上整本书都是围绕着代码来展开 的。用 “函数式”的方式编写代码牵涉到诸多方面,我会用具体的例子来解说各方面的要 旨,包括设计上的种种取舍 、不同重用单元的作用等。比起语法,我更看重思路,因此解 说会从 Java 语言入手,毕竟这是最大的开发者群体的最基本的共同语言,而且会掺杂 Java 8 和旧版 J ava 的例子。我会尽可能地用 Java 语言(或其近亲)来解释函数式编程概念,仅 仅用其他语言来演示一些独有的特性。 也许你对 Scala 和 Clojure 一点都不感兴趣,下半辈子能有现在用着的语言就心满意足了, 可是你的语言并不会停下来,反而时刻都在变得更加函数式,也径直带着你一起。所以 说,现在快来学学函数式编程范式吧 ,这样,当有一天(不是假如)函数式降临你日常使 2 | 第 1 章 用的语言的时候,你才知道如何驾驭它。我们不妨先了解一下,为什么所有的语言都日渐 向函数式靠拢。 1.1 范式转变 计算机科学的进步经常是间歇式的,好思路有时搁置数十年后才突然间变成主流。举个例 子,第一种面向对象的语言 Simula 67 是 1967 年发明的,可是直到 1983 年诞生的 C++ 终 于流行起来以后,面向对象才真正成为主流。很多时候,再优秀的想法也得等待技术基础 慢慢成熟 。早年Java 总被认为太慢,内存耗费太高,不适合高性能的应用,如今硬件市场 的变迁把它变成了极具吸引力的选择。 函数式编程的发展轨迹与面向对象编程十分相似,它也是诞生在学院里,然后用几十年的 时间悄悄浸染了所有的现代编程语言。不过,仅仅在语言里加入一些新语法,并不足以让 开发者完全发挥出这种新思维的全部力量。 我们的讨论可以从两种风格的对比开始,尝试分别用传统编程风格(命令式的循环)和函 数式特征更明显的方式来解决同一道题目。这道题目出自计算机科学史上的著名事件,是 当年 Communications of the ACM 杂志“ Programming Pearls”专栏的作者 Jon Bentley 向计 算机科学先驱 Donald Knuth 提出的挑战。涉猎过文本操作的开发者会很熟悉这道题目: 读 入一个文本文件,确定所有单词的使用频率并从高到低排序,打印出所有单词及其频率的 排序列表。对于问题中的词频统计部分,我给出了一个“传统”Java 的解答,见例 1-1。 例 1-1 词频统计的 Java 实现 public class Words { private Set NON_WORDS = new HashSet() {{ add("the"); add("and"); add("of"); add("to"); add("a"); add("i"); add("it"); add("in"); add("or"); add("is"); add("d"); add("s"); add("as"); add("so"); add("but"); add("be"); }}; public Map wordFreq(String words) { TreeMap wordMap = new TreeMap(); Matcher m = Pattern.compile("\\w+").matcher(words); while (m.find()) { String word = m.group().toLowerCase(); if (! NON_WORDS.contains(word)) { if (wordMap.get(word) == null) { wordMap.put(word, 1); } else { wordMap.put(word, wordMap.get(word) + 1); } } } return wordMap; 为什么 | 3 } } 例 1-1 首先建立了一个“虚词”( nonwords)的集合(包括冠词和其他起连接作用的词), 然后实现了 wordFreq() 方法。方法中首先建立一个 Map 结构来容纳由单词和词频组成的键 值对 ,接着构造了一个用来识别单词的正则表达式。接下来的大段篇幅逐一遍历所有找到 的单词 ,将首次遇到的单词添入Map 结构,将重复遇到的单词的出现次数加 1。对于提倡 以步进方式处理集合(如例中正则表达式的匹配结果)遍历的语言来说,这是司空见惯的 编码风格。 Java 8 新增了 Stream API 和以 lambda 块方式实现的高阶函数(后文将会详细介绍),我们 利用这些新的编程手段来改写上面的例子,就得到例 1-2。 例 1-2 词频统计的 Java 8 实现 private List regexToList(String words, String regex) { List wordList = new ArrayList<>(); Matcher m = Pattern.compile(regex).matcher(words); while (m.find()) wordList.add(m.group()); return wordList; } public Map wordFreq(String words) { TreeMap wordMap = new TreeMap<>(); regexToList(words, "\\w+").stream() .map(w -> w.toLowerCase()) .filter(w -> !NON_WORDS.contains(w)) .forEach(w -> wordMap.put(w, wordMap.getOrDefault(w, 0) + 1)); return wordMap; } 在例 1-2 里,我将正则表达式的匹配结果转换为 stream,更方便后续执行互相独立的 几项操作:将所有的单词条目转换为小写,滤除虚词,计算余下单词的词频。我把 regexToList() 方法经由 find() 产生的匹配结果集合转换成 stream,这是为了让后续的操 作能够像我们考虑问题的方式一样,做完一步再去做下一步。虽然将命令式风格的例 1-1 改为对集合进行三次循环遍历(第一遍把所有的单词变成小写,第二遍滤除虚词,第三遍 计算词频)也能达成目的,但这种写法的效率会惨不忍睹。例 1-1 在一个迭代块里完成三 项操作,这是牺牲了代码的清晰来换取执行性能。哪怕这种牺牲再稀松平常,我总是不情 愿的。 Clojure 语言(http://clojure.org/)的发明人 Rich Hickey 在 Strange Loop 会议上做过一堂题 为“Simple Made Easy” 的 演 讲(http://www.infoq.com/presentations/Simple-Made-Easy), 他翻出了一个已经很少用到的老词——“交织”( complect):穿插缠绕地合为一体,使错 综复杂 。命令式编程风格常常迫使我们出于性能考虑,把不同的任务交织起来 ,以便能够 用一次循环来完成多个任务。而函数式编程用 map()、filter() 这些高阶函数把我们解放 4 | 第 1 章 出来,让我们站在更高的抽象层次上去考虑问题,把问题看得更清楚。后文我们将看到许 多函数式思维破解交织现象的例子。 1.2 跟上语言发展的潮流 如果我们关注各种语言的发展情况就会发现,所有的主流语言都在进行函数式方面的扩 充。早走一步的 Groovy 已经具备了丰富的函数式特性,包括像“记忆”( memoization,指 运行时自动缓存函数返回值的能力)这样的高级特性在内。随着 lambda 块(也就是高阶 函数)被纳入 Java 8,Java 语言也终于披挂上函数式的武器。JavaScript,这种也许算得 上使用最为广泛的语言,本身就拥有不少函数式特性。就连最老成持重的 C++ 语言,也 在 2011 年版的语言标准里增加了 lambda 块,引人关注的 Boost.Phoenix(http://dwz.cn/ phoenix-library)等类库,更是透露出函数式思潮已经对 C++ 语言有了更深入的影响。 不论你用的是 Clojure 这类新语言,还是日常相伴的老语言,都有可能遇到相关的特性, 而只有学会这些新的编程范式,你才能从容地利用它们。我会在第 2 章讨论如何转变思 维,运用这些先进的工具去大展拳脚。 1.3 把控制权让渡给语言/运行时 在计算机科学短短的发展历史上,有时候会从技术主流分出一些枝杈,有源于实务界 的,也有源于学术界的 。例如在 20 世纪 90 年代个人电脑大发展的时期,第四代编程语言 (4GL)也出现了爆发式的流行,涌现了 dBASE、Clipper、FoxPro、Paradox 等不可胜数的 新语言 。这些语言的卖点之一是比C、Pascal 等第三代语言(3GL)更高层次的抽象。换 言之, 4GL 下的一行命令,3GL 可能要用很多行才写得出来,因为 4GL 自带了更丰富的 编程环境 。像从磁盘读取流行的数据库格式这样的功能,4GL 天生就具备,并不需要使用 者特意去实现。 函数式编程也是这样一根横生出来的枝杈,是学术界那些乐于为新思路和新范式寻找表达 手段的计算机科学家们的发明。分出来的枝杈偶尔会重新汇入主流,函数式编程当前正好 是这种情况。函数式语言不仅在 Java 虚拟机(JVM)平台上迅速地崭露头角,例如最有 代表性的 Scala 和 Clojure 语言,.NET 平台也不例外,F# 已经是堂堂正正的平台一员。那 么,为什么所有的平台都在拥抱函数式编程呢? 20 世纪 80 年代早期,我还在上大学的时候,用的编程环境叫作 Pecan Pascal。Pecan Pascal 的独门绝技是可以在 Apple ][ 和 IBM PC 上运行相同的 Pascal 代码。为了做到这一点, Pecan 的工程师祭出了神秘的“字节码”(bytecode)。在编译的时候,开发者写下的 Pascal 源代码会被编译成这种在“虚拟机”上执行的“字节码”,而“虚拟机”在每一种运行平 台上都有专门的原生实现。Pecan Pascal 用起来让人痛不欲生。就算最简单的编程习题, 为什么 | 5 编译出来的代码都慢得无法忍受。当时的硬件水平还没有准备好迎接这样的挑战。 Pecan P ascal 被淘汰了,但它的架构我们都很熟悉。十年之后 Sun 发布了采用同样设计的 Java,在 20 世纪 90 年代中期的硬件环境下勉力取得了成功。Java 还带来了其他一些救开 发者于水火的特性,自动垃圾收集即是其中之一。我从此再也不想碰那些没有垃圾收集的 语言 。亲身经历告诉我,最好还是把时间花在更高层次的抽象上,多考虑怎样解决复杂的 业务场景 ,少去费心复杂的底层运作。我为Java 纾解了人工管理内存的痛苦而欣喜,同时 期冀在别的方面也能找到这样的利器。 人生苦短,远离 malloc。 随着时间的推移,开发者们越来越多地把乏味单调的任务托付给语言和运行时。对于我日 常编写的应用程序类型来说,失去对内存的直接控制没什么可惋惜的,放弃这些反而让我 能够专注于更重要的问题。Java 接管内存分配减轻了我们的负担,函数式编程语言让我们 用高阶抽象从容取代基本的控制结构,也有着同样的意义。 将琐碎的细节交托给运行时,令繁冗的实现化作轻巧,这样的例子本书中比比皆是。 1.4 简洁 Working with Legacy Code 的作者 Michael Feathers 用寥寥数语(https://twitter.com/mfeathers/ status/29581296216)捕捉到了函数式抽象和面向对象抽象的关键区别: 面向对象编程通过封装不确定因素来使代码能被人理解;函数式编程通过尽量减少 不确定因素来使代码能被人理解。 ——Michael Feathers 请回想一下你熟悉的封装、作用域、可见性等面向对象编程( OOP)构造,这些机制的 存在意义 ,都是为了精细地控制谁能够感知状态和改变状态。而当涉及多线程的时候,对 状态的控制就更复杂了。这些机制就属于 Michael Feathers 所谓的“不确定因素”( moving parts)。大多数函数式语言在这个问题上采取了另一种做法,它们认为,与其建立种种机 制来控制可变的状态,不如尽可能消灭可变的状态这个不确定因素。其立论的根据是这样 的:假如语言不对外暴露那么多有出错可能的特性 ,那么开发者就不那么容易犯错。我会 展示各种例子来说明函数式编程是怎样消除变量、抽象和其他不确定因素的。 在面向对象的命令式编程语言里面,重用的单元是类和类之间沟通用的消息,这些都可 以用类图( class diagram)来表述。这个领域的代表性著作《设计模式:可复用面向对象 6 | 第 1 章 软件的基础》(Design Patterns: Elements of Reusable Object-Oriented Software,作者 Erich Gamma、R ichard Helm、Ralph Johnson、John Vlissides)就在每一个模式的说明里都附上 了至少一幅类图。OOP 的世界提倡开发者针对具体问题建立专门的数据结构,相关的专门 操作以 “方法”的形式附加在数据结构上。函数式编程语言实现重用的思路很不一样。函 数式语言提倡在有限的几种关键数据结构(如 list、set、map)上运用针对这些数据结构 高度优化过的操作,以此构成基本的运转机构。开发者再根据具体用途,插入自己的数据 结构和高阶函数去调整机构的运转方式。 我们来分析下面截取自例 1-2 的片段: regexToList(words, "\\b\\w+\\b").stream() .filter(w -> !NON_WORDS.contains(w)) 这里为了取得列表的一个子集而调用了 filter() 方法,并向 filter() 方法传入已被转换 为 stream 的列表内容,以及定义了筛选条件的高阶函数(即行中裹上了语法糖衣的 (w → !NON_WORDS.contains(w))))。运转机构高效率地按照指定的条件实行筛选,返回筛选后的 列表。 比起一味创建新的类结构体系,把封装的单元降低到函数级别,更有利于达到细粒度的、 基础层面的重用。反面例子如 Java 世界的数十种 XML 类库,每一种都有自己定义的内部 数据结构 。相比之下,Clojure 就享受到了使用高层次抽象的好处。不久前 Clojure 库中的 map 方法经过创造性的重写,获得了自动并行的能力,也就是说,所有 Clojure 开发者不需 要动一行代码,就自动享受到了 map 操作的性能提升。 函数式程序员喜欢用少数几个核心数据结构,围绕它们去建立一套充分优化的运转机构。 面向对象程序员喜欢不断地创建新的数据结构和附属的操作,因为压倒一切的面向对象编 程范式就是建立新的类和类间的消息。把所有的数据结构都封装成类,一方面压制了方法 层面的重用,另一方面鼓励了大粒度的框架式的重用。函数式编程的程序构造更方便我们 在比较细小的层面上重用代码。 例 1-3 取自为 Java 提供大量辅助工具类的 Apache Commons(http://commons.apache.org/ proper/commons-lang)框架,请观察下面的 indexOfAny() 方法。 例 1-3 取自 Apache Commons 工具类 StringUtils 的 indexOfAny() 方法 // 来源于Apache Commons Lang,http://commons.apache.org/lang/ public static int indexOfAny(String str, char[] searchChars) { if (isEmpty(str) || ArrayUtils.isEmpty(searchChars)) { ➊ return INDEX_NOT_FOUND; } int csLen = str.length(); ➋ int csLast = csLen - 1; int searchLen = searchChars.length; int searchLast = searchLen - 1; 为什么 | 7 for (int i = 0; i < csLen; i++) { ➌ char ch = str.charAt(i); for (int j = 0; j < searchLen; j++) { ➍ if (searchChars[j] == ch) { ➎ if (i < csLast && j < searchLast && CharUtils.isHighSurrogate(ch)) { if (searchChars[j + 1] == str.charAt(i + 1)) { return i; } } else { return i; } } } } return INDEX_NOT_FOUND; } ➊ 防范参数错误。 ➋ 初始化。 ➌ 外层迭代。 ➍ 内层迭代。 ➎ 判断多组条件。 indexOfAny() 方法的参数是一个 String 和一个数组,它会在 String 中查找数组里的字符, 并返回任意一个字符第一次出现的索引位置。其文档中举了一些例子来说明输入与输出的 关系,见例 1-4。 例 1-4 indexOfAny() 的用法示例 StringUtils.indexOfAny("zzabyycdxx",['z','a']) == 0 StringUtils.indexOfAny("zzabyycdxx",['b','y']) == 3 StringUtils.indexOfAny("aba", ['z']) == -1 我们看到,字符串 zzabyycdxx 中第一次出现字符 z 或 a 是在索引位置 0,第一次出现字符 b 或 y 是在索引位置 3。 这个问题的实质可以表述为:对于 searchChars 中的任意字符,在目标字符串中查找该字 符第一处匹配的索引位置。假如换成 Scala 语言,同样的方法实现起来要直接得多,请看 例 1-5 的 firstIndexOfAny 方法。 例 1-5 Scala 实现的 firstIndexOfAny() def firstIndexOfAny(input : String, searchChars : Seq[Char]) : Option[Int] = { def indexedInput = (0 until input.length).zip(input) val result = for (pair <- indexedInput; char <- searchChars; if (char == pair._2)) yield (pair._1) if (result.isEmpty) None 8 | 第 1 章 else Some(result.head) } 在本例中,我为输入字符串制作了一个添加了索引的版本。 Scala 的 zip() 方法将(从 0 到 输入字符串长度值的)数字集合与 String 对象中所含字符的集合对位结合,组成一个新 的、由数字和字符对构成的集合 。例如当输入字符串为 zabycdxx 时,indexedInput 将取值 为 Vector ((0,z), (1,a), (2,b), (3,y), (4,c), (5,d), (6,x), (7,x))。zip 方法得名于 它像拉链(zipper)一样让两个集合对齐咬合在一起。 准备好索引集合之后,我使用 Scala 的 for comprehension 首先查看待搜索字符的集合,然 后取出索引集合中的索引字符对。由于 Scala 允许快捷访问集合的元素,所以我可以直接 将当前搜索的字符与集合的第二个元素进行比较((if (char == pair._2))))。如果两个 字符相同,那么返回索引字符对的索引部分 (pair._1)。 null 的存在是 Java 语言的一大混乱来源:它到底是一个有效的返回值,还是表明返回值 缺失了 ?包括Scala 在内的很多函数式语言通过 Option 类来避免这种语义上的含混,其取 值要么是表示没有返回值的 None,要么是容纳了返回值的 Some。因为例 1-5 的需求只要求 找到第一处匹配,所以我返回了结果集合的第一个元素 result.head。 从原本需求的第一处匹配改为返回所有的匹配是轻而易举的事情。只要修改一下返回类 型,并去掉返回值外面的包装就可以了,修改后的代码见例 1-6。 例 1-6 返回匹配项的一个缓求值列表 def indexOfAny(input : String, searchChars : Seq[Char]) : Seq[Int] = { def indexedInput = (0 until input.length).zip(input) fo r (pair <- indexedInput; char <- searchChars; if (char == pair._2)) yield (pair._1) } 修改后的 API 去掉了限制,让用户自己决定需要多少个返回值。执行 firstIndexOfAny ("zzabyycdxx", "by") 会得到返回值 3,而 indexOfAny("zzabyycdxx", "by") 的返回值则是 Vector(3, 4, 5)。
还剩23页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

ncnf

贡献于2015-11-27

下载需要 3 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf