Func_and_module.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 函数\n",
    "\n",
    "我们之前已经频繁的使用到了函数。\n",
    "\n",
    "函数是一个带有输入和输出的能够完成特定功能的代码块。比如，在某段程序中我们可能需要频繁的使用某一功能，比如，我们可能需要频繁的计算正态分布的密度函数，虽然我们可以使用：\n",
    "```python\n",
    "pi=3.141592654\n",
    "e=2.718\n",
    "sigma=1\n",
    "mu=0\n",
    "f=1/((2*pi)**0.5*sigma)*e**(-1*(x-mu)**2/(2*sigma^2))\n",
    "```\n",
    "\n",
    "进行计算，但是以上计算公式仍然十分复杂，每次碰到都输入不仅麻烦，而且容易犯错。更方便的做法时将以上语句写成一个**函数**（**function**）。\n",
    "\n",
    "在Python中，函数可以方便的使用def来定义，比如，上面计算正态分布的密度函数的函数可以写为："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.39894228037538715\n"
     ]
    }
   ],
   "source": [
    "def normden(x, mu, sigma):\n",
    "    pi = 3.141592654\n",
    "    e = 2.718\n",
    "    f = 1 / ((2 * pi)**0.5 * sigma) * e**(-1 * (x - mu)**2 / (2 * sigma**2))\n",
    "    return f\n",
    "\n",
    "\n",
    "print(normden(0, 0, 1))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在以上语句中，normden是所声明函数的函数名称，后面括号中的“x”、“mu”、“sigma”都是需要用户输入的参数：我们希望计算期望为mu，标准差为sigma的正态分布在x处的密度函数值。\n",
    "\n",
    "在函数的最后，有一个return语句，该语句用以给出函数的返回值：在本例中就是我们计算得到的密度函数值。\n",
    "\n",
    "注意如果需要函数有返回值，必须加入return语句，如果不加，函数默认返回None："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "def normden(x, mu, sigma):\n",
    "    pi = 3.141592654\n",
    "    e = 2.718\n",
    "    f = 1 / ((2 * pi)**0.5 * sigma) * e**(-1 * (x - mu)**2 / (2 * sigma**2))\n",
    "    # return f\n",
    "\n",
    "\n",
    "print(normden(0, 0, 1))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "此外需要注意的时，在调用函数时必须按照声明函数时的参数顺序传入参数，比如在上例中，normden(0,0,1)即对于期望为0，标准差为1的正态分布，计算x=0处的密度函数值，不能将顺序搞错。从而以下调用方式：\n",
    "```python\n",
    "normden(0,1,0)\n",
    "```\n",
    "\n",
    "必然是错的，因为标准差不可能为0。\n",
    "\n",
    "有时对于一个足够复杂的函数，可能会有很多参数值需要传入，而有些参数是允许有默认值的，即使用函数时如果不需要改动可以不改动。此时，我们可以可以在声明函数时就给出默认值，比如，在上例中，如果我们默认计算标准正态分布（期望为0、标注差为1）的密度函数，可以这样写："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.39894228037538715\n"
     ]
    }
   ],
   "source": [
    "def normden(x, mu=0, sigma=1):\n",
    "    pi = 3.141592654\n",
    "    e = 2.718\n",
    "    f = 1 / ((2 * pi)**0.5 * sigma) * e**(-1 * (x - mu)**2 / (2 * sigma**2))\n",
    "    return f\n",
    "\n",
    "\n",
    "print(normden(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果需要指明mu或者sigma的值，只需要在调用时声明即可，比如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.19947114018769357\n"
     ]
    }
   ],
   "source": [
    "print(normden(0, sigma=2))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "就计算了标准差为2、期望为0的正态分布的密度函数值。\n",
    "\n",
    "注意**不可使用列表作为默认的函数参数**，因为列表是一个可变对象（mutable），如果将列表作为默认的函数参数，会导致奇奇怪怪的问题，比如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "[6, 7, 8]\n",
      "[6, 7, 8]\n",
      "[6, 7, 8, 9, 10, 11]\n"
     ]
    }
   ],
   "source": [
    "def plus5(a, b=[]):\n",
    "    print(b)\n",
    "    for aa in a:\n",
    "        b.append(aa + 5)\n",
    "    return b\n",
    "\n",
    "\n",
    "a = [1, 2, 3]\n",
    "print(plus5(a))\n",
    "b = [4, 5, 6]\n",
    "print(plus5(b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python并不像C语言等有很强的类型要求，在Python中定义函数时，并不需要指定输入和输出的数据类型，不过也可以加入类型提示，比如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def add(a: int, b: int) -> int:\n",
    "    return a + b\n",
    "\n",
    "\n",
    "add(3, 4)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其中的“:int”用于标明输入的类型，而“-> int”用于标明输出的类型。不过“类型提示”中的“提示”也代表着，以上的类型要求并不是强制的："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7.8"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add(3.3, 4.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "此外，我们之前提到过，为代码加注释是非常好的习惯，在Python中，由于自定义的函数有可能被其他人使用，而其他人不一定会看源代码，因而注释可能不会被看到。Python提供了一种非常方便的方法，即**文档字符串**（**docstring**），这个字符串仅仅是在函数体内、放在函数开头、不赋值给任何变量的字符串："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Function computing the density function of normal distribution with expection mu and variance sigma at x.\n"
     ]
    }
   ],
   "source": [
    "def normden(x, mu=0, sigma=1):\n",
    "    \"Function computing the density function of normal distribution with expection mu and variance sigma at x.\"\n",
    "    pi = 3.141592654\n",
    "    e = 2.718\n",
    "    f = 1 / ((2 * pi)**0.5 * sigma) * e**(-1 * (x - mu)**2 / (2 * sigma**2))\n",
    "    return f\n",
    "\n",
    "\n",
    "print(normden.__doc__)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "声明了文档字符串后，可以直接使用function.\\_\\_doc\\_\\_进行调阅。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 作用域\n",
    "\n",
    "在创建函数时，必须注意变量的作用域问题。\n",
    "\n",
    "作用域即变量的作用范围。比如，我们在normden()函数中定义了两个变量：pi和e，但是由于这两个变量是在函数体内定义的，因而外界无法使用这两个变量："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "错误： name 'pi' is not defined\n"
     ]
    }
   ],
   "source": [
    "def normden(x, mu=0, sigma=1):\n",
    "    pi = 3.141592654\n",
    "    e = 2.718\n",
    "    f = 1 / ((2 * pi)**0.5 * sigma) * e**(-1 * (x - mu)**2 / (2 * sigma**2))\n",
    "    return f\n",
    "\n",
    "\n",
    "try:\n",
    "    print(pi)\n",
    "except Exception as e:\n",
    "    print(\"错误：\", e)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可见程序出错，并提示pi这个变量没有定义。\n",
    "\n",
    "然而反过来，被定义在函数体外的变量，可以被函数所使用，比如，如果我们写成："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "函数体外，pi= 3.141592654\n",
      "函数体内，pi= 3.141592654\n",
      "0.39894228037538715\n"
     ]
    }
   ],
   "source": [
    "pi = 3.141592654\n",
    "e = 2.718\n",
    "\n",
    "\n",
    "def normden(x, mu=0, sigma=1):\n",
    "    f = 1 / ((2 * pi)**0.5 * sigma) * e**(-1 * (x - mu)**2 / (2 * sigma**2))\n",
    "    print(\"函数体内，pi=\", pi)\n",
    "    return f\n",
    "\n",
    "\n",
    "try:\n",
    "    print(\"函数体外，pi=\", pi)\n",
    "    print(normden(0))\n",
    "except Exception as e:\n",
    "    print(\"错误：\", e)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "不过，如果在函数体内重新定义了pi，则会按照函数体内的定义："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "函数体外，pi= 4\n",
      "函数体内，pi= 3.141592654\n",
      "0.39894228037538715\n"
     ]
    }
   ],
   "source": [
    "pi = 4\n",
    "e = 2.718\n",
    "\n",
    "\n",
    "def normden(x, mu=0, sigma=1):\n",
    "    pi = 3.141592654\n",
    "    e = 2.718\n",
    "    f = 1 / ((2 * pi)**0.5 * sigma) * e**(-1 * (x - mu)**2 / (2 * sigma**2))\n",
    "    print(\"函数体内，pi=\", pi)\n",
    "    return f\n",
    "\n",
    "\n",
    "try:\n",
    "    print(\"函数体外，pi=\", pi)\n",
    "    print(normden(0))\n",
    "except Exception as e:\n",
    "    print(\"错误：\", e)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "另外，如果需要在函数体重更改函数体外定义的变量的值，需要使用global关键字来声明该变量是一个“全局变量”，比如，如果执行如下代码：\n",
    "```python\n",
    "x=1\n",
    "def add1():\n",
    "    x=x+1\n",
    "    print(x)\n",
    "add1()\n",
    "```\n",
    "那么会报错，原因在于在函数add1()内部，“x=”是要给x赋值，那么此时Python会认为这是一个函数体内的局部变量，所以与函数体外的“x=1”这个变量没有关系；然而要给x赋值的值是“x+1”，既然x是局部变量，在“x=x+1”前面并没有定义x，所以Python会认为此时x没有定义。\n",
    "\n",
    "实际上，**只要在函数体里面涉及到对x的重新赋值，Python解释器就会将x解释为函数体内的局部变量**，比如：\n",
    "```python\n",
    "x=1\n",
    "def add1():\n",
    "    a=x+1\n",
    "    x=a\n",
    "    print(x)\n",
    "add1()\n",
    "```\n",
    "同样会报错。\n",
    "\n",
    "解决办法是在使用x之前先用global关键词声明x是全局变量："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "x = 1\n",
    "\n",
    "\n",
    "def add1():\n",
    "    global x\n",
    "    x = x + 1\n",
    "    print(x)\n",
    "\n",
    "\n",
    "add1()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用global关键词声明x是一个“全局”变量，从而接下来引用x时，Python解释器就将其视为函数定义之前的那个x了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## lambda表达式\n",
    "\n",
    "函数虽然好用，但是有一个缺点是，有时语句非常简单，但是我们还需要写def、return等语句。\n",
    "\n",
    "Python提供了一个语法糖，即lambda表达式，可以让我们很方便的在一行以内定义一个函数。比如刚刚计算标准正态分布的密度函数的函数可以定义为："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.39894228037538715\n"
     ]
    }
   ],
   "source": [
    "stdnormden = lambda x: 1 / ((2 * 3.141592654)**0.5) * 2.718**(-1 * (x**2) / 2)\n",
    "print(stdnormden(0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当然，简单的代价是损失方便性，上面的lambda表达式虽然定义了标准正态分布的密度函数，但是并没有定义一般意义的正态分布的密度函数，如果需要传入额外的变量，可以使用："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.19947114018769357\n"
     ]
    }
   ],
   "source": [
    "normden = lambda x, mu, sigma: 1 / (\n",
    "    (2 * 3.141592654)**0.5 * sigma) * 2.718**(-1 * ((x - mu)**2) /\n",
    "                                              (2 * sigma**2))\n",
    "print(normden(0, 0, 2))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在这里，我们不妨回忆一下上一节中有关列表排序的内容，比如对于列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('Messi', 10), ('Xavi', 6), ('ter Stegen', 1), ('Busquets', 5), ('Pique', 3), ('Suárez', 9)]\n"
     ]
    }
   ],
   "source": [
    "player_list = [('Messi', 10), ('Xavi', 6), ('ter Stegen', 1), ('Busquets', 5),\n",
    "               ('Pique', 3), ('Suárez', 9)]\n",
    "print(player_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在该列表的每个元素是一个元组，我们希望的是对每个元组的第二个元素排序。而列表的sort()函数中，key是一个参数，当这个参数不传入任何东西时，默认按照元素值进行排序；但是key参数允许传入一个函数，在进行排序时，先将每个元素带入到key的函数中，计算返回值，再根据返回值排序。比如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('ter Stegen', 1), ('Pique', 3), ('Busquets', 5), ('Xavi', 6), ('Suárez', 9), ('Messi', 10)]\n"
     ]
    }
   ],
   "source": [
    "def sort_list_by_2(t):\n",
    "    return t[1]\n",
    "\n",
    "\n",
    "player_list.sort(key=sort_list_by_2)\n",
    "print(player_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "或者，我们可以使用lambda表达式写成更加简洁的形式："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('Messi', 10), ('Suárez', 9), ('Xavi', 6), ('Busquets', 5), ('Pique', 3), ('ter Stegen', 1)]\n"
     ]
    }
   ],
   "source": [
    "player_list.sort(key=lambda x: x[1], reverse=True)\n",
    "print(player_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python中的函数式编程\n",
    "\n",
    "可能有心的读者已经注意到了，函数是可以通过等号赋予某一个变量的，甚至可以传入另外一个函数。\n",
    "\n",
    "实际上在Python中也吸收了函数式编程的一些特点，函数也是“一等公民”，跟数字、字符串一样，也可以传给一个变量、当做参数传入给另外一个函数。比如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.39894228037538715\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "def normden(x, mu=0, sigma=1):\n",
    "    pi = 3.141592654\n",
    "    e = 2.718\n",
    "    f = 1 / ((2 * pi)**0.5 * sigma) * e**(-1 * (x - mu)**2 / (2 * sigma**2))\n",
    "    return f\n",
    "\n",
    "\n",
    "normden2 = normden\n",
    "print(normden2(0))\n",
    "print(normden2 is normden)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的代码中，我们将已经声明的一个函数normden()赋值给了另一个变量,normden2，并使用normden2计算了0处的密度函数值。\n",
    "\n",
    "此外，我们还是用is关键字判断两者是否指代一个对象，发现两者实际上指代的同一个对象，是完全等价的。\n",
    "\n",
    "以下展示了将函数作为参数传递给另外一个函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.159154943071114\n"
     ]
    }
   ],
   "source": [
    "def normden(x, mu=0, sigma=1):\n",
    "    pi = 3.141592654\n",
    "    e = 2.718\n",
    "    f = 1 / ((2 * pi)**0.5 * sigma) * e**(-1 * (x - mu)**2 / (2 * sigma**2))\n",
    "    return f\n",
    "\n",
    "\n",
    "def den2(f, x):\n",
    "    return f(x)**2\n",
    "\n",
    "\n",
    "print(den2(normden, 0))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以上程序中，我们定义了一个新的函数，den2()，该函数接受两个参数：f和x，其中f为一个函数，可用来计算f(x)，并返回f(2)\\*\\*2。\n",
    "\n",
    "随后，我们将刚刚定义的normden()函数以及x=0传入了den2()函数，计算得到了具体数值。\n",
    "\n",
    "## 递归\n",
    "\n",
    "**递归**（**recursion**）是函数是函数值编程一个非常有意思的应用，即一个函数调用其本身。\n",
    "\n",
    "比如，为了计算阶乘，我们通常会使用循环："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "def factorial(n):\n",
    "    frcn = 1\n",
    "    for i in range(n):\n",
    "        frcn *= (i + 1)\n",
    "    return frcn\n",
    "\n",
    "\n",
    "print(factorial(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果使用递归的思路，我们可以这么写："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "def factorial(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return n * factorial(n - 1)\n",
    "\n",
    "\n",
    "print(factorial(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在以上程序中，我们定义了一个函数factorial()，接受一个数字作为参数：只要该参数不为1，就继续往下乘，直到编程1为止。因而，factorial(5)具体执行了：\n",
    "\n",
    "1. factorial(5), 计算5\\*factorial(4)\n",
    "1. factorial(4), 计算4\\*factorial(3)\n",
    "1. factorial(3), 计算3\\*factorial(2)\n",
    "1. factorial(2), 计算2\\*factorial(1)\n",
    "1. factorial(1)=1\n",
    "1. 最终依次返回"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接下来我们展示了一个二分查找的例子，可以证明，以下的二分查找比线性查找更加快速。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Messi\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "player_list = [('Messi', 10), ('Xavi', 6), ('ter Stegen', 1), ('Busquets', 5),\n",
    "               ('Pique', 3), ('Suárez', 9)]\n",
    "player_list.sort(key=lambda x: x[1])\n",
    "\n",
    "\n",
    "def search(num, name_list):\n",
    "    l = len(name_list)\n",
    "    if l == 1:\n",
    "        if name_list[0][1] == num:\n",
    "            return name_list[0][0]\n",
    "        else:\n",
    "            return None\n",
    "    else:\n",
    "        l2 = l // 2\n",
    "        if name_list[l2 - 1][1] < num:\n",
    "            return search(num, name_list[l2:])\n",
    "        else:\n",
    "            return search(num, name_list[0:l2])\n",
    "\n",
    "\n",
    "print(search(10, player_list))\n",
    "print(search(11, player_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "类似的，以下代码使用递归实现了因数分解，即将任何一个数字分解为质数的乘机："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 2, 2, 2, 2, 17, 59, 45817, 140589937]\n"
     ]
    }
   ],
   "source": [
    "def factorize(x):\n",
    "    plist=[]\n",
    "    if x==1:\n",
    "        return list()\n",
    "    i=1\n",
    "    found=False\n",
    "    if x%2==0:\n",
    "        plist.append(2)\n",
    "        plist.extend(factorize(int(x/2)))\n",
    "        found=True\n",
    "    else:\n",
    "        while 2*i+1<=(x/(2*i+1)):\n",
    "            b=2*i+1\n",
    "            if x%b==0:\n",
    "                plist.extend(factorize(b))\n",
    "                plist.extend(factorize(int(x/b)))\n",
    "                found=True\n",
    "                break\n",
    "            i+=1\n",
    "    if not found:\n",
    "        plist.append(x)\n",
    "    return plist\n",
    "print(factorize(310115201806060197))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## map()、reduce()以及filter()\n",
    "\n",
    "函数式编程另外比较常用的特性时map()、reduce()、filter等函数。\n",
    "\n",
    "其中，map(func, list)函数接受一个函数func和一个列表list，其作用是将函数func作用与list的每一个元素中。\n",
    "\n",
    "值得注意的是，map()语句之后，计算并不会立即执行，而是会返回一个可迭代的对象，等到需要计算值时才进行计算，比如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "<map object at 0x7f206837cbe0>\n",
      "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]\n"
     ]
    }
   ],
   "source": [
    "num_list = list(range(10))\n",
    "print(num_list)\n",
    "num_sq_list = map(lambda x: x**2, num_list)\n",
    "print(num_sq_list)\n",
    "num_sq_list = list(num_sq_list)\n",
    "print(num_sq_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在以上程序中，我们先使用range()函数产生了一个0...9的列表，接着使用map函数，计算了每个元素的平方。注意到map()函数被调用之后，计算并没有立即执行，返回的是一个map对象。该对象是可迭代的，因而我们可以使用list()函数将其转化为列表。\n",
    "\n",
    "或者，更常用的，我们可能会使用reduce()以及filter()函数处理map对象。其中：\n",
    "\n",
    "* reduce(func,iterable_obj)接受一个二元函数，以及一个可迭代的对象iterable_obj，该函数使用func函数依次计算iterable_obj每个的值。\n",
    "    - 比如，如果iterable_obj=\\[x1,x2,x3,x4\\]，那么reduce()函数计算的是：func(func(func(x1,x2),x3),x4)\n",
    "* filter(func,iterable_ojb)接受一个逻辑函数，以及一个可迭代的对象iterable_obj，该函数的作用是将iterable_obj中带入func返回值为True的子集挑出来。\n",
    "\n",
    "\n",
    "\n",
    "比如，以下使用reduce() 函数计算了一个列表的和："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "\n",
    "num_list = [1, 3, 8, 6, 9]\n",
    "sums = reduce(lambda x, y: x + y, num_list)\n",
    "print(sums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以下使用reduce() 函数计算了一个列表的最大值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "\n",
    "num_list = [1, 3, 8, 6, 9]\n",
    "sums = reduce(lambda x, y: max(x, y), num_list)\n",
    "print(sums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以下使用reduce() 函数计算了0...9的平方和："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "285\n"
     ]
    }
   ],
   "source": [
    "num_list = list(range(10))\n",
    "num_sq_list = map(lambda x: x**2, num_list)\n",
    "sum_sq = reduce(lambda x, y: x + y, num_sq_list)\n",
    "print(sum_sq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以下则挑出了所有1,...,9的平方中的所有的能被3整除的数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 9, 36, 81]\n"
     ]
    }
   ],
   "source": [
    "num_list = list(range(10))\n",
    "num_sq_list = map(lambda x: x**2, num_list)\n",
    "sub_sq = filter(lambda x: x % 3 == 0, num_sq_list)\n",
    "print(list(sub_sq))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 闭包\n",
    "\n",
    "我们前面已经看到，函数可以作为另一个函数的输入，与此同时，函数还可以作为另一个函数的输出。**闭包**（**closure**）在Python中可以简单的看做是一个返回函数的函数。\n",
    "\n",
    "在比较复杂的设计模式中，闭包使用起来非常方便，比如**修饰器**（**decorator**）就是使用闭包创建的。\n",
    "\n",
    "在这里我们讲一个小例子来帮助理解这个概念。\n",
    "\n",
    "我们知道在统计学中有不同的平均数的概念，比如：\n",
    "\n",
    "* 算术平均：$$\\bar{x}=\\frac{1}{N}\\sum_{i=1}^{N}x_i$$\n",
    "* 几何平均：$$\\tilde{x}=\\exp\\left[\\frac{1}{N}\\sum_{i=1}^{N}\\ln\\left(x_i\\right)\\right]$$\n",
    "* 调和平均：$$\\bar{\\bar{x}}=\\left[\\frac{1}{N}\\sum_{i=1}^{N}x_i^{-1}\\right]^{-1}$$\n",
    "\n",
    "实际上对于任意的单调函数$f\\left(x\\right)$，我们都可以定义一个新的平均数：$$\\tilde{\\tilde{x}}=f^{-1}\\left[\\frac{1}{N}\\sum_{i=1}^{N}f\\left(x_i\\right)\\right]$$如果$f\\left(x\\right)=x$，那就是算术平均；如果$f\\left(x\\right)=\\ln\\left(x\\right)$，那就是集合平均；如果$f\\left(x\\right)=x^{-1}$，那就是调和平均。\n",
    "\n",
    "那么我们能不能写一个抽象的函数，只要给出$f\\left(x\\right)$和$f^{-1}\\left(x\\right)$，就能给出算平均的函数呢？当然可以："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.0\n",
      "2.6051710846973517\n",
      "2.18978102189781\n",
      "3.842476483503493\n"
     ]
    }
   ],
   "source": [
    "def general_mean(f, finv):\n",
    "\n",
    "    def mean_func(x):\n",
    "        fx = map(f, x)\n",
    "        mean_fx = sum(fx)\n",
    "        mean_fx /= len(x)\n",
    "        mean = finv(mean_fx)\n",
    "        return mean\n",
    "\n",
    "    return mean_func\n",
    "\n",
    "\n",
    "a = [1, 2, 3, 4, 5]\n",
    "##简单平均\n",
    "mean = general_mean(lambda x: x, lambda x: x)\n",
    "print(mean(a))\n",
    "##几何平均\n",
    "import math\n",
    "\n",
    "mean = general_mean(math.log, math.exp)\n",
    "print(mean(a))\n",
    "##调和平均\n",
    "mean = general_mean(lambda x: 1 / x, lambda x: 1 / x)\n",
    "print(mean(a))\n",
    "##奇奇怪怪的平均\n",
    "mean = general_mean(math.exp, math.log)\n",
    "print(mean(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以上代码中使用闭包，通过带入不同的$f\\left(x\\right)$和$f^{-1}\\left(x\\right)$，得到了不同的平均函数。这样做的好处是抽象化：我们只需要定义各种平均数中的单调函数，就可以不用重复写同样的代码并计算均值。这在处理复杂任务时可以非常有效的降低代码量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 模块\n",
    "\n",
    "注意我们在使用reduce()函数时，多加了一句：\n",
    "```python\n",
    "from functools import reduce\n",
    "```\n",
    "\n",
    "原因是由于reduce()并非Python內建的函数，需要从functools这个模块中调用。functools这个模块是Python自带的，无需安装。\n",
    "\n",
    "\n",
    "在Python中，**模块** （ **module** ）通常是一个Python文件，在该文件中定义了很多函数、类、常数等供我们使用。\n",
    "\n",
    "而 **包** （ **package** ）是一个目录，包中可以有很多的模块。\n",
    "\n",
    "我们之前曾经讲过，使用类似“pip install bs4”之类的命令安装包，安装好之后就可以供我们在Python程序中调用。\n",
    "\n",
    "如果需要使用某个模块，可以直接使用“import”命令。比如，我们经常使用的带有一些数学函数的math模块："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "e: 2.718281828459045\n",
      "pi: 3.141592653589793\n",
      "sin(1): 0.8414709848078965\n",
      "log(2): 0.6931471805599453\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "print(\"e:\", math.e)\n",
    "print(\"pi:\", math.pi)\n",
    "print(\"sin(1):\", math.sin(1))\n",
    "print(\"log(2):\", math.log(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意在上面我们在使用math模块中的元素时，都加了math.的前缀，这是由于Python中的命名空间导致的，为了防止在不同的地方定义了相同的函数名等。比如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "e in math: 2.718281828459045\n",
      "e: 3\n",
      "pi in math: 3.141592653589793\n",
      "pi: 4\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "e = 3\n",
    "pi = 4\n",
    "print(\"e in math:\", math.e)\n",
    "print(\"e:\", e)\n",
    "print(\"pi in math:\", math.pi)\n",
    "print(\"pi:\", pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了防止混乱，特地使用math.前缀作为区分。\n",
    "\n",
    "如果需要同时导入多个模块，可以直接用逗号隔开，比如以下程序我们使用梯形公式计算了标准正态分布函数从-1.96到1.96的数值积分："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "integral= 0.9500039163481592\n"
     ]
    }
   ],
   "source": [
    "import math, functools\n",
    "\n",
    "\n",
    "def normden(x, mu=0, sigma=1):\n",
    "    f = 1 / (math.sqrt(2 * math.pi) * sigma) * math.exp(-1 * (x - mu)**2 /\n",
    "                                                        (2 * sigma**2))\n",
    "    return f\n",
    "\n",
    "\n",
    "N = 1000\n",
    "x = [-1.96 + (1.96 * 2) / N * i for i in range(N)]\n",
    "# print(x)\n",
    "integral = functools.reduce(lambda a, b: a + b,\n",
    "                            map(lambda z: normden(z) * (1.96 * 2) / N, x))\n",
    "print(\"integral=\", integral)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意到，我们使用import 语句同时导入了functools以及math两个模块，因而在这里我们需要使用functools.reduce来表示reduce()函数。\n",
    "\n",
    "当然，我们也看到了，可以直接使用： from ... import ... 的语法来导入模块中的某一个元素，比如from functools import reduce就从functools模块中导入了reduce函数，且reduce函数使用时不需要再加functools.前缀。\n",
    "\n",
    "当然，不需要前缀的代价是要小心不要覆盖已经导入的东西，比如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.141592653589793\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "from math import pi\n",
    "\n",
    "print(pi)\n",
    "pi = 4\n",
    "print(pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "此外，import 语句还可以为导入的东西起别名，比如 import math as m，以后就可以使用m.sin()、m.e、m.pi、m.log()、m.exp()等替代math.sin() 等等。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "e in math: 2.718281828459045\n",
      "e: 3\n",
      "pi in math: 3.141592653589793\n",
      "pi: 4\n"
     ]
    }
   ],
   "source": [
    "import math as m\n",
    "\n",
    "e = 3\n",
    "pi = 4\n",
    "print(\"e in math:\", m.e)\n",
    "print(\"e:\", e)\n",
    "print(\"pi in math:\", m.pi)\n",
    "print(\"pi:\", pi)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}