许多讲解函数式编程的文章教授抽象的理论化的函数式编程技术,如,组合(composition)、管道(pipelining)、高阶函数(higher order functions)。而本文则有所不同,首先,我会展示一些命令式而非函数式代码的例子,这些例子均来自程序员日常编写的代码,然后,我再将这些例子改写成函数式风格。

文章第一部分演示简单短小的数据转换循环,以及如何将其改写成函数式 maps 和 reduces。第二部分演示复杂的长循环,以及如何把它分割成多个单元,每个单元都是一个函数。第三部分演示一个连续执行一长串数据转换的循环,以及如何将其分解成一个函数式管道。

由于很多人认为 Python 非常易读,所以我们的例子全部由 Python 编写而成。有些例子特意避开了 Python 专有技术,这样做的目的,就是为了更好地演示这些适用于很多语言的函数式编程技术:map、reduce 和 pipeline。

指导方针

当人们谈论函数式编程时,许多令人眼花缭乱的“函数式”特征都将涵盖其中。他们会提及不可变数据(1)、一等函数(2)、尾部调用优化(3),这些都是有助函数式编程的语言层面的功能特性;他们还会提及映射(mapping)、化简(reducing)、管道(pipeling)、递归(recursing)、柯里化(currying)(4)、以及高阶函数的应用,这些均为编写函数式代码的技术和技巧;他们还会提及并行化(parallelization)(5)、惰性求值(lazy evaluation)(6)、确定性(determinism)(7),这些正是函数式程序的优势所在。

抛开以上先不谈,函数式代码可以归结为一个基本特性:没有副作用。它既不依赖于函数之外的数据,也不会改变函数之外的数据。其它每一个“函数式”特征都源自这个特性。在学习过程中,希望你能把它当作一项指导原则。

这是一个非函数式函数:

a = 0  
def increment1():  
    global a
    a += 1

这是一个函数式函数:

def increment2(a):  
    return a + 1

不要遍历列表,应该使用 map 和 reduce。

Map

Map 接受一个函数和一个集合作为参数,它生成一个新的空集合,然后对集合中的每一个元素执行该函数,并把返回的结果值插入新集合中,最后返回这个新集合。

这是一个简单的 map 示例,它接受一个名字列表并返回一个包含这些名字长度的列表:

name_lengths = map(len, ["Mary", "Isla", "Sam"])

print name_lengths  
# => [4, 4, 3]

这是一个 map 示例,它对集合中的每一个元素求平方:

squares = map(lambda x: x * x, [0, 1, 2, 3, 4])

print squares  
# => [0, 1, 4, 9, 16]

这个 map 没有使用一个命名函数,而是一个匿名的、使用 lambda 定义的内联函数。lambda 的参数在冒号的左边,函数体在冒号的右边,函数体运行的结果被(隐式)返回。

下面是一段非函数式代码,它使用随机分配的代码名字来替换一个真实名字列表。

import random

names = ['Mary', 'Isla', 'Sam']  
code_names = ['Mr. Pink', 'Mr. Orange', 'Mr. Blonde']

for i in range(len(names)):  
    names[i] = random.choice(code_names)

print names  
# => ['Mr. Blonde', 'Mr. Blonde', 'Mr. Blonde']

(这个算法可能会把相同的秘密代号分配给多个特工。在秘密任务执行期间,希望这不会成为引发困惑的源头。)

这段代码可以使用 map 重写:

import random

names = ['Mary', 'Isla', 'Sam']

secret_names = map(lambda x: random.choice(['Mr. Pink',  
                                            'Mr. Orange',
                                            'Mr. Blonde']),
                   names)

练习 1. 尝试用 map 重写以下代码。使用代号替换一个列表中的真实名字,代号使用更健壮的策略生成。

names = ['Mary', 'Isla', 'Sam']

for i in range(len(names)):  
    names[i] = hash(names[i])

print names  
# => [6306819796133686941, 8135353348168144921, -1228887169324443034]

(在秘密任务执行期间,希望特工们的脑袋瓜都足够灵光,不至于忘记彼此的秘密代号。)

我的解决方法:

names = ['Mary', 'Isla', 'Sam']

secret_names = map(hash, names)  

Reduce

Reduce 接受一个函数和一个集合作为参数,返回一个通过组合各个元素而生成的值。

这是一个简单的 reduce 示例,它返回集合中所有元素之和。

sum = reduce(lambda a, x: a + x, [0, 1, 2, 3, 4])

print sum  
# => 10

x 是当前被迭代的元素。a 是累加器,它是在前一个元素之上执行 lambda 表达式产生的结果值。reduce() 遍历所有元素,对每一个元素,它对当前的 ax 执行 lambda 表达式,把返回的结果作为下一次迭代的 a 值。

在第一次跌代时 a 是什么值呢?由于不存在前一次迭代结果作为返回值,因此 reduce() 使用集合中的第一个元素作为第一次迭代时的 a 值,然后开始迭代第二个元素。也就是说,第一个 x 值是第二个元素。

这段代码计算单词'Sam'在字符串列表中出现的频率:

sentences = ['Mary read a story to Sam and Isla.',  
             'Isla cuddled Sam.',
             'Sam chortled.']

sam_count = 0  
for sentence in sentences:  
    sam_count += sentence.count('Sam')

print sam_count  
# => 3

这是用 reduce 写的功能相同的代码:

sentences = ['Mary read a story to Sam and Isla.',  
             'Isla cuddled Sam.',
             'Sam chortled.']

sam_count = reduce(lambda a, x: a + x.count('Sam'),  
                   sentences,
                   0)

这段代码如何获知最初的 a 值呢?计算'Sam'出现频率的起点不可能是 'Mary read a story to Sam and Isla.'。 最初的累加器在 reduce() 函数的第三个参数中指定,这个值可以与集合中元素的类型不一致。

为什么 map 和 reduce 更好?

第一,它们通常一行代码就能搞定。

第二,迭代的重要部分 - 集合、操作和返回值 - 总是在 map 和 reduce 的同一位置。

第三,一个循环中的代码可能会影响在它之前定义的变量或者在它之后运行的代码。而按照惯例,maps 和 reduces 则是函数式的。

第四,map 和 reduce 是基本操作。每一次阅读 for 循环代码,都必须逐行遍历代码,而且它在结构上几乎没有什么规律可言,无法通过创建一个脚手架来达到帮助理解代码的目的。与此相反,map 和 reduce 可以立即构建出组合复杂算法的代码块,以及代码读者在脑海中可以立即理解和抽象的元素。“啊,这段代码会转换集合中的每一项,丢弃一些中间转换值,最后组合剩余值作为一个单一值输出。”

第五,map 和 reduce 有许多功能相似的“朋友”,这些都是基于它们的基本行为提供的有用功能的修改版。例如:filterallany 以及 find

练习 2. 尝试使用 map、reduce 和 filter 重写以下代码。Filter 接受一个函数和一个集合作为参数,对集合中的每一个元素执行函数,将执行结果为 True 的元素组成一个集合,最后返回这个集合。

people = [{'name': 'Mary', 'height': 160},  
          {'name': 'Isla', 'height': 80},
          {'name': 'Sam'}]

height_total = 0  
height_count = 0  
for person in people:  
    if 'height' in person:
        height_total += person['height']
        height_count += 1

if height_count > 0:  
    average_height = height_total / height_count

    print average_height
    # => 120

如果这段代码看上去很棘手,那就试着先不要考虑对数据的操作,只关注数据经历的状态,从名字的字典列表到平均高度。不要试图把多个转换函数捆绑在一起,每个函数应该独占一行,并把函数执行结果分配给一个含义明确的变量。一旦代码可以正常运转了,再进一步简化。

我的解决方法:

people = [{'name': 'Mary', 'height': 160},  
          {'name': 'Isla', 'height': 80},
          {'name': 'Sam'}]

heights = map(lambda x: x['height'],  
              filter(lambda x: 'height' in x, people))

if len(heights) > 0:  
    from operator import add
    average_height = reduce(add, heights) / len(heights)

写声明式代码,而非命令式

下面的程序演示了三辆汽车之间的比赛过程。在每一时间步(time step),每辆汽车可能向前移动也可能停下来。在每一时间步,程序打印出车辆到目前为止前进的路线。五个时间步之后,比赛结束。

这是一些示例输出:

-
--
--

--
--
---

---
--
---

----
---
----

----
----
-----

这是程序代码:

from random import random

time = 5  
car_positions = [1, 1, 1]

while time:  
    # decrease time
    time -= 1

    print ''
    for i in range(len(car_positions)):
        # move car
        if random() > 0.3:
            car_positions[i] += 1

        # draw car
        print '-' * car_positions[i]

以上代码为命令式风格。函数式版本与之不同,其具有声明式编程的特点,它描述做什么而不是怎样去做。


作者:Mary Rose,一名程序员兼音乐人,生活在纽约,在 Recurse Center 工作。

原文: A practical introduction to functional programming

感谢: Jodoo 帮助审阅并完成校对。