03_Functional_Programming.ipynb

{
 "metadata": {
  "celltoolbar": "Slideshow",
  "name": "",
  "signature": "sha256:fd19691bf35a6c513ecfa0b7f95cd106f3075ba1e39de36b8641b2dd2da2efa2"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Functional Programming And Programming With Functions\n",
      "====================================================="
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "What is a computer program?\n",
      "---------------------------\n",
      "\n",
      "+ Do Instruction 1\n",
      "+ Do Instruction 2\n",
      "+ Do Instruction 3\n",
      "+ Do Instruction 1\n",
      "+ Do Instruction 2\n",
      "+ Do Instruction 3\n",
      "\n",
      "This is called an _imperative_ style of programming."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Functions conceptually help divide up tasks and make it easier to do things repeatedly and more concicely:\n",
      "\n",
      "+ Define Function 1\n",
      "    + Instruction 1\n",
      "    + Instruction 2\n",
      "    + Instruction 3\n",
      "+ Do Function 1\n",
      "+ Do Function 1\n",
      "\n",
      "Functions can also be used to define the program as a whole."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Functional programming\n",
      "----------------------\n",
      "\n",
      "+ In an imperative programming style we are concerned with *how* the program achieves the end result. \n",
      "+ Functional programming helps us to focus more on *what* the end result is. \n",
      "+ An imperative program will describe how the **state** of the program is updated by the commands, or _statements_, and the order to execute them; \n",
      "    + in functional style the order is not important.\n",
      "\n",
      "+ Functional programming essentialy breaks the code down into smaller functions, or _expressions_, that take only input and produce an output that is not dependent on the state of the system.\n",
      "    + _The function will always produce the same output for a given input._\n",
      "\n",
      "+ Whereas an imperative program will be a series of expressions for the computer to execute a pure functional program will be a series of definitions of the functions and a single expression that returns the result of the program.\n",
      "\n",
      "    + Intput -> Function 1 -> Function 2 -> Function 3 -> Output"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "This part was inspired from several sources. For further, in-depth reading, you can find them here:\n",
      "\n",
      "* [http://docs.python.org/2/howto/functional.html](http://docs.python.org/2/howto/functional.html)\n",
      "* [http://www.ibm.com/developerworks/linux/library/l-prog/index.html](http://www.ibm.com/developerworks/linux/library/l-prog/index.html)\n",
      "* [http://www-inst.eecs.berkeley.edu/~cs61a/sp12/book/functions.html](http://www-inst.eecs.berkeley.edu/~cs61a/sp12/book/functions.html)\n",
      "* [http://ua.pycon.org/static/talks/kachayev/#/](http://ua.pycon.org/static/talks/kachayev/#/)\n",
      "\n",
      "The functional approach varies by user and this lesson will be a bit of an amalgamation.\n",
      "\n",
      "If you decide that you love functional programming and want more purity in your life, you can try: F#, Haskell, Erlang, Common Lisp, OCaml..."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "As a scientist, functional programming offers benefits in terms of clearly defining the mathematical parts of your problems, but can also place severe limitations on the ability to process data and deal with inherently stateful problems. With Python we can get the best of both worlds by applying functional paradigms where they are appropriate."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Some benefits of a functional style are:\n",
      "\n",
      "+ Modularity\n",
      "    + Forces consideration of how to break up code into smaller blocks\n",
      "    + Helps to enforce DRY (Don't Repeat Yourself)\n",
      "+ Debugging and testing\n",
      "    +  Each function can be tested individually\n",
      "    + Errors are easily traceable to the function level as everything else is invariant\n",
      "+ Formal provability\n",
      "    + Some of the restrictive aspects that we will encounter enable mathematical proof of the correctness of programs.\n",
      "    > Beware of bugs in the above code; I have only proved it correct, not tried it.\n",
      "    > &mdash; <cite>Donald Knuth</cite>"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Functions\n",
      "---------\n",
      "\n",
      "Functions have input (arguments) and return an output. A **pure function** has no effects besides returning a value:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "abs(-3)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "3"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "In Python the function is 'called' by the brackets (); anything in the brackets becomes the input of the function, and the function '**return**'s an output.\n",
      "\n",
      "A pure function can just be replaced by the output value, this is called _referential transparency_.\n",
      "\n",
      "Since the output can replace the function, we can chain functions as input to other functions:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from math import exp, sqrt\n",
      "\n",
      "sqrt(exp(abs(-3)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "4.4816890703380645"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from __future__ import print_function\n",
      "\n",
      "print(abs(-3))\n",
      "print(print(abs(-3)))"
     ],
     "language": "python",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "3\n",
        "3\n",
        "None\n"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Here, we have converted `print` to a *function* from a *statement* (this will be useful later). The return value of the `abs` function is passed to `print` which has the job of displaying the output. The display of the value is called a *side effect*; the print function does not return any value, so if we try to print it's output we get `None` which is the empty, or null value in Python. Functions return `None` if they have no other return value.\n",
      "\n",
      "A pure function cannot have any side effects, this includes I/O and interacting with a global state. We will need side effects later, and these will be a key component of object oriented programming, but often key components to code can benefit from a more functional approach."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Functions\n",
      "---------\n",
      "\n",
      "Functions can be:\n",
      "\n",
      "* designed to take multiple values\n",
      "* require order in their arguments\n",
      "* replace the common infix notations\n",
      "* be nested"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "max(7.5, 9.5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "9.5"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "pow(4, 5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "1024"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "pow(5, 4)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "625"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from operator import add, mul, sub\n",
      "\n",
      "add(mul(3, 5), sub(12, 33))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "-6"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Operators\n",
      "---------\n",
      "\n",
      "The standard mathematical operators are, of course, available in Python, but importing their functional counterparts from the operator mudule can make functional programming clearer and can help reduce confusion about mathematical precedence and can be passed around as first class citizens. It is up to you which notation you use, just be aware that sometimes one may be more appropriate that the other."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Is it easy to tell what is going on here?\n",
      "7 + 3 * 4 - 8 ** 2 / 6 + 4 - 3 * 12"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "-23"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from operator import add, mul, sub, div\n",
      "\n",
      "# How about here?\n",
      "sub(add(sub(add(7, mul(3, 4)), div(pow(8, 2), 6)), 4), mul(3, 12))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "-23"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Defining functions\n",
      "------------------\n",
      "\n",
      "Python defines a number of functions, and the standard operators are available as functions from the operator module, as shown above as well as functions from many other modules. To be useful, we also need to be able to define our own functions, which is done with the `def` statement:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def square(number):\n",
      "    \"\"\"Return the number multiplied by itself.\"\"\"\n",
      "    return mul(number, number)\n",
      "\n",
      "def square_square(number):\n",
      "    \"\"\"Calculate the square of the square of a number.\"\"\"\n",
      "    return square(square(number))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "-"
      }
     },
     "source": [
      "We should always choose a function_name that is descriptive, and document things properly (coming later). The colon starts a block which is defined by the indentation, and we return the result of the function."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "square_square"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "<function __main__.square_square>"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "square_square(202)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "1664966416"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Be careful to avoid functions that depend on global conditions as these reduce clarity for someone reading or using your code."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# try to restrict globals to CONSTANT values like physical constants\n",
      "global_thing = 12\n",
      "\n",
      "def bad_function(number):\n",
      "    \"\"\"A terrible function that gives you different answers depending on a global condition.\"\"\"\n",
      "    return add(global_thing, number)\n",
      "\n",
      "print(bad_function(5))\n",
      "\n",
      "global_thing = -3\n",
      "\n",
      "# pure functional code produces the same output for identical input\n",
      "# this snippet is BAD and does not!\n",
      "print(bad_function(5))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "17\n",
        "2\n"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Scope\n",
      "-----\n",
      "\n",
      "Scope defines the region of the code where a name is defined, and is closeley related to blocks:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# global_variables defined in the outer scope\n",
      "global_variable = 'foo'\n",
      "another_global = 'foo_too'\n",
      "\n",
      "def function():\n",
      "    \"\"\"Demonstration of scoped varibles.\"\"\"\n",
      "    # Scope can be any block, such as a definition or a loop\n",
      "    \n",
      "    # variables are accessible to any scope within them\n",
      "    print(\"global_variable, in function: {}\".format(global_variable))\n",
      "    \n",
      "    # reassigning within a local scope creates a new local variable \n",
      "    # that shadows the outer one\n",
      "    another_global = 'bar'\n",
      "    print(\"another_global, in function: {}\".format(another_global))\n",
      "    \n",
      "    # local variables are only available in the scope that they are defined in\n",
      "    local_variable = 'baz'\n",
      "    \n",
      "    print(\"local_variable, in function: {}\".format(local_variable))\n",
      "\n",
      "    def inner_function():\n",
      "        \"\"\"A closure.\"\"\"\n",
      "        # a function within a function that contains a reference to \n",
      "        # an outer local variable is called a closure\n",
      "        closured_variable = local_variable\n",
      "\n",
      "function()\n",
      "\n",
      "print(\"another_global, unchanged in outer_scope: {}\".format(another_global))\n",
      "#print(\"local_variable, in outer_scope: {}\".format(local_variable))\n",
      "# Will result in an error as the variable is not assigned in this scope\n",
      "# NameError: name 'local_variable' is not defined"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "global_variable, in function: foo\n",
        "another_global, in function: bar\n",
        "local_variable, in function: baz\n",
        "another_global, unchanged in outer_scope: foo_too\n"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Properties of functions\n",
      "-----------------------\n",
      "\n",
      "Functions are an abstraction, this means that whatever calls your function shouldn't care about what goes on inside it. This keeps the code partitioned, and allows you to freely update the inner workings without breaking other parts that depend on the output of the function."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def square(number):\n",
      "    \"\"\"Multiply the number by itself.\"\"\"\n",
      "    return add(mul(sub(number, 1), number), number)\n",
      "\n",
      "square(12)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 15,
       "text": [
        "144"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Functions are '_first class_' in Python (a prefequisite of functional programming) which means you can return then from another function or pass them around as arguments. They act like everything else."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def powerer(power):\n",
      "    \"\"\"Create a function that will raise numbers to a specific power.\"\"\"\n",
      "    def new_pow(number):\n",
      "        \"\"\"Raise number to the power %s.\"\"\" % power\n",
      "        return pow(number, power)\n",
      "    return new_pow"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "squarer = powerer(2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "squarer(20)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 18,
       "text": [
        "400"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The `powerer` function here gives a *parital* function as we have fixed one of the arguments to the `pow` function. This is similar to a FP technique known as currying. Currying is not so useful in Python, so we'll skip it; feel free to look it up though.\n",
      "\n",
      "`powerer` also demonstrates a *closure*, this is where the function that it creates, `new_pow` knows about what created it, because the `power` argument is carried from the outer scope."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "If we find ourselves doing the same thing repeatedly with different functions, we can define functions that take functions as arguments and will do that for us."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def double_funcinate(function, argument):\n",
      "    \"\"\"Apply the function twice to the argument.\"\"\"\n",
      "    return function(function(argument))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "double_funcinate(squarer, 33)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 20,
       "text": [
        "1185921"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Recursion\n",
      "---------\n",
      "\n",
      "The traditional first program for a language in programming, the \"Hello, World!\", is not something that you can do in pure functional programming. Instead we could look at a factorial, this implementation relies on recursion, a common style in functional programming.\n",
      "\n",
      "Recursion is where a function calls itself."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from operator import sub, mul, eq\n",
      " \n",
      "def factorial(n):\n",
      "    \"\"\"Recursive factorial\"\"\"\n",
      "    if eq(n, 0):\n",
      "        return 1\n",
      "    else:\n",
      "        # The function calls itself\n",
      "        return mul(n, factorial(sub(n, 1)))\n",
      "\n",
      "factorial(7)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "5040"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Lambdas\n",
      "-------\n",
      "\n",
      "A lambda is an anonymous function, they can help you to put code near to where the logic requires it, but they can be hard to interpret and there is nothing that you can do with lambdas that you cannot do without them. You define arguments on the left and the operations after the colon."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# gives you a function that calculates 3*x - 2*y\n",
      "lambda x, y: sub(mul(x, 3), mul(y, 2))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 22,
       "text": [
        "<function __main__.<lambda>>"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "bound_lambda = lambda x, y: sub(mul(x, 3), mul(y, 2))\n",
      "\n",
      "bound_lambda(3, 4)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 23,
       "text": [
        "1"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "double_funcinate(lambda x: add(x, 10), 30)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 24,
       "text": [
        "50"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Iterators\n",
      "---------\n",
      "\n",
      "Functional programs often deal with *streams* of data. A collection of data can be a finite set or an infinite sequence."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "items = [1, 2, 7.4, \"stuff\"]\n",
      "it = iter(items)\n",
      "next(it)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 25,
       "text": [
        "1"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "next(it)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 26,
       "text": [
        "2"
       ]
      }
     ],
     "prompt_number": 26
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "The list, enclosed by square brackets, is one of the most useful datatypes in Python, but it can be dangerous from a functional point of view. In pure FP there are no _mutable_ types and we should not be modifying lists in place, a function should return a new list."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from operator import iadd\n",
      "\n",
      "def join_lists(left, right):\n",
      "    \"\"\"Join two lists.\"\"\"\n",
      "    # iadd adds the second argument to the first in-place\n",
      "    iadd(left, right)\n",
      "    # BAD!!\n",
      "    # left is different from when it started\n",
      "\n",
      "from operator import concat\n",
      "\n",
      "def nice_join(left, right):\n",
      "    \"\"\"Join two lists.\"\"\"\n",
      "    return concat(left, right)\n",
      "    # BETTER\n",
      "    # returns a new list\n",
      "\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 27
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Mutability is a key component in object-oriented programming, as we will see, but we lose referential transparency. In Python functions our data can be modified in undocumented ways, so always ensure that it is clear in your code what is going on. Unfortuantely it is easy to do bad things with mutable data in Python."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "global_list = [1, 2, 4, 6, 7]\n",
      "\n",
      "def bad_global_muter(value_list):\n",
      "    \"\"\"Do bad things to a mutable global list.\"\"\"\n",
      "    # hilarious if someone depends on the global, LOL\n",
      "    iadd(global_list, value_list)\n",
      "    return global_list\n",
      "\n",
      "print(global_list)\n",
      "\n",
      "bad_global_muter([22, 13])\n",
      "\n",
      "print(global_list)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[1, 2, 4, 6, 7]\n",
        "[1, 2, 4, 6, 7, 22, 13]\n"
       ]
      }
     ],
     "prompt_number": 28
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Working with iterators\n",
      "----------------------\n",
      "\n",
      "Some of the basic inbuilt functions that operate on iterators are `map`, `filter` and `reduce`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "map(square, range(10))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 29,
       "text": [
        "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
       ]
      }
     ],
     "prompt_number": 29
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is also where a `print` function comes in useful, or other in-place functions."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "map(print, range(10))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n",
        "1\n",
        "2\n",
        "3\n",
        "4\n",
        "5\n",
        "6\n",
        "7\n",
        "8\n",
        "9\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 30,
       "text": [
        "[None, None, None, None, None, None, None, None, None, None]"
       ]
      }
     ],
     "prompt_number": 30
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from operator import mod, eq\n",
      "\n",
      "# a lambda can keep the logic where it is applied\n",
      "filter(lambda x: eq(mod(x, 2), 0), range(10))"
     ],
     "language": "python",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 31,
       "text": [
        "[0, 2, 4, 6, 8]"
       ]
      }
     ],
     "prompt_number": 31
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# lambdas do get messy, it is probaby better to define an explicit function:\n",
      "def even(number):\n",
      "    \"\"\"Return True for an even number.\"\"\"\n",
      "    return eq(mod(number, 2), 0)\n",
      "\n",
      "filter(even, range(10))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 32,
       "text": [
        "[0, 2, 4, 6, 8]"
       ]
      }
     ],
     "prompt_number": 32
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "reduce(add, range(10))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 33,
       "text": [
        "45"
       ]
      }
     ],
     "prompt_number": 33
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "List comprehensions\n",
      "-------------------\n",
      "\n",
      "Whilts these are useful to demonstrate functional concepts, Python also has list comprehensions which achive the same thing in a subjectively clearer and more versatile manner."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[square(x) for x in range(10)]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 34,
       "text": [
        "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
       ]
      }
     ],
     "prompt_number": 34
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[x for x in range(10) if eq(mod(x, 2), 0)]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 35,
       "text": [
        "[0, 2, 4, 6, 8]"
       ]
      }
     ],
     "prompt_number": 35
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sum(range(10))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 36,
       "text": [
        "45"
       ]
      }
     ],
     "prompt_number": 36
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As shown above, the `for` statement is used to consume an iterator. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for x in range(10):\n",
      "    print(x)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n",
        "1\n",
        "2\n",
        "3\n",
        "4\n",
        "5\n",
        "6\n",
        "7\n",
        "8\n",
        "9\n"
       ]
      }
     ],
     "prompt_number": 37
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Generator expressions\n",
      "---------------------\n",
      "\n",
      "Similar to the list comprehension is the generator expression. Each of these expressions generates a list, but when we have large (or infinite) datasets, memory usage can be excessive. Using round brackets in a list comprehension creates a _lazy_ generator instead."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(square(x) for x in range(10))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 38,
       "text": [
        "<generator object <genexpr> at 0x2f0aeb0>"
       ]
      }
     ],
     "prompt_number": 38
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The result still iterates, but is only evaluated as it is needed."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sum(_)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 39,
       "text": [
        "285"
       ]
      }
     ],
     "prompt_number": 39
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Lazy evaluation is possible with functions by `yield`ing values rather than `return`ing them. Values are only calculated as they are needed."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def square_range(stop):\n",
      "    \"\"\"Return squares of numbers from 1 to stop.\"\"\"\n",
      "    for x in range(stop):\n",
      "        yield square(add(x, 1))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 40
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "square_range(10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 41,
       "text": [
        "<generator object square_range at 0x3139190>"
       ]
      }
     ],
     "prompt_number": 41
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "square_range(10).next()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 42,
       "text": [
        "1"
       ]
      }
     ],
     "prompt_number": 42
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(square_range(10))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 43,
       "text": [
        "[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]"
       ]
      }
     ],
     "prompt_number": 43
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Generators also allow us to create infinite sequences."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def repeat_forever(thing):\n",
      "    \"\"\"Repeat the same thing repeatedly.\"\"\"\n",
      "    while True:\n",
      "        yield thing"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 44
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# This will never complete and your machine will not be happy\n",
      "#sum(repeat_forever(1))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 45
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Itertools\n",
      "---------\n",
      "\n",
      "The `itertools` module has many functions for dealing with iterators and creating new generators in an efficient manner. The documentation for the itertools module is excellent and each function is documented with a pure python implementation (altough the actual implementation is probably more optimised), see [http://docs.python.org/2/library/itertools.html](http://docs.python.org/2/library/itertools.html) for the details. The end of the documentation page also gives many examples that can be cribbed from."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import itertools"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 46
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(itertools.chain([1,2,3], [10,20,30]))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 47,
       "text": [
        "[1, 2, 3, 10, 20, 30]"
       ]
      }
     ],
     "prompt_number": 47
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "In many occasions it is useful to iterate over several sequences at the same time and combine them in some way."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(itertools.izip(range(7), itertools.cycle('LOL')))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 48,
       "text": [
        "[(0, 'L'), (1, 'O'), (2, 'L'), (3, 'L'), (4, 'O'), (5, 'L'), (6, 'L')]"
       ]
      }
     ],
     "prompt_number": 48
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "map(sum, itertools.izip(range(8), square_range(8), square_range(9)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 49,
       "text": [
        "[2, 9, 20, 35, 54, 77, 104, 135]"
       ]
      }
     ],
     "prompt_number": 49
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "In contrast to some other languages, in Python you iterate over the *items* in an iterable, but you can index them as necessary. Note that everything is *zero-based* in Python.\n",
      "\n",
      "    struct foo fooarr[10];\n",
      "\n",
      "    for(i = 0; i < sizeof(fooarr) / sizeof(struct foo); i++)\n",
      "    {\n",
      "      do_something(fooarr[i].data);\n",
      "    }"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(enumerate(itertools.permutations(range(3))))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 50,
       "text": [
        "[(0, (0, 1, 2)),\n",
        " (1, (0, 2, 1)),\n",
        " (2, (1, 0, 2)),\n",
        " (3, (1, 2, 0)),\n",
        " (4, (2, 0, 1)),\n",
        " (5, (2, 1, 0))]"
       ]
      }
     ],
     "prompt_number": 50
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for index, item in enumerate([\"Earl Grey\", \"English Breakfast\", \"Yorkshire\", \"Royal Blend\"]):\n",
      "    print([index, item])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[0, 'Earl Grey']\n",
        "[1, 'English Breakfast']\n",
        "[2, 'Yorkshire']\n",
        "[3, 'Royal Blend']\n"
       ]
      }
     ],
     "prompt_number": 51
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "slide"
      }
     },
     "source": [
      "Slicing\n",
      "-------\n",
      "\n",
      "Another aspect of lists is slicing, using square brackets, which is accessing subsets of elements or the individual elements. Slicing can also be used in a functional manner and made to return generator expressions and the `itertools` module lets you work with infinte sequences too."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(range(10))[4:10]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 52,
       "text": [
        "[4, 5, 6, 7, 8, 9]"
       ]
      }
     ],
     "prompt_number": 52
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(itertools.islice(itertools.count(10), 10))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 53,
       "text": [
        "[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]"
       ]
      }
     ],
     "prompt_number": 53
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "dict(itertools.izip(\"ABCD\", [1,2,3,4]))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 54,
       "text": [
        "{'A': 1, 'B': 2, 'C': 3, 'D': 4}"
       ]
      }
     ],
     "prompt_number": 54
    },
    {
     "cell_type": "markdown",
     "metadata": {
      "slideshow": {
       "slide_type": "skip"
      }
     },
     "source": [
      "\n",
      "--  \n",
      "\n",
      "\u00a9 Tom Daff - All rights reserved"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 54
    }
   ],
   "metadata": {}
  }
 ]
}