函数式编程入门(Introduction to Functional Programming)

hwhwhw

函数式编程入门
作者：John Puopolo
翻译：Vincent
联系方式：QQ 14173579 MSN square@sina.com

翻译者的话：本文是一篇新鲜出炉的介绍函数式编程的普及型文章，具体到某一个语言的话就是微软将要推广的F#语言，这应该是微软未来参与多核平台与云计算竞争的重量级产品。相信这些概念对未来游戏开发也会产生深远的影响。相关的F#的资料我会在文章最后加上链接，供广大开发者使用，谢谢。

函数式编程为开发可扩展系统提供了新的途径。
John Puopolo和Sandy Squires是《F#生存手册》的作者，此文便是根据该书所著。《F#生存手册》涵盖了函数式编程的基本元素和F#语言。

分析问题并且建立解决方案的模型的方法有很多种。在软件领域，我们趋向于通过既有的经验和掌握的工具来检视问题。也就是说，我们的经验和掌握的工具影响了我们如何解决问题。比如，在结构化编程的年代，我们通过结构化的分解和子程序来解决问题，同时将重点放在内部聚合和松耦合上。在这些成功的技术之上，我们过渡到了使用对象和面向对象技术来建立解决方案，并且将命令式的代码和数据进行包装。

面向对象的设计和编程还会在未来很多年扮演相当重要的角色，但是我相信我们正在面对一些挑战——这需要新思路和新的解决方案。比如，通过多核架构和云计算来实现的大规模计算能力使得并发式系统和并行算法成为潜在的命令式条件。函数式编程为我们提供了很多工具和技术来满足我们的相关需求。另外，函数式编程为我们提供了新的途径来开发易于调试和测试的可扩展系统。

什么是函数式编程？

函数式编程式是一种检视问题并且建立解决方案的特殊途径。实用一点地讲，函数式编程是一种展现了如下特征的代码风格：
性能和弹性。我们可以通过函数式编程来解决很多真实世界中的通用问题。
简洁。大多数函数式程序包含一个小型关键字集合，以及简明的表达概念的语法。
适用于并行处理。通过不可变值和运算符，函数式程序使自己可以融入异步并行处理。

函数式编程对待计算就像评估函数的价值一样，譬如，运行一个程序或者解决一个数学计算。不奇怪的是，在应用函数式编程时，我们会经常在上下文中使用时态函数。所以，在继续讲解之前，让我们先搞清楚我们确实理解一个函数是什么：
一个函数基本上就是一个转换。它将一组输入准确地转换成一个输出。

纯函数的一个重要的属性就是它不会产生副作用。这表示同样的输入总会产生同样的输出，同时这组输入并不会因为结果而改变。“没有副作用”这个概念在编写多进程和多线程系统时使得函数式编程特别地吸引人。在解决特定问题时，函数式编程的魅力之处在《F#生存手册》中被详细地描述了。

纯函数？
有些编程语言是“纯函数语言”。这表示它们严格地遵守函数规则，比如，没有命令式的循环构造器和没有显示的状态转换。例如Haskell就是一个禁止状态转换和副作用的纯函数语言。绝大多数由纯函数语言编写的程序仅仅由接收输入和返回输出的函数组成。与面向对象语言不同，它们不允许副作用并且使用递归而不是循环来处理迭代。像Haskell这样的语言经常受到“不允许副作用到了极致”之类的批评，这使得它们被排斥在主流开发环境之外。在不允许副作用的语言中像读文件这样的操作将会变得十分笨拙。相反，不纯的、多示例的语言，如由Don Syme和其他来自微软研究所的人所编写的F#，虽然不鼓励副作用和命令式的构造器，但是也不禁止它们出现在函数中。

从函数的纯数学理论中可以得到很多有趣的概念，这些概念在函数式计算中有着广泛的应用。比如，函数可以将其它函数当作参数，也可以将它们当作返回值。基于这些能力，我们可以得到一个富有弹性和强大的机制，这个机制使得我们可以简洁并且优雅地实现那些在非函数式语言中难以表达的目标。

函数式和命令式

我们可以把命令式编程看作是编写一个具有详细步骤并且必须执行给定运算的软件。这些步骤通常是一组表达式，状态转换，循环以及条件转移的集合。

不同的是，函数式编程将程序看作一组函数的集合——一个外层函数调用一个或多个内层函数来计算一个返回值。函数获得参数然后计算返回值，但是就其本身而言并不保留“程序的状态”。

大多数现代的编程语言具有充足的逻辑和数据存储功能，这使得它们本身成为Turing complete。这表示原则上它们可以被用来解决任何计算问题。F#也是一种Turing complete语言。在选择一门语言时，最重要的是它的内在的适用性，而不是能力强弱。

F#在解决特定问题时比其它语言具有优势。F#的不分强大的地方体现在：
信噪比很高。F#的表达方式非常经济，比如，用空格来对符号进行分组。这样你的代码就显得十分简洁。
强大的基于数据类型（而不是布尔值）的匹配逻辑。
原生支持对表达式进行延迟求值。
原生支持通过异步工作流来编写线程安全和异步的应用程序。

为了使事情更加明确，同时也为了吊一下你的胃口，让我们从命令式和函数式的角度来比较它们是如何解决同一个问题的。

示例1：过滤列表
假设我们有一个包含10，000个雇员记录的列表，同时我们想查找所有薪水大于等于100，000美元的员工。采用命令式方法，我们可能会写一个for或者while之类的循环来检查每一个员工的薪水是否符合我们的过滤标准。对于每一个符合标准的员工，我们会向匹配列表添加一条记录。你会发现，我们详细地描述了每一个步骤。相反，从函数式的角度，我们这样来描述解决方案：对一个列表使用一个过滤器从而得到一个新的列表。

示例2：异步下载文件
异步和并行的程序很难做，当然想要做对就更难了。比如，想要通过命令式的语言异步地从一个网站下载HTML文件，我们需要建立HTTP通道，发布异步请求，编写完成子函数，还要管理错误。基于这样的实现，我们也需要管理我们的线程。这样做的结果就是大量复杂的，错误丛生的代码。当我们还无法摆脱这些任务的时候，我们可以通过使用工作流这一来自函数式语言的概念，来简洁且严谨地构造和序列化这些请求。

示例3：自定义算法
函数式语言可以优雅地解决判定值的比较这一经典问题。当你的程序需要排序或者比较值的时候，你需要一个机制来决定两个值是否相等或者其中一个比另一个小。当面对自然有序的元素，譬如数字或者字母，这些自然的排序方法可以使用。然而在很多经济类程序中，我们需要比较那些没有自然排序的元素，比如雇员，汽车，门票，电影，音乐会等等。在具有这类数据的程序中，拥有一个可以对两个元素进行比较或者排序的函数将会是非常另人愉悦的。当然这就是函数式语言最强有力的属性之一——不但使用和返回简单的值，而且可以使用和返回函数。

要用函数式语言解决这个问题，你只需要给用来比较的函数传递一个“排序函数”就能比较两个元素了。根据程序的上下文，或者正在被排序的数据类型，程序可以采用不同的“排序函数”而不用改变主函数流程。函数式语言在设计和功能的方方面面都会展示这一可复用性。

要用传统的命令式语言，我们需要采用函数指针或者类似的结构。再一次提醒，这样做是可行的，但是并不像期望的哪样简洁和优雅。我们可以注意到，C#现在采用了一些函数式结构，包括匿名函数和lambda表达式，这些东西可以帮助我们优雅地解决这类问题。

示例4：创建无限序列
有一些数据集合是自然无限的，比如所有质数的集合，想要计算所有的质数是不可能的。函数式语言采用类似延迟求值和延迟计算的机制来表示无限集合，并且有效地根据需求来计算。再一次提醒，你可以用非函数式语言来完成这个事情，但是命令式的实现会显得“没有那么自然”和更加复杂。

函数式编程可以解决什么问题？
在我成长过程中，我偶尔会帮助父亲修整房子，绘画等东西。从他的教导中我知道“合适的工具”是最重要的。当面对一个难题时，你需要看看你的“工具箱”然后决定哪一个才是最好使的。有时你需要选择锤子，有时是锯。面对语言也是一样。

函数式编程适用于具有如下特征的应用：要求把大量计算并行化的，本质上是并行的，可以从异步请求中受益的，需要复杂模式匹配功能的。这表示函数式程序并不适用于那些典型的处理对象和自身状态的应用；然而，这些应用中的某些个体也许会从基于函数的库中得到极大的好处，比如对固定收入保险的投资组合优化。我们还会看到函数式编程应用于图像处理，机器代数，文法和解析，人工智能，以及数据挖掘。

为什么我需要关注函数式编程？
当你还没有采用函数式编程来开发并发的，可扩展和异步的软件时，选择它将会使你的工作更加简单和安全。函数式编程使你可以借助多核系统的优势，开发稳健的并发算法，并行化大规模计算算法，以及便捷地从不断发展的云计算平台中受益。

此外，如果你还没有开始探索非命令式编程，那么这次探索将会极大地扩展你的问题解决能力和眼界。这些新的概念将会帮助你从不同的视角来分析问题，并且使你更加深刻地理解面向对象技术。

注意：我并不是要说服你相信函数式编程有多么神奇，或者它将如何改变你的生活。它仅仅是一个工具而已，一个可以帮助你解决特定问题的工具。在《F#生存手册》中，我们探索和解释了这些问题，并且指出了为什么函数式编程适用于它们。我们将会在第八章《函数于函数的概念》中继续深度探索函数的概念。在那之前，我们先审视一下“F#的语法，基本数据类型，控制流结果，循环和基本的集合”。

相关链接：
《F#生存手册》http://www.ctocorner.com/fsharp/book/default.aspx
《来自微软的F#》 http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/default.aspx