13-GeneratorsAndIterators.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:c50470657f7c55b7085b609d8c336141f0d022bb0c8a7b8651ef2d1e7c2120b5"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Generators and Iterators\n",
      "\n",
      "## Building your own generators with `yield`"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "def counter(start, end):\n",
      "    current = start\n",
      "    while current < end:\n",
      "        yield current\n",
      "        current += 1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "counter(1, 10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "<generator object counter at 0x305d280>"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = counter(1,10)\n",
      "x.next()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "1"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x.next()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "2"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x.next()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "3"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = counter(1,10)\n",
      "list(x)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "[1, 2, 3, 4, 5, 6, 7, 8, 9]"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`yield` can also be used as a function, along with the `send()` method"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "def accumulator(start=0):\n",
      "    current = start\n",
      "    while True:\n",
      "        current += yield(current)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = accumulator()\n",
      "x.next()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 14,
       "text": [
        "0"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x.send(1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 15,
       "text": [
        "1"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x.send(1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "2"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x.send(10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 17,
       "text": [
        "12"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## The iterator protocol\n",
      "\n",
      "What does `for x in sequence:` *really* do?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "seq = range(4)\n",
      "for x in seq: print x"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n",
        "1\n",
        "2\n",
        "3\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "iter_seq = iter(seq)\n",
      "print iter_seq"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "<listiterator object at 0x31c5450>\n"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "iter_seq = iter(seq)\n",
      "try:\n",
      "    while True:\n",
      "        x = iter_seq.next()\n",
      "        print x\n",
      "except StopIteration:\n",
      "    pass"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n",
        "1\n",
        "2\n",
        "3\n"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Generators are their own iterators:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print counter(0, 4)\n",
      "print iter(counter(0, 4))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "<generator object counter at 0x31a4e60>\n",
        "<generator object counter at 0x31a4e60>\n"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for item in counter(0, 4): print item"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0\n",
        "1\n",
        "2\n",
        "3\n"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can also define our own iterator classes (though generators are usually more readable):"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Counter(object):\n",
      "    def __init__(self, start, end):\n",
      "        self._start = start\n",
      "        self._end = end\n",
      "    def __iter__(self):\n",
      "        return CounterIterator(self._start, self._end)\n",
      "    \n",
      "class CounterIterator(object):\n",
      "    def __init__(self, start, end):\n",
      "        self._cur = ctr._start\n",
      "        self._end = ctr._end\n",
      "    def next(self):\n",
      "        result = self._cur\n",
      "        self._cur += 1\n",
      "        if result < self._end:\n",
      "            return result\n",
      "        else:\n",
      "            raise StopIteration\n",
      "\n",
      "ctr = Counter(0, 5)\n",
      "print list(ctr)    "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[0, 1, 2, 3, 4]\n"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Loop comprehensions"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[ x*2 for x in range(4) ]   # map(lambda x: x*2, range(4))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 24,
       "text": [
        "[0, 2, 4, 6]"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "lst = [ ]\n",
      "for x in range(4):\n",
      "    lst.append(x*2)\n",
      "lst"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 25,
       "text": [
        "[0, 2, 4, 6]"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[ (x,y) for x in range(4) for y in range(4) ]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 26,
       "text": [
        "[(0, 0),\n",
        " (0, 1),\n",
        " (0, 2),\n",
        " (0, 3),\n",
        " (1, 0),\n",
        " (1, 1),\n",
        " (1, 2),\n",
        " (1, 3),\n",
        " (2, 0),\n",
        " (2, 1),\n",
        " (2, 2),\n",
        " (2, 3),\n",
        " (3, 0),\n",
        " (3, 1),\n",
        " (3, 2),\n",
        " (3, 3)]"
       ]
      }
     ],
     "prompt_number": 26
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[ [ (r,c) for c in range(4) ]\n",
      "  for r in range(4) ]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 62,
       "text": [
        "[[(0, 0), (0, 1), (0, 2), (0, 3)],\n",
        " [(1, 0), (1, 1), (1, 2), (1, 3)],\n",
        " [(2, 0), (2, 1), (2, 2), (2, 3)],\n",
        " [(3, 0), (3, 1), (3, 2), (3, 3)]]"
       ]
      }
     ],
     "prompt_number": 62
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[ x for x in range(10) if x % 2 == 0 ]   # { x | x e range(10), x is even}"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 27,
       "text": [
        "[0, 2, 4, 6, 8]"
       ]
      }
     ],
     "prompt_number": 27
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[ x * 4\n",
      "  for x in range(10) \n",
      "  if x % 2 == 0 \n",
      "  if x % 3 == 0 ]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 28,
       "text": [
        "[0, 24]"
       ]
      }
     ],
     "prompt_number": 28
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Generator expressions"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[ x for x in range(10) if x % 2 == 0 ]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 29,
       "text": [
        "[0, 2, 4, 6, 8]"
       ]
      }
     ],
     "prompt_number": 29
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "( x for x in range(10) if x % 2 == 0 )"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 30,
       "text": [
        "<generator object <genexpr> at 0x31b85a0>"
       ]
      }
     ],
     "prompt_number": 30
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "gen = ( x for x in range(10) if x % 2 == 0 )"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 31
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "gen.next()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 32,
       "text": [
        "0"
       ]
      }
     ],
     "prompt_number": 32
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "gen.next()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 33,
       "text": [
        "2"
       ]
      }
     ],
     "prompt_number": 33
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "list(gen)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 34,
       "text": [
        "[4, 6, 8]"
       ]
      }
     ],
     "prompt_number": 34
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Exercises\n",
      "\n",
      "- Write a generator that will yield the nodes of a tree and their depth in post-order\n",
      "- Write a loop that uses that generator to *print* the nodes of a tree in post-order"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}