{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Functional tools\n",
    "================\n",
    "\n",
    "Python provides a few in-built commands such as `map`, `filter`, `reduce` as well `lambda` (to create anonymous functions) and list comprehension. These are typical commands from functional languages of which LISP is probably best known.\n",
    "\n",
    "Functional programming can be extremely powerful and one of the strengths of Python is that it allows to program using (i) imperative/procedural programming style, (ii) object oriented style and (iii) functional style. It is the programmers choice which tools to select from which style and how to mix them to best address a given problem.\n",
    "\n",
    "In this chapter, we provide some examples for usage of the commands listed above.\n",
    "\n",
    "Anonymous functions\n",
    "-------------------\n",
    "\n",
    "All functions we have seen in Python so far have been defined through the `def` keyword, for example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def f(x):\n",
    "     return x ** 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This funtion has the name `f`. Once the function is defined (i.e. the Python interpreter has come across the `def` line), we can call the function using its name, for example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "y = f(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes, we need to define a function that is only used once, or we want to create a function but don’t need a name for it (as for creating closures). In this case, this is called *anonymous* function as it does not have a name. In Python, the `lambda` keyword can create an anonymous function.\n",
    "\n",
    "We create a (named) function first, check it’s type and behaviour:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function __main__.f>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(x):\n",
    "    return x ** 2\n",
    "\n",
    "f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we do the same with an anonymous function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function __main__.<lambda>>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lambda x: x ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(lambda x: x ** 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(lambda x: x ** 2)(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This works exactly in the same way but – as the anonymous function does not have a name – we need to define the function (through the `lambda` expression) – every time we need it.\n",
    "\n",
    "Anonymous functions can take more than one argument:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(lambda x, y: x + y)(10, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "60"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(lambda x, y, z: (x + y) * z )(10, 20, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will see some examples using `lambda` which will clarify typical use cases.\n",
    "\n",
    "Map\n",
    "---\n",
    "\n",
    "The map function `lst2 = map(f, s )` applies a function `f` to all elements in a sequence `s`.\n",
    "The result of `map` can be turned into a list with the same length as `s`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def f(x): \n",
    "    return x ** 2\n",
    "lst2 = list(map(f, range(10)))\n",
    "lst2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Banana', 'Apple', 'Orange']"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(str.capitalize, ['banana', 'apple', 'orange']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Often, this is combined with the anonymous function `lambda`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(lambda x: x ** 2, range(10) ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Banana', 'Apple', 'Orange']"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(lambda s: s.capitalize(), ['banana', 'apple', 'orange']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Filter\n",
    "------\n",
    "\n",
    "The filter function `lst2 = filter( f, lst)` applies the function `f` to all elements in a sequence `s`. The function `f` should return `True` or `False`. This makes a list which will contain only those elements *s*<sub>*i*</sub> of the sequence `s` for which `f`(*s*<sub>*i*</sub>) has returned `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 7, 8, 9, 10]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def greater_than_5(x):\n",
    "    if x > 5:\n",
    "            return True\n",
    "    else:\n",
    "            return False\n",
    "\n",
    "list(filter(greater_than_5, range(11)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The usage of `lambda` can simplify this significantly:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 7, 8, 9, 10]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(filter(lambda x: x > 5, range(11)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['smith', 'bob']"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "known_names = ['smith', 'miller', 'bob']\n",
    "list(filter( lambda name : name in known_names, \\\n",
    "     ['ago', 'smith', 'bob', 'carl']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "List comprehension\n",
    "------------------\n",
    "\n",
    "List comprehensions provide a concise way to create and modify lists without resorting to use of map(), filter() and/or lambda. The resulting list definition tends often to be clearer than lists built using those constructs. Each list comprehension consists of an expression followed by a `for` clause, then zero or more `for` or `if` clauses. The result will be a list resulting from evaluating the expression in the context of the for and if clauses which follow it. If the expression would evaluate to a tuple, it must be parenthesized.\n",
    "\n",
    "Some examples will make this clearer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['banana', 'loganberry', 'passion fruit']"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']\n",
    "[weapon.strip() for weapon in freshfruit]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 12, 18]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vec = [2, 4, 6]\n",
    "[3 * x for x in vec]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[12, 18]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[3 * x for x in vec if x > 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[3 * x for x in vec if x < 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[2, 4], [4, 16], [6, 36]]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[[x, x ** 2] for x in vec]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also use list comprehension to modify the list of integers returned by the `range` command so that our subsequent elements in the list increase by non-integer fractions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x*0.5 for x in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let’s now revisit the examples from the section on `filter`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 7, 8, 9, 10]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x for x in range(11) if x>5 ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['smith', 'bob']"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[name for name in ['ago','smith','bob','carl'] \\\n",
    "      if name in known_names]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and the examples from the `map` section"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[x ** 2 for x in range(10) ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Banana', 'Apple', 'Orange']"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[fruit.capitalize() for fruit in ['banana', 'apple', 'orange'] ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "all of which can be expressed through list comprehensions.\n",
    "\n",
    "More details\n",
    "\n",
    "-   Python Tutorial [5.1.4 List comprehensions](http://docs.python.org/tutorial/datastructures.html#list-comprehensions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reduce\n",
    "------\n",
    "\n",
    "The `reduce` function takes a binary function `f(x,y)`, a sequence `s`, and a start value `a0`. It then applies the function `f` to the start value `a0` and the first element in the sequence: `a1 = f(a,s[0])`. The second element (`s[1]`) of the sequence is then processed as follows: the function f is called with arguments `a1` and `s[1]`, i.e. `a2 = f(a1,s[1])`. In this fashion, the whole sequence is processed. Reduce returns a single number.\n",
    "\n",
    "This can be used, for example, to compute a sum of numbers in a sequence if the function `f(x,y)` returns `x+y`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from functools import reduce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def add(x,y):\n",
    "    return x+y\n",
    "\n",
    "reduce(add, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "155"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(add, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can modify the function `add` to provide some more detail about the process:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "add(x=0, y=1) -> 1\n",
      "add(x=1, y=2) -> 3\n",
      "add(x=3, y=3) -> 6\n",
      "add(x=6, y=4) -> 10\n",
      "add(x=10, y=5) -> 15\n",
      "add(x=15, y=6) -> 21\n",
      "add(x=21, y=7) -> 28\n",
      "add(x=28, y=8) -> 36\n",
      "add(x=36, y=9) -> 45\n",
      "add(x=45, y=10) -> 55\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def add_verbose(x, y):\n",
    "    print(\"add(x=%s, y=%s) -> %s\" % (x, y, x+y))\n",
    "    return x+y\n",
    "\n",
    "reduce(add_verbose, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It may be instructive to use an asymmetric function `f`, such as `add_len( n, s )` where s is a sequence and the function returns `n+len(s)` (suggestion from Thomas Fischbacher):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def add_len(n,s):\n",
    "    return n+len(s)\n",
    "\n",
    "reduce(add_len, [\"This\",\"is\",\"a\",\"test.\"],0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As before, we’ll use a more verbose version of the binary function to see what is happening:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "add_len(n=0, s=This) -> 4\n",
      "add_len(n=4, s=is) -> 6\n",
      "add_len(n=6, s=a) -> 7\n",
      "add_len(n=7, s=test.) -> 12\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def add_len_verbose(n,s):\n",
    "    print(\"add_len(n=%d, s=%s) -> %d\" % (n, s, n+len(s)))\n",
    "    return n+len(s)\n",
    "\n",
    "reduce(add_len_verbose, [\"This\", \"is\", \"a\", \"test.\"], 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another way to understand what the reduce function does is to look at the following function (kindly provided by Thomas Fischbacher) which behaves like `reduce` but explains what it does:\n",
    "\n",
    "Here is an example using the `explain_reduce` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "/Users/fangohr/hg/teaching-python/book/text/code\n"
     ]
    }
   ],
   "source": [
    "cd code/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from explain_reduce import explain_reduce\n",
    "def f(a,b):\n",
    "    return a+b\n",
    "\n",
    "reduce(f, [1,2,3,4,5], 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 0: value-so-far=0 next-list-element=1\n",
      "Step 1: value-so-far=1 next-list-element=2\n",
      "Step 2: value-so-far=3 next-list-element=3\n",
      "Step 3: value-so-far=6 next-list-element=4\n",
      "Step 4: value-so-far=10 next-list-element=5\n",
      "Done. Final result=15\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "explain_reduce(f, [1,2,3,4,5], 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reduce is often combined with `lambda`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(lambda x,y:x+y, [1,2,3,4,5], 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is also the `operator` module which provides standard Python operators as functions. For example, the function `operator.__add__(a,b)` is executed when Python evaluates code such as `a+b`. These are generally faster than `lambda` expressions. We could write the example above as"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import operator\n",
    "reduce(operator.__add__, [1,2,3,4,5], 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use `help(’operator’)` to see the complete list of operator functions.\n",
    "\n",
    "Why not just use for-loops?\n",
    "---------------------------\n",
    "\n",
    "Let’s compare the example introduced at the beginning of the chapter written (i) using a for-loop and (ii) list comprehension. Again, we want to compute the numbers 0<sup>2</sup>, 1<sup>2</sup>, 2<sup>2</sup>, 3<sup>2</sup>, ... up to (*n* − 1)<sup>2</sup> for a given *n*.\n",
    "\n",
    "Implementation (i) using a for-loop with *n*=10:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "y = []\n",
    "for i in range(10):\n",
    "    y.append(i ** 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implementation (ii) using list comprehension:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "y = [x ** 2 for x in range(10)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or using `map`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "y = map(lambda x: x ** 2, range(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The versions using list comprehension and `map` fit into one line of code whereas the for-loop needs 3. This example shows that functional code result in very *concise* expressions. Typically, the number of mistakes a programmer makes is per line of code written, so the fewer lines of code we have, the fewer bugs we need to find.\n",
    "\n",
    "Often programmers find that initially the list-processing tools introduced in this chapter seem less intuitive than using for-loops to process every element in a list individually, but that – over time – they come to value a more functional programming style.\n",
    "\n",
    "Speed\n",
    "-----\n",
    "\n",
    "The functional tools described in this chapter can also be faster than using explicit (for or while) loops over list elements.\n",
    "\n",
    "The program `list_comprehension_speed.py` below computes $\\\\sum\\_{i=0}^{N-1} i^2$ for a large value of *N* using 4 different methods and records execution time:\n",
    "\n",
    "-   Method 1: for-loop (with pre-allocated list, storing of *i*<sup>2</sup> in list, then using in-built `sum` function)\n",
    "\n",
    "-   Method 2: for-loop without list (updating sum as the for-loop progresses)\n",
    "\n",
    "-   Method 3: using list comprehension\n",
    "\n",
    "-   Method 4: using numpy. (Numpy is covered in [chapter 14](14-numpy.ipynb))\n",
    "\n",
    "The program produces the following output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N = 10000000\n",
      "for-loop1 3.92704701423645\n",
      "for-loop2 3.2223408222198486\n",
      "listcomp 2.6926040649414062\n",
      "numpy 0.11613011360168457\n",
      "Slowest method is 33.8 times slower than the fastest method.\n"
     ]
    }
   ],
   "source": [
    "!python list_comprehension_speed.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The actual execution performance depends on the computer. The relative performance may depend on versions of Python and its support libraries (such as numpy) we use.\n",
    "\n",
    "With the current version (python 3.4, numpy 1.10, on a x84 machine running OS X), we see that methods 1 and 2 (for-loop without list and with pre-allocated list) are slowest, somewhat closely followed by the slightly faster list comprehension. The fastest method is number 4 (using numpy)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For reference, here is the source code of the programme:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\"\"\"Compare calculation of \\sum_i x_i^2 with\r\n",
      "i going from zero to N-1.\r\n",
      "\r\n",
      "We use (i) for loops and list, (ii) for-loop, (iii) list comprehension\r\n",
      "and (iv) numpy.\r\n",
      "\r\n",
      "We use floating numbers to avoid using Python's long int (which would\r\n",
      "be likely to make the timings less representative).\r\n",
      "\"\"\"\r\n",
      "\r\n",
      "import time\r\n",
      "import numpy\r\n",
      "N = 10000000\r\n",
      "\r\n",
      "\r\n",
      "def timeit(f, args):\r\n",
      "    \"\"\"Given a function f and a tuple args containing\r\n",
      "    the arguments for f, this function calls f(*args),\r\n",
      "    and measures and returns the execution time in\r\n",
      "    seconds.\r\n",
      "\r\n",
      "    Return value is tuple: entry 0 is the time,\r\n",
      "    entry 1 is the return value of f.\"\"\"\r\n",
      "\r\n",
      "    starttime = time.time()\r\n",
      "    y = f(*args)    # use tuple args as input arguments\r\n",
      "    endtime = time.time()\r\n",
      "    return endtime - starttime, y\r\n",
      "\r\n",
      "\r\n",
      "def forloop1(N):\r\n",
      "    s = 0\r\n",
      "    for i in range(N):\r\n",
      "        s += float(i) * float(i)\r\n",
      "    return s\r\n",
      "\r\n",
      "\r\n",
      "def forloop2(N):\r\n",
      "    y = [0] * N\r\n",
      "    for i in range(N):\r\n",
      "        y[i] = float(i) ** 2\r\n",
      "    return sum(y)\r\n",
      "\r\n",
      "\r\n",
      "def listcomp(N):\r\n",
      "    return sum([float(x) * x for x in range(N)])\r\n",
      "\r\n",
      "\r\n",
      "def numpy_(N):\r\n",
      "    return numpy.sum(numpy.arange(0, N, dtype='d') ** 2)\r\n",
      "\r\n",
      "#main program starts\r\n",
      "timings = []\r\n",
      "print(\"N =\", N)\r\n",
      "forloop1_time, f1_res = timeit(forloop1, (N,))\r\n",
      "timings.append(forloop1_time)\r\n",
      "print(\"for-loop1\", forloop1_time)\r\n",
      "forloop2_time, f2_res = timeit(forloop2, (N,))\r\n",
      "timings.append(forloop2_time)\r\n",
      "print(\"for-loop2\", forloop2_time)\r\n",
      "listcomp_time, lc_res = timeit(listcomp, (N,))\r\n",
      "timings.append(listcomp_time)\r\n",
      "print(\"listcomp\", listcomp_time)\r\n",
      "numpy_time, n_res = timeit(numpy_, (N,))\r\n",
      "timings.append(numpy_time)\r\n",
      "print(\"numpy\", numpy_time)\r\n",
      "\r\n",
      "#ensure that different methods provide identical results\r\n",
      "assert f1_res == f2_res\r\n",
      "assert f1_res == lc_res\r\n",
      "# Allow a bit of difference for the numpy calculation\r\n",
      "numpy.testing.assert_approx_equal(f1_res, n_res)\r\n",
      "\r\n",
      "print(\"Slowest method is {:.1f} times slower than the fastest method.\".format(\r\n",
      "    max(timings)/min(timings)))\r\n"
     ]
    }
   ],
   "source": [
    "!cat list_comprehension_speed.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.4.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}