10-Iterators.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Iterators\n",
    "Often an important piece of data analysis is repeating a similar calculation, over and over, in an automated fashion.\n",
    "For example, you may have a table of a names which you'd like to split into first and last, or perhaps of dates that you'd like to convert to some standard format.\n",
    "One of Python's answers to this is the *iterator* syntax.\n",
    "We've seen this already with the ``range`` iterator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 "
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    print(i, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we're going to dig a bit deeper.\n",
    "It turns out that in Python 3, ``range`` is not a list, but is something called an *iterator*, and learning how it works is a key to understanding a wide class of very useful Python functionality."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterating over lists\n",
    "Iterators are perhaps most easily understood in the concrete case of iterating through a list.\n",
    "Consider the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 5 7 9 11 "
     ]
    }
   ],
   "source": [
    "for value in [2, 4, 6, 8, 10]:\n",
    "    # do some operation\n",
    "    print(value + 1, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The familiar \"``for x in y``\" syntax allows us to repeat some operation for each value in the list.\n",
    "The fact that the syntax of the code is so close to its English description (\"*for [each] value in [the] list*\") is just one of the syntactic choices that makes Python such an intuitive language to learn and use.\n",
    "\n",
    "But the face-value behavior is not what's *really* happening.\n",
    "When you write something like \"``for val in L``\", the Python interpreter checks whether it has an *iterator* interface, which you can check yourself with the built-in ``iter`` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<list_iterator at 0x104722400>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iter([2, 4, 6, 8, 10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is this iterator object which provides the functionality required by the ``for`` loop.\n",
    "The ``iter`` object is a container that gives you access to the next object for as long as it's valid, which can be seen with the built-in function ``next``:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "I = iter([2, 4, 6, 8, 10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "print(next(I))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "print(next(I))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "print(next(I))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What is the purpose of this level of indirection?\n",
    "Well, it turns out this is incredibly useful, because it allows Python to treat things as lists that are *not actually lists*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ``range()``: A List is Not Always a List\n",
    "Perhaps the most common example of this indirect iteration is the ``range()`` function in Python 3 (named ``xrange()`` in Python 2), which returns not a list, but a special ``range()`` object:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "range(0, 10)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "range(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "``range``, like a list, exposes an iterator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<range_iterator at 0x1045a1810>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iter(range(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So Python knows to treat it *as if* it's a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 "
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    print(i, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The benefit of the iterator indirection is that *the full list is never explicitly created!*\n",
    "We can see this by doing a range calculation that would overwhelm our system memory if we actually instantiated it (note that in Python 2, ``range`` creates a list, so running the following will not lead to good things!):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0, 1, 2, 3, 4, 5, 6, 7, 8, 9, "
     ]
    }
   ],
   "source": [
    "N = 10 ** 12\n",
    "for i in range(N):\n",
    "    if i >= 10: break\n",
    "    print(i, end=', ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If ``range`` were to actually create that list of one trillion values, it would occupy tens of terabytes of machine memory: a waste, given the fact that we're ignoring all but the first ten values!\n",
    "\n",
    "In fact, there's no reason that iterators ever have to end at all!\n",
    "Python's ``itertools`` library contains a ``count`` function which acts as an infinite range:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0, 1, 2, 3, 4, 5, 6, 7, 8, 9, "
     ]
    }
   ],
   "source": [
    "from itertools import count\n",
    "\n",
    "for i in count():\n",
    "    if i >= 10:\n",
    "        break\n",
    "    print(i, end=', ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Had we not thrown-in a loop break here, it would go on happily counting until the process is manually interrupted or killed (using, for example, ``ctrl-C``)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Useful Iterators\n",
    "This iterator syntax is used nearly universally in Python built-in types as well as the more data-science-specific object we'll explore in later chapters.\n",
    "Here we'll cover some of the more useful iterators in the Python language:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ``enumerate``\n",
    "Often you need to iterate not only the values in an array, but also keep track of the index.\n",
    "You might be tempted to do things this way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 2\n",
      "1 4\n",
      "2 6\n",
      "3 8\n",
      "4 10\n"
     ]
    }
   ],
   "source": [
    "L = [2, 4, 6, 8, 10]\n",
    "for i in range(len(L)):\n",
    "    print(i, L[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While this works, Python provides a cleaner syntax using the ``enumerate`` iterator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 2\n",
      "1 4\n",
      "2 6\n",
      "3 8\n",
      "4 10\n"
     ]
    }
   ],
   "source": [
    "for i, val in enumerate(L):\n",
    "    print(i, val)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the more \"Pythonic\" way to enumerate the indices and values in a list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ``zip``\n",
    "Other times, you may have multiple lists that you want to iterate over simultaneously.\n",
    "You could certainly iterate over the index as in the non-Pythonic example above, but it is better to use the ``zip`` iterator, which zips together iterables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 3\n",
      "4 6\n",
      "6 9\n",
      "8 12\n",
      "10 15\n"
     ]
    }
   ],
   "source": [
    "L = [2, 4, 6, 8, 10]\n",
    "R = [3, 6, 9, 12, 15]\n",
    "for lval, rval in zip(L, R):\n",
    "    print(lval, rval)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Any number of iterables can be zipped together, and if they are different lengths, the shortest will determine the length of the ``zip``."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ``map`` and ``filter``\n",
    "The ``map`` iterator takes a function and applies it to the values in an iterator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 4 9 16 25 36 49 64 81 "
     ]
    }
   ],
   "source": [
    "# find the first ten square numbers\n",
    "square = lambda x: x ** 2\n",
    "for val in map(square, range(10)):\n",
    "    print(val, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The ``filter`` iterator looks similar, except it only passes-through values for which the filter function evaluates to True:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 2 4 6 8 "
     ]
    }
   ],
   "source": [
    "# find values up to 10 for which x % 2 is zero\n",
    "is_even = lambda x: x % 2 == 0\n",
    "for val in filter(is_even, range(10)):\n",
    "    print(val, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The ``map`` and ``filter`` functions, along with the ``reduce`` function (which lives in Python's ``functools`` module) are fundamental components of the *functional programming* style, which, while not a dominant programming style in the Python world, has its outspoken proponents (see for example the [pytoolz](https://toolz.readthedocs.org/en/latest/) library)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterators as function arguments\n",
    "\n",
    "We saw in section X.X. that ``*args`` and ``**kwargs`` can be used to past sequences and dictionaries to functions.\n",
    "It turns out that the ``*args`` syntax works not just with sequences, but with any iterator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9\n"
     ]
    }
   ],
   "source": [
    "print(*range(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, for example, we can get tricky and compress the ``map`` example above into the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 4 9 16 25 36 49 64 81\n"
     ]
    }
   ],
   "source": [
    "print(*map(lambda x: x ** 2, range(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using this trick lets us answer the age-old question that comes up in Python learners' forums: why is there no ``unzip()`` function which does the opposite of ``zip()``?\n",
    "If you lock yourself in a dark closet and think about it for a while, you might realize that the opposite of ``zip()`` is... ``zip()``! The key is that ``zip()`` can zip-together any number of iterators or sequences. Observe:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "L1 = (1, 2, 3, 4)\n",
    "L2 = ('a', 'b', 'c', 'd')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 'a') (2, 'b') (3, 'c') (4, 'd')\n"
     ]
    }
   ],
   "source": [
    "z = zip(L1, L2)\n",
    "print(*z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2, 3, 4) ('a', 'b', 'c', 'd')\n"
     ]
    }
   ],
   "source": [
    "z = zip(L1, L2)\n",
    "new_L1, new_L2 = zip(*z)\n",
    "print(new_L1, new_L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ponder this for a while. If you understand why it works, you'll have come a long way in understanding Python iterators!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Specialized Iterators: ``itertools``\n",
    "\n",
    "Above we briefly looked at the infinite ``range`` iterator, ``itertools.count``.\n",
    "The ``itertools`` module contains a whole host of useful iterators; it's well worth your while to take explore the module to see what's available.\n",
    "As an example, consider the ``itertools.permutations`` function, which iterates over all permutations of a sequence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0)\n"
     ]
    }
   ],
   "source": [
    "from itertools import permutations\n",
    "p = permutations(range(3))\n",
    "print(*p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, the ``itertools.combinations`` function which iterates over all unique combinations of ``N`` values within a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 1) (0, 2) (0, 3) (1, 2) (1, 3) (2, 3)\n"
     ]
    }
   ],
   "source": [
    "from itertools import combinations\n",
    "c = combinations(range(4), 2)\n",
    "print(*c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Somewhat related is the ``product`` iterator, which iterates over all sets of pairs between two or more iterables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('a', 0) ('a', 1) ('a', 2) ('b', 0) ('b', 1) ('b', 2)\n"
     ]
    }
   ],
   "source": [
    "from itertools import product\n",
    "p = product('ab', range(3))\n",
    "print(*p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Many more useful iterators exist in ``itertools``: the full list can be found, along with some examples, in Python's [online documentation](https://docs.python.org/3.5/library/itertools.html)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}