p2-d-functional-2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 函数也是数据：进阶篇"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在第一部分的最后我们详细介绍了面向对象的概念、方法和实践；在这第二部分的最后我们要更系统地学习一些**函数式**（*functional*）的概念、方法和工具。\n",
    "\n",
    "其实 *functional* 的思想历史很悠久（诞生比 *object-oriented* 还早），但很长时间里都属于很小众的一个编程范型（*paradigm*），不过在最近十年扬眉吐气，热度暴涨，几乎所有新编程语言中都占有一席之地。\n",
    "\n",
    "目前虽普及率还远不及 *object-oriented*，但随着数据科学、人工智能等以数据处理和算法为核心的应用场景的崛起，函数式编程的大量优秀思想一定会得到越来越广泛的认同和应用。\n",
    "\n",
    "目前编程语言的发展趋势是多范型语言，基本就是融合面向对象和函数式里最好的部分。\n",
    "\n",
    "面向对象的起点是“一切都是对象”，函数式的起点则是“一切都是函数”。面向对象着眼于现实世界在计算机程序中的映射，函数式则更多把数学思想和方法引入到软件开发中来，所以函数式编程很受理工科尤其是数学粉的青睐，但比起面向对象门槛还是高了不少。\n",
    "\n",
    "放在 *functional* 这个大帽子下面是一系列围绕函数展开的思想，这些思想之间并没有很强的耦合，完全可以分开理解和应用。关于这些思想可以写好几本书，我们这里只开个头，重点介绍其中最重要的三个：**纯函数**（*pure functions*），**高阶函数**（*higher-order function*）和 **惰性计算**（*lazy evaluation*）。\n",
    "\n",
    "另外你之前已经学过的 `lambda` [匿名函数](2-function-2.ipynb) 和 [函数递归](3-function-3.ipynb)，也都是 functional 大家庭的成员，这里就不重复了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 副作用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "要理解什么是**纯函数**（*pure functions*），就要先理解什么是函数的**副作用**（*side effects*）。\n",
    "\n",
    "在编程世界里，“副作用”指的是一个函数的代码影响了它自己以外的状态，我们看下这个例子："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "正如我们之前学习过的，`count` 是一个全局变量（*global variable*），函数 `add(a, b)` 的工作是把输入的两个数相加，返回二者之和，可是除此以外它还想统计下自己到底被调用了多少次，每被调用一次就把全局变量 `count`  的值加一，所以上面的代码会依次打印 `0`，`7`，`1` 三个数字。这里函数 `add` 操作全局变量 `count` 就是一种**副作用**（*side effect*）。\n",
    "\n",
    "全局变量有很多危害：\n",
    "* 对所有操作全局变量的函数来说，全局变量的状态是个谜，不知道有多少函数在如何影响它，如果要搞清楚那就相当于所有这些函数都要互相了解各自的实现逻辑，这与“责任分离”的模块化原则是背道而驰的，会显著增加整个系统测试和维护的难度；\n",
    "* 全局变量的生命周期和程序本身一样，对全局变量的影响在函数执行完毕之后保持存在，为了维护这些全局变量的值需要额外的开销；\n",
    "* 如果有若干个程序在多核/多CPU的环境下同时操作全局变量，可能导致意想不到的问题。\n",
    "\n",
    "除了读写全局变量，还有一类典型的副作用：改变输入参数的值，请看下面的例子："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "函数 `remove_last()` 的输入参数是一个列表，这个函数直接操作输入参数，弹出（同时删除）最后一个元素后返回，输入参数在调用函数前后内容发生了变化，这也是典型的副作用。\n",
    "\n",
    "这个函数可以很容易改为无副作用的版本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个版本类似经典函数式编程语言 Lisp 中的 butlast 函数，输入参数不动，通过返回一个新的列表来避免副作用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "副作用在短小的程序中没什么太大问题，但在大规模的程序中，会让代码的执行状态非常难以控制，追踪一个变量的值变化变成一个几乎不可能的任务。\n",
    "\n",
    "编程的先辈们延续到我们的共同梦想是：写出无错的软件系统，无论多么复杂。我们希望能够像搭积木一样，用完美的小积木组成大的结构，用大小各异的结构最终搭建出全世界，甚至超越现实世界的超世界（*cyber-world*）。副作用是我们这个宏伟梦想的的死敌，怎么办呢？*Object-oriented* 从描述高内聚低耦合的对象这条路寻找机会，而 *functional* 的开创者们则从另一个角度掏出了大杀器：**不可更改数据**（*immutable values*）和 **纯函数**（*pure functions*）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 纯函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所谓 *immutable value*，是指这么一条强悍的限制：所有变量一经初始化其状态和内容就不能再被改变，也就是说任何变量只能赋值一次，之后永远是这个值，不会变化。\n",
    "\n",
    "如果一个编程语言具有 *immutability* 这个特性，即所有变量都是 *immutable*（和 Python 中的 *tuple* 一样），其实都不配叫“变量”了，因为并不能“变”，这样的函数式编程语言一般就干脆取消 *variable* 这个名词，改用 *label* 这个名词来指 *value* 的名字。\n",
    "\n",
    "在这个简单而又极其苛刻的限制下，函数可以做什么呢？从输入出发计算输出，输出结果只依赖于输入条件和函数体内定义的算法逻辑，不依赖于外界环境；同时函数除了给出计算结果外也不做任何其他事情，不影响函数以外的世界。这样的函数就是**纯函数**（*pure function*）。\n",
    "\n",
    "> 严格来说 *pure function* 是满足下面两个特征的函数：\n",
    "> 1. 幂等（*idempotent*）：这是一个数学术语，意思是函数用相同的输入参数无论调用多少次，每次返回的结果都一样；\n",
    "> 2. 无副作用（*without side effect*）：不会影响和改变函数体以外的状态，包括传入的参数。\n",
    "> \n",
    "> 不太严谨（但好理解）的说法：第 1 点排除了对函数以外环境的依赖，第 2 点排除了对函数以外环境的影响。\n",
    "\n",
    "纯函数非常的**模块化**，往往更**简洁和易于测试**；而纯函数层层调用时，只要保证每个函数的逻辑正确，整个链条就不会出问题，就像数学定理推演的严密逻辑一样。\n",
    "\n",
    "纯函数还有一个巨大的优势：天然支持**并行计算**，无论多少台机器、多少 CPU 和核，以什么顺序调用一个纯函数，只要输入一样输出一定一样，调用之间不会影响，彼此独立的给出结果。这让我们可以放心地把一个大问题切割成无数小问题交给无数机器去算，然后把结果加起来就行。比如并行计算的工业先行者 Google，就利用 *functional* 思想构建了大型并行计算系统，来计算全世界每天数以亿计的网页上的信息数据。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Everything cost*. 这样的好事不会没有代价，*immutable* 和 *pure function* 这条路也一样：\n",
    "* 纯函数有时候不太好写，可能写出来非常难懂，尤其是处理和其他软件以及 I/O 设备（因为键盘鼠标显示器打印机这些都属于全局共享的资源，严格来说纯函数不能直接访问）有关的场景；\n",
    "* *Immutable values* 有时候会带来一定的资源和性能开销，比如因为变量不能重新赋值，导致传统的循环没法写了，必须改用递归（*recursive*）模式来写，相比起来会不那么直观，而且会占用更多内存。\n",
    "\n",
    "这两个问题都有解决方法，前者通过一种特殊的抽象方法，可以在不使用任何副作用的前提下操作外部资源（但说实话，相当抽象和难于理解），还有些编程语言干脆就放宽了特定场景下的限制，允许个别常用、危险可控的副作用（比如读写 I/O）；后一个问题可以通过编译优化来降低资源消耗。\n",
    "\n",
    "反正人类很聪明，凡事也不用那么极端，况且科学计算、机器学习等以数据处理和算法为核心的应用，就非常适合函数式编程范型，很容易把算法和计算任务抽象为一组非常纯粹的函数；至于比较难处理的 I/O 和其他环节，影响可控，总有办法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python 不是一个纯粹的函数式编程语言，也不强制使用纯函数，但我们强烈建议**尽可能保持函数是纯的，对不得不带有副作用的函数在文档中清晰说明副作用**。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 函数也是数据"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本章的标题“函数也是数据（*function is data*）”，说的是，函数和数字、字符串、布尔值之类的没什么两样，也是程序可以操作的一种数据，函数可以作为参数传给别的函数，也可以作为别的函数的返回值返回。\n",
    "\n",
    "* 用作参数或返回值的函数叫做 *first-class function*，是指函数和别的数据没什么两样；\n",
    "* 而把函数作为输入参数或者返回值的函数叫做 *high-order function*（可以翻译为“高阶函数”），意思是操作函数的函数。\n",
    "\n",
    "这两种函数是相辅相成的关系，合起来说明函数是程序里可以被操作的对象，也就是一种 *data*。\n",
    "\n",
    "*Function is data* 是本章要介绍的第二个重要的 *functional* 思想，也是最直接可以看到和用到的。\n",
    "\n",
    "首先我们来看一个 *high-order function* 的例子："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个函数 `apply` 的第一个参数必须是个函数，后面有不定数的参数（*arbitrary arguments*），`apply` 执行第一个参数传进来的函数 `func`，并把其他参数传给 `func` 作为参数，我们可以这么使用它："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的代码和下面这样直接调用是等效的："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "但是我们定义的高阶函数 `apply` 可以执行任何传进来的函数，而不需要在写程序的时候就确定，这是和直接调用 `max` 函数最大的区别。这在某些场景下非常有用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们还可以定义另一种高阶函数，能够构造和返回函数的函数。比如经典的 *function composition* 就是组合两个或者多个函数的效果，假定有两个函数 `f(x)` 和 `g(x)`，那么 `f` 和 `g` 的 *composition* 效果应该等同于 `f(g(x))`，这样的函数操作这么实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "然后可以试试效果："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们定义了两个简单的函数 `double` 和 `inc`，然后用两种不同的顺序对它们做 *composition* 得到两个函数，这两个函数都是我们用高阶函数 `comp2` “造”出来的，它们用起来和别的函数没啥不同："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个例子也告诉我们 *function composition* 没有交换律。\n",
    "\n",
    "像 `comp2` 这样的函数，输入参数和返回值都是函数，是彻头彻尾的 *high-order function*。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 常用高阶函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "高阶函数不是用来玩的，而是确实有大用。这一节我们介绍一些最经典和常用的高阶函数，一般被称为“函数工具”。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面介绍的高阶函数有好几个和一个典型 *functional* 套路有关，就是把要处理的东西做成一个列表，然后对这个列表里的每个元素应用一些函数，或者对整个列表应用一些函数，最后输出一个新的列表或者一个值，在这个套路里有不少经典工具。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### map"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`map` 是一个经典的函数工具，它做的事情是对给定的一个 *iterable* 里每个元素执行一个指定的函数，然后把返回值组成一个新的 *iterable*。我们看看例子："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意中间的 `map(abs, [-2, -1, 0, 1, 2])` 即可，外面包着的一层 `list()` 只是为了展示执行结果。`map` 是个高阶函数，它的第一个参数是个函数 f，第二个参数是个 *iterable*，用里面每个元素作为参数去调用函数 `f`（所以函数 `f` 是只有一个输入参数的函数）。\n",
    "\n",
    "返回结果是一个新的 *iterator*（所以可以用 `list()` 将其转换成列表），其输出序列的每个值和 `lst` 里的值一一对应。上面的例子 `f` 函数是 `abs()`，也就是求绝对值，这个执行过程类似这样：\n",
    "\n",
    "`[-2, -1, 0, 1, 2]` ->  \n",
    "`[abs(-2), abs(-1), abs(0), abs(1), abs(2)]` ->  \n",
    "`[2, 1, 0, 1, 2]`\n",
    "\n",
    "注意：`map` 不改变传入的列表，而是新建一个列表做上面的处理并返回；只要传给 `map` 的函数 `f` 是纯函数（一般都是），`map` 就是。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "传给 `map` 的函数各种各样，所以 `map` 可以做很简单到很复杂的事情，也可以使用匿名函数，下面是个例子（对每个元素做平方的操作）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### reduce"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`reduce` 经常和 `map` 一起使用，它的输入参数和 `map` 一样，也是一个函数 f 和一个 *iterable*，但是和 `map` 对每个元素做分别处理不一样，`reduce` 的目标是把一列值最终“合并起来”变成一个值。\n",
    "\n",
    "`reduce` 的处理模式是：取列表里前两个值传给函数 f（所以函数 f 必须是两个输入参数的函数），算出一个值，把这个值和列表里下一个（第三个）值一起再传给 f，再算出一个值，然后把这个值和列表里下一个值再传给 f，如此一直下去，直到列表里没有元素位置。这样无论多么长的列表最后都可以被 `reduce` 处理成一个值（这也是 *reduce* 这个词儿的含义）。\n",
    "\n",
    "我们来看几个例子，注意 `reduce` 并不是内置函数（`map` 是，我也不知道为什么这样），它在 Python 的 `functools` 包里，所以需要先 `import`："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面这个 `reduce` 的效果是对这一列数求和，其执行过程是这样的：\n",
    "\n",
    "1. 取列表的前两个数 1 和 2 传给我们构造的匿名函数 `lambda x, y: x + y`，实际上就是做加法，算出 3；\n",
    "2. 把 3 和列表里下一个数 4 一起传给匿名函数，算出 7；\n",
    "3. 把 7 和列表里下一个数 9 一起传给匿名函数，算出 16；\n",
    "4. 把 16 和列表里下一个数 12 一起传给匿名函数，算出 28；\n",
    "5. 由于列表里已经没有数了，28 就是 `reduce` 的最终结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面的这个例子是计算一列值里的最大值，可以自行推演。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意这里有一个 `lambda` 里面特殊的 `if...else` 写法，记住就好。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为什么 `map` `reduce` 很重要而且经常一起出现呢？其实这两个工具组合起来是我们说的“分而治之”的经典模式。\n",
    "\n",
    "Google 最早公开的大规模并行计算系统名字就叫 MapReduce，这个系统能把一个规模很大的任务分解成很多子任务，所有子任务排成一列，然后用 `map` 来对其中每个元素做处理，然后用 `reduce` 把处理结果合起来得到我们要的任务的结果。\n",
    "\n",
    "这么说比较抽象，我们来看一个例子。比如我们要计数一篇文章里有多少个单词（*word*），我们当然可以从头开始一个一个数，但文章很长，这么做要花很长的时间，所以我们把文章分成句子，每个句子作为一个元素，文章就是所有句子组成的列表，类似下面这样（实际上可能有很多句子，我们简化成几句示意好了）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们可以定义一个对句子计数单词的函数（这个实现很粗糙，你可以尝试改进它）："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "然后我们用 `map` 来对列表 `sentences` 里的每个句子进行计数，就会得到一个包含“每句含单词数”的新列表："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "然后我们用 `reduce` 来把这些计数加起来，就得到整篇文章的单词数了："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们可以把一切都写在一行里也没问题，这也是函数式编程经常采用的风格："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Google 采用了一种自己设计的版本的 `map` 和 `reduce`，使得每一次函数调用可以在不同的计算机上并行进行，MapReduce 系统处理了这些计算机交换中间结果的各种逻辑，从而构建了一个强大的并行计算系统，可以运用他们成千上万的计算节点来对海量数据进行操作。\n",
    "\n",
    "之所以可以这么做，其前提是：`map` `reduce` 以及他们执行的函数 `f` 都是纯函数，可以打散了执行，而且无论在哪里、以什么顺序执行都不影响最后的结果。\n",
    "\n",
    "设想一下，如果我们要计数的不是这几个句子，而是上亿网页上的数据，用一般的循环完全没法处理，但是通过函数式 `map` `reduce` 却可以方便的化整为零，充分发挥全球数百万个计算节点的并行计算威力。\n",
    "\n",
    "顺便也要提醒大家，即使不考虑 Google 那样规模的计算问题，仅仅是函数式抽象对问题思考和分解的思路，也值得我们好好学习和运用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### filter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "和 `map` `reduce` 类似，`filter` 也是一种对列表进行处理的工具，其参数也是一个函数 `f` 和一个 *iterable*。\n",
    "\n",
    "`filter` 用函数 `f` 去测试其中每个元素，只有通过测试（函数 `f` 返回为 `True`）的元素才会留下来，其他的就被过滤掉，留下来的元素组成一个新的 *iterable* 返回。你一定也注意到了，和 `map` 一样，这里的 `f` 也必须是一个参数的函数。\n",
    "\n",
    "下面两个例子，第一个过滤掉小于零的值，第二个过滤掉所有奇数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`filter` 经常和 `map` `reduce` 组合使用，比如先用 `map` 对子任务进行处理，然后用 `filter` 过滤掉我们不需要的结果，最后用 `reduce` 把结果组装起来；或者先用 `filter` 过滤掉我们不想处理的任务，然后用 `map` 分别处理，最后用 `reduce` 组装；怎么用都可以，非常灵活。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面三个都是用来对一个序列进行处理的函数工具，另外还有一类函数式工具，是用来“处理”函数的，也就是用一些已知函数来构造新的函数，前面我们举例的 *function composition* 是一个例子，下面再举一个例子。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### partial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`partial` 是用来对函数进行“降参”用的，如果有个现成的函数 `f`，需要两个参数，但是我们做某个操作只能使用一个参数的函数（比如前面的 `map` `reduce` `filter` 都对参数数目有要求），那么我们可以用 `partial` 来把 `f` 的参数减少一个，办法就是把它的某个参数用一个值固定下来。\n",
    "\n",
    "这里有个简单的例子，注意 `partial` 和 `reduce` 一样也在 `functools` 包里，所以需要先引入："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`partial` 的第一个参数是我们要降参的函数，后面是我们要固定的参数及其值，返回一个降参之后的函数。\n",
    "\n",
    "这里 `power(x, y)` 是个计算 `x` 的 `y` 次幂（$x^y$）的函数，我们用 `partial` 将其参数中的 `y` 固定为 `3`，就产生了一个新的单参数函数 `cube`。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 函数装饰器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**装饰器**（*decorator*）是 Python 中很强大的一个特性，允许我们用很简洁的语法来对现存的函数做“装饰”，给它添加新的操作而不需要改变原有函数。\n",
    "\n",
    "*Decorator* 的输入输出都是函数（被“装饰”的函数和“装饰”好的函数），是典型的高阶函数。\n",
    "\n",
    "*Decorator* 是颇为高级的语法特性，但有了前面的基础，现在的你应该就不难理解了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们来考虑一个非常典型的需求：记录日志。我们希望在一个函数被调用之前和之后各记录一条日志，这样可以帮助我们跟踪一些关键函数的执行情况：何时被调用了，有没有正确完成调用，花了多少时间等等。我们当然可以修改这个函数，在它一头一尾加上打印日志的代码，但这样会把已有的函数改的乱七八糟，更好的办法是从原有函数出发构造一个新的函数，就像这样："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个例子里 `greeting()` 是我们想要“装饰”的函数，而 `log_decorator()` 就是一个 *decorator*，它接受一个函数作为参数 f，在自己的函数体里定义了一个**内嵌函数**（*nested function*）`wrapper`，`wrapper` 里在调用函数 `f()` 前后加上了日志的代码，然后返回这个函数。\n",
    "\n",
    "用这个装饰器处理我们原来的 `greeting()` 函数，就得到一个新的支持日志的新函数 `logged_greeting()`，测试结果符合预期。\n",
    "\n",
    "如果只是这样，不过是高阶函数的正常操作，Python 的 *decorator* 更进一步，提供了更简洁优雅的语法，上面的代码的后半段可以写成："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "也就是说可以把定义好的 *decorator* 前面加上一个 `@` 写在函数定义前面，就给下面的函数增加了这个“装饰”。\n",
    "\n",
    "不过这样定义的 *decorator* 有个小问题："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们的函数 `greeting()` 的名字怎么变成了 `wrapper` 了……为了解决这个问题需要一系列特定操作，保持被装饰的函数的名字不变，这些操作你甚至不需要了解，因为 Python 做好了解决方案，只要用就好了，这个解决方案也在 `functools` 模块中，本身就用 *decorator* 实现的，最后标准写法应该是下面这样："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这下一切都完美了，只要在定义装饰器返回的函数前面加上 `@wraps` 这个 *decorator* 就行了。\n",
    "\n",
    "好，以上就是 *decorator* 的基本说明，下面我们来看一些稍微复杂的例子。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 处理被装饰函数的参数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的 `greeting()` 函数既没有参数也没有返回值，但大部分函数是有的，而大多数 *decorator* 需要做到能对各种函数进行处理，所以我们写 *decorator* 时通常把被装饰的函数的参数写成 *arbitrary arguments* 的样式，前面的例子可以进一步优化为下面的样子："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的 `log_decoratot(f)` 可以看做一个模板，你写任何 *decorator* 都可以从这个模板开始，只要换掉 `f()` 调用前后的代码就行了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 带参数的装饰器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "有时候 *decorator* 本身带参数，注意这不是指被装饰的函数的参数，而是 *decorator* 自己的参数。\n",
    "\n",
    "比如我们想让上面的 `log_decorator()` 把函数调用日志写入一个日志文件，日志文件名是作为参数传给 *decorator* 的，这时候我们就需要定义一个带参数的函数，让这个函数返回一个 *decorator* 就行了，是不是有点绕？写出来是下面这样的："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在上面的代码中，函数 'log()' 接受一个指定日志文件路径的参数，返回一个装饰器，我们用它装饰函数 `f1()` 时使用缺省参数，也就是把日志写到 `out.log` 中，而装饰 `f2()` 时则传递了一个 `'out.f2.log'` 参数，也就是把日志写到 `out.f2.log` 文件中。\n",
    "\n",
    "仔细读懂上面的这个例子，别被 `log()` 函数那一串 `return` 搞晕，那每个 `return` 都有自己的含义。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 装饰器类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Decorator* 是个返回函数的函数，函数本身也是对象，我们当然也可以把 *decorator* 写成类，Python 定义了专门的一个方法叫 `__call()__`，拥有这个方法的类可以直接当 *decorator* 用，这样我们就可以利用面向对象的方法来写出一组 *decorator*，实现更好的概念分离和复用。\n",
    "\n",
    "比如我们可以把上面的日志 *decorator* 写成一个类："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意，把 *decorator* 写成类时，被装饰的函数是以实例初始化时的参数方式传递进去的，也就是 `__init__()` 方法中的 `func` 参数，我们把这个参数保存在实例变量 `self.func` 中，并在 `__call__()` 方法中使用。\n",
    "\n",
    "另外我们这里还定义了一个方法 `notify()`，在 `logger` 类的定义中这个方法使用 `print()` 函数把日志信息输出到终端，我们可以定义一个 `logger` 的子类，重新实现这个 `notify()` 方法，把日志信息 Email 给某人，这样就能用面向对象的方式来创建不同层次的 *decorator* 了。\n",
    "\n",
    "如果我们需要一组有共性但又各有特色的 *decorators*，写成父子类是个不错的选择。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 装饰器的价值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "装饰器不仅是一种漂亮的语法糖，它实质上是一种特殊的函数抽象方法，非常有助于我们书写纯函数（*pure functions*）。\n",
    "\n",
    "我们前面讲了 *pure function* 的好处，简单内聚，无副作用，但有些事情不可避免的需要副作用，比如前面举例的想要统计函数调用的次数和时间，想给函数调用前后加上日志记录，或者在函数调用前检查是否拥有访问的权限，等等，这些操作都需要在函数中检查某个外部状态，或者改变某个全局变量的值。\n",
    "\n",
    "类似这些日志啊、权限检查啊，与函数主体目标没有直接联系但又不得不做的全局性功能，有一个术语叫 *cross-cutting concerns*，即“横切式”的功能，而装饰器就是解决这类问题的良药。\n",
    "\n",
    "装饰器把这些 *cross-cutting concerns* 抽离出来写在 *decorator* 中，保持原函数仍聚焦于自己的核心目标，这样就做到了概念责任分离（*separation of concerns*）。\n",
    "\n",
    "这样子一来，程序中大部分函数可以是纯的，而一些麻烦的、不得不依赖副作用的全局 *cross-cutting concerns* 可以在少量 *decorator* 中处理。\n",
    "\n",
    "另外，有些应用框架大量采用 *decorator* 来实现模板化的编程，我们后面会学到的 Web 应用开发框架 Flask 就是一个典型的例子。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 惰性计算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**惰性计算**（*lazy evaluation*）是 *functional* 思想中的另外一个大宝藏，有的专家甚至认为这是最有用的 *functional* 工具之一（参见 *John Hughes* 的名论文 [Why Functional Programming Matters](https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf)）。\n",
    "\n",
    "惰性计算的意思是，一个函数只有在必要时才会计算其返回值。这种技术允许我们定义”虚拟“的无穷序列，但用到哪里算到哪里，不用担心计算机会把自己算死，非常的智能好用。\n",
    "\n",
    "Python 也支持惰性计算，实际上你可能已经想到了，*generator* 就是一种惰性计算的实现。如果你记不太清 *generator* 的事，现在是复习一遍 [Iterable 和 Iterator](7-data-2.ipynb) 的好机会。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Generator* 是一种特殊的函数，它返回一个序列的 *iterator*；*generator* 函数本身定义了这个序列的生成算法，通过 `yield` 关键字的特殊机制，每次调用 *generator* 函数就返回序列里的“下一个值”；这个序列可以是有限的，但更多时候是无限的，反正是一次返回一个值，用到哪儿算到哪儿，这是典型的 *lazy evaluation* 模式。\n",
    "\n",
    "Python 内置函数 `range()` 就是一个 *generator*，当我们调用 `range()` 时只是定义了一个等差数列的规则，而不是全都算出来："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "此时 r 里面只保存了一个定义：“我是从 10 开始的、公差为 4 的等差数列，最大不超过 1000”，至于具体的数，比如第 10 个数是几，是不知道的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可以看到 `range()` 返回的不是一个序列（列表），而是一个特殊的 `range` 类型，其值也只是一个定义；当我们要用到具体的第几个数时，才会把这之前所有数算出来：\n",
    "\n",
    "> `range` 是与 `tuple` 很像的内置类型，它也是有序的数据容器（*sequence*），而且也是 *immutable*，即定义之后不可更改。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面的例子帮助我们理解惰性与非惰性的差别。\n",
    "\n",
    "假设我们要对 0 到 1000万 的整数，每个都做一个运算（比如简单点，就说每个都除以 2 吧），然后把结果放进一个新的列表，我们可以用[前面学过的](8-data-3.ipynb) *list comprehension*："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "运行上面的代码，我们发现哪怕只是访问列表里第二个数，也要计算好一阵子，因为 *list comprehension* 不是惰性的，它实打实的做了一千万个数的计算并生成了完整列表。\n",
    "\n",
    "下面是同样的数列的 *generator* 版本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这次是几乎立刻返回了前两个数，因为 *generator* 是惰性的。上面这个 *generator* 有个更简单的写法："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这种写法叫做 *generator expression*，是 [PEP 289](https://www.python.org/dev/peps/pep-0289/) 定义的。其语法有点像 *comprehension* 但使用小括号 `()` 而不是 `[]`（*list comprehension*）或者 `{}`（*set or dictionary comprehension*）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面的代码分别用 *list comprehension* 和 *generator* 两种方法构造了一个数列，里面是 10000 以下能被 3 或者 5 整除的数，然后我们用 Python 内置模块 `sys` 的 `getsizeof()` 方法来列出两种数列占用内存的大小："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一般来说那些确定范围边界的问题，比如我们要处理 1 到 100 的数字，用一般列表和循环就挺好，但有些问题的边界在计算前不确定，或者干脆就是无穷的，那就是惰性计算擅长的主场了。考虑下面两个例子：\n",
    "\n",
    "1. 计算前 100 个素数，我们其实不知道第 100 个质数有多大，也没法用一个公式算出第 100 个质数，但我们可以定义从 2 开始的所有素数组成的无穷序列；\n",
    "2. 诸如斐波那契（*Fibonacci*）数列这样本身就用递归方式定义的列表，用前几个数算下一个数，这类问题一般都很适合惰性计算。\n",
    "\n",
    "这两个例子我们都在 [Iterable 和 Iterator](7-data-2.ipynb) 一章作为示例给出过 *generator* 解决方案，比如斐波那契数列的 *generator*："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这个 *generator* 定义了无穷的斐波那契数列，然后我们就可以用 `islice()` 这样的工具来计算前 10 个数，由于 *generator* 是惰性的，绝不会多算一个，也不会占用额外的内存："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 请在这里输入代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 小结"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "作为学习 *functional* 思想的入门，本章重点介绍了三个主要的 *functional* 特性：**纯函数**（*pure functions*），**高阶函数**（*higher-order function*）和 **惰性计算**（*lazy evaluation*）。\n",
    "* 纯函数（*pure functions*）是没有副作用且不依赖于外部状态的函数，纯函数对构建“无错软件系统”有很大的帮助；Python 不是纯函数式编程语言，但我们仍应该尽量减少“不纯”的函数，将其限制在可控范围内；\n",
    "* 高阶函数（*higher-order function*）是以函数作为输入参数或返回值的函数，是用来操作函数的函数，一些经典的高阶函数能让我们写出高度精炼而优雅的代码；\n",
    "* 装饰器是一种非常有用的高阶函数，可以处理一些比较棘手的全局性 *cross-cutting concerns*；\n",
    "* 惰性计算（*lazy evaluation*）让我们可以放心的定义无穷序列生成器，专注于序列本身的特征，而不用担心内存和计算时间的消耗，在很多场合都有不可替代的作用。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}