{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 函数进阶：参数传递，高阶函数，lambda 匿名函数，global 变量，递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 函数是基本类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在 `Python` 中，函数是一种基本类型的对象，这意味着\n",
    "\n",
    "- 可以将函数作为参数传给另一个函数\n",
    "- 将函数作为字典的值储存\n",
    "- 将函数作为另一个函数的返回值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def square(x):\n",
    "    \"\"\"Square of x.\"\"\"\n",
    "    return x*x\n",
    "\n",
    "def cube(x):\n",
    "    \"\"\"Cube of x.\"\"\"\n",
    "    return x*x*x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "作为字典的值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "funcs = {\n",
    "    'square': square,\n",
    "    'cube': cube,\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例子："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "8\n",
      "cube 8\n",
      "square 4\n"
     ]
    }
   ],
   "source": [
    "x = 2\n",
    "\n",
    "print square(x)\n",
    "print cube(x)\n",
    "\n",
    "for func in sorted(funcs):\n",
    "    print func, funcs[func](x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 函数参数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 引用传递"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Python` 中的函数传递方式是 `call by reference` 即引用传递，例如，对于这样的用法：\n",
    "\n",
    "    x = [10, 11, 12]\n",
    "    f(x)\n",
    "\n",
    "传递给函数 `f` 的是一个指向 `x` 所包含内容的引用，如果我们修改了这个引用所指向内容的值（例如 `x[0]=999`），那么外面的 `x` 的值也会被改变。不过如果我们在函数中赋给 `x` 一个新的值（例如另一个列表），那么在函数外面的 `x` 的值不会改变："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[999, 2, 3]\n",
      "[999, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "def mod_f(x):\n",
    "    x[0] = 999\n",
    "    return x\n",
    "\n",
    "x = [1, 2, 3]\n",
    "\n",
    "print x\n",
    "print mod_f(x)\n",
    "print x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[4, 5, 6]\n",
      "[1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "def no_mod_f(x):\n",
    "    x = [4, 5, 6]\n",
    "    return x\n",
    "\n",
    "x = [1,2,3]\n",
    "\n",
    "print x\n",
    "print no_mod_f(x)\n",
    "print x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 默认参数是可变的！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "函数可以传递默认参数，默认参数的绑定发生在函数定义的时候，以后每次调用默认参数时都会使用同一个引用。\n",
    "\n",
    "这样的机制会导致这种情况的发生："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def f(x = []):\n",
    "    x.append(1)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "理论上说，我们希望调用 `f()` 时返回的是 `[1]`， 但事实上："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n",
      "[1, 1]\n",
      "[1, 1, 1]\n",
      "[9, 9, 9, 1]\n",
      "[1, 1, 1, 1]\n",
      "[1, 1, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "print f()\n",
    "print f()\n",
    "print f()\n",
    "print f(x = [9,9,9])\n",
    "print f()\n",
    "print f()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "而我们希望看到的应该是这样："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1]\n",
      "[1]\n",
      "[1]\n",
      "[9, 9, 9, 1]\n",
      "[1]\n",
      "[1]\n"
     ]
    }
   ],
   "source": [
    "def f(x = None):\n",
    "    if x is None:\n",
    "        x = []\n",
    "    x.append(1)\n",
    "    return x\n",
    "\n",
    "print f()\n",
    "print f()\n",
    "print f()\n",
    "print f(x = [9,9,9])\n",
    "print f()\n",
    "print f()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 高阶函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以函数作为参数，或者返回一个函数的函数是高阶函数，常用的例子有 `map` 和 `filter` 函数：\n",
    "\n",
    "`map(f, sq)` 函数将 `f` 作用到 `sq` 的每个元素上去，并返回结果组成的列表，相当于：\n",
    "```python\n",
    "[f(s) for s in sq]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map(square, range(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`filter(f, sq)` 函数的作用相当于，对于 `sq` 的每个元素 `s`，返回所有 `f(s)` 为 `True` 的 `s` 组成的列表，相当于：\n",
    "```python\n",
    "[s for s in sq if f(s)]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def is_even(x):\n",
    "    return x % 2 == 0\n",
    "\n",
    "filter(is_even, range(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一起使用："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 4, 16]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map(square, filter(is_even, range(5)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`reduce(f, sq)` 函数接受一个二元操作函数 `f(x,y)`，并对于序列 `sq` 每次合并两个元素："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def my_add(x, y):\n",
    "    return x + y\n",
    "\n",
    "reduce(my_add, [1,2,3,4,5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "传入加法函数，相当于对序列求和。\n",
    "\n",
    "返回一个函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def make_logger(target):\n",
    "    def logger(data):\n",
    "        with open(target, 'a') as f:\n",
    "            f.write(data + '\\n')\n",
    "    return logger\n",
    "\n",
    "foo_logger = make_logger('foo.txt')\n",
    "foo_logger('Hello')\n",
    "foo_logger('World')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello\n",
      "World\n"
     ]
    }
   ],
   "source": [
    "!cat foo.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import os\n",
    "os.remove('foo.txt')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 匿名函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在使用 `map`， `filter`，`reduce` 等函数的时候，为了方便，对一些简单的函数，我们通常使用匿名函数的方式进行处理，其基本形式是：\n",
    "\n",
    "    lambda <variables>: <expression>\n",
    "\n",
    "例如，我们可以将这个："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 4, 9, 16]\n"
     ]
    }
   ],
   "source": [
    "print map(square, range(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用匿名函数替换为："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 4, 9, 16]\n"
     ]
    }
   ],
   "source": [
    "print map(lambda x: x * x, range(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "匿名函数虽然写起来比较方便（省去了定义函数的烦恼），但是有时候会比较难于阅读："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "285\n"
     ]
    }
   ],
   "source": [
    "s1 = reduce(lambda x, y: x+y, map(lambda x: x**2, range(1,10)))\n",
    "print(s1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当然，更简单地，我们可以写成这样："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "285\n"
     ]
    }
   ],
   "source": [
    "s2 = sum(x**2 for x in range(1, 10))\n",
    "print s2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# global 变量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一般来说，函数中是可以直接使用全局变量的值的："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "x = 15\n",
    "\n",
    "def print_x():\n",
    "    print x\n",
    "    \n",
    "print_x()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "但是要在函数中修改全局变量的值，需要加上 `global` 关键字："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18\n",
      "18\n"
     ]
    }
   ],
   "source": [
    "x = 15\n",
    "\n",
    "def print_newx():\n",
    "    global x\n",
    "    x = 18\n",
    "    print x\n",
    "    \n",
    "print_newx()\n",
    "\n",
    "print x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果不加上这句 `global` 那么全局变量的值不会改变："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "x = 15\n",
    "\n",
    "def print_newx():\n",
    "    x = 18\n",
    "    print x\n",
    "    \n",
    "print_newx()\n",
    "\n",
    "print x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "递归是指函数在执行的过程中调用了本身，一般用于分治法，不过在 `Python` 中这样的用法十分地小，所以一般不怎么使用：\n",
    "\n",
    "Fibocacci 数列："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\n"
     ]
    }
   ],
   "source": [
    "def fib1(n):\n",
    "    \"\"\"Fib with recursion.\"\"\"\n",
    "\n",
    "    # base case\n",
    "    if n==0 or n==1:\n",
    "        return 1\n",
    "    # recurssive caae\n",
    "    else:\n",
    "        return fib1(n-1) + fib1(n-2)\n",
    "\n",
    "print [fib1(i) for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一个更高效的非递归版本："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\n"
     ]
    }
   ],
   "source": [
    "def fib2(n):\n",
    "    \"\"\"Fib without recursion.\"\"\"\n",
    "    a, b = 0, 1\n",
    "    for i in range(1, n+1):\n",
    "        a, b = b, a+b\n",
    "    return b\n",
    "\n",
    "print [fib2(i) for i in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "速度比较："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 5.35 ms per loop\n",
      "100000 loops, best of 3: 2.2 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit fib1(20)\n",
    "%timeit fib2(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于第一个递归函数来说，调用 `fib(n+2)` 的时候计算 `fib(n+1), fib(n)`，调用 `fib(n+1)` 的时候也计算了一次 `fib(n)`，这样造成了重复计算。\n",
    "\n",
    "使用缓存机制的递归版本，这里利用了默认参数可变的性质，构造了一个缓存："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]\n",
      "100 loops, best of 3: 5.37 ms per loop\n",
      "100000 loops, best of 3: 2.19 µs per loop\n",
      "The slowest run took 150.16 times longer than the fastest. This could mean that an intermediate result is being cached \n",
      "1000000 loops, best of 3: 230 ns per loop\n"
     ]
    }
   ],
   "source": [
    "def fib3(n, cache={0: 1, 1: 1}):\n",
    "    \"\"\"Fib with recursion and caching.\"\"\"\n",
    "\n",
    "    try:\n",
    "        return cache[n]\n",
    "    except KeyError:\n",
    "        cache[n] = fib3(n-1) + fib3(n-2)\n",
    "        return cache[n]\n",
    "\n",
    "print [fib3(i) for i in range(10)]\n",
    "\n",
    "%timeit fib1(20)\n",
    "%timeit fib2(20)\n",
    "%timeit fib3(20)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}