04a-lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Programming with Python\n",
    "#### Vedran Šego, [vsego.org](http://vsego.org/)\n",
    "\n",
    "## Contents:\n",
    "\n",
    "1. Data structures (intro)\n",
    "\n",
    "2. Lists\n",
    "\n",
    "3. Iterables\n",
    "\n",
    "4. Other built-in iterables\n",
    "\n",
    "5. Converting between iterables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Data structures\n",
    "\n",
    "So far, we have seen how to work with integers, \"real\" numbers, and Boolean values. However, there is often a need to work with more complex values, like lists, sets, and various other collections of data. The joint name for these is *data structures* or *compound data types*.\n",
    "\n",
    "The most common data structure is a list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lists\n",
    "\n",
    "As the name sugests, a list is a list of values. Each value has its index (a zero-based position in the list) and can appear in the list as many times as we want.\n",
    "\n",
    "A list is defined as a comma-separated list of values, enclosed in square brackets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = [17, 19, 23, 29, 31]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The list of values may end with a comma (for lists as well as the other structures in this lecture). For example, this is equivalent to `x` above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = [17, 19, 23, 29, 31,]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This is convenient when a list contains items with longer definitions, so each is put in its own line for better readability, as well as ease of cut/copy/paste. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "marx_bros = [\n",
    "    \"Chico (Leonard)\",\n",
    "    \"Harpo (Adolph/Arthur)\",\n",
    "    \"Groucho (Julius Henry)\",\n",
    "    \"Gummo (Milton)\",\n",
    "    \"Zeppo (Herbert Manfred)\",\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "An empty list can be given by"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "but it is preferred to do it like this, for better code readability:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A list in Python can be printed using a simple call to `print`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 19, 23, 29, 31, 37, 41, 43, 47, 53]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23, 29, 31, 37,    41, 43, 47, 53]\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "To get the list elements, we use indices. The first element has index 0 (zero), the second one has index 1, etc. Negative indices count from the end of the list, with `-1` denoting the last element, `-2` denoting the one before it, and so on.\n",
    "\n",
    "Indexing a nonexistent list element will result in an error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The list: [17, 19, 23, 29, 31, 37, 41, 43, 47, 53]\n",
      "The first element of the list x: 17\n",
      "The second element of the list x: 19\n",
      "The last element of the list x: 53\n",
      "The next to last element of the list x: 47\n"
     ]
    },
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-8-804389ab6b93>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"The last element of the list x:\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"The next to last element of the list x:\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 6\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"The nonexistent element of the list x:\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1719\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "print(\"The list:\", x)\n",
    "print(\"The first element of the list x:\", x[0])\n",
    "print(\"The second element of the list x:\", x[1])\n",
    "print(\"The last element of the list x:\", x[-1])\n",
    "print(\"The next to last element of the list x:\", x[-2])\n",
    "print(\"The nonexistent element of the list x:\", x[1719])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can also slice a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The list: [17, 19, 23, 29, 31, 37, 41, 43, 47, 53]\n",
      "All elements except the first two (the one with index 2 and those after it): [23, 29, 31, 37, 41, 43, 47, 53]\n",
      "Elements with indices 2, 3, and 4 (indices 2 through 5, but excluding 5): [23, 29, 31]\n",
      "The first 3 elements (elements from start up to the one indexed by 3, but without it): [17, 19, 23]\n",
      "A copy of the list (all of its elements): [17, 19, 23, 29, 31, 37, 41, 43, 47, 53]\n",
      "x[3], x[5], x[7]: [29, 37, 43]\n",
      "All elements with even indices: [17, 23, 31, 41, 47]\n",
      "All elements with odd indices: [19, 29, 37, 43, 53]\n"
     ]
    }
   ],
   "source": [
    "print(\"The list:\", x)\n",
    "print(\"All elements except the first two (the one with index 2 and those after it):\", x[2:])\n",
    "print(\"Elements with indices 2, 3, and 4 (indices 2 through 5, but excluding 5):\", x[2:5])\n",
    "print(\"The first 3 elements (elements from start up to the one indexed by 3, but without it):\", x[:3])\n",
    "print(\"A copy of the list (all of its elements):\", x[:])\n",
    "print(\"x[3], x[5], x[7]:\", x[3:8:2])\n",
    "print(\"All elements with even indices:\", x[::2])\n",
    "print(\"All elements with odd indices:\", x[1::2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Changing the elements of a list\n",
    "\n",
    "The same indexing that we have used to read the elements of a list can be used to change them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The list:       [17, 19, 23, 29, 31]\n",
      "The list:       [17, 19, 23, 13, 31]       (29 -> 13)\n",
      "The list:       [17, 19, 23, 13, 11]       (31 -> 11)\n",
      "The list:       [17, 2, 3, 5, 7, 13, 11]   ([19, 23] -> [2, 3, 5, 7])\n",
      "A cleared list: []                         (all the elements replaced with an empty list)\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23, 29, 31]\n",
    "print(\"The list:      \", x)\n",
    "x[3] = 13\n",
    "print(\"The list:      \", x, \"      (29 -> 13)\")\n",
    "x[-1] = 11\n",
    "print(\"The list:      \", x, \"      (31 -> 11)\")\n",
    "x[1:3] = [2, 3, 5, 7]\n",
    "print(\"The list:      \", x, \"  ([19, 23] -> [2, 3, 5, 7])\")\n",
    "x[:] = []\n",
    "print(\"A cleared list:\", x, \"                        (all the elements replaced with an empty list)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Warning:** Be very careful with list assignments:\n",
    "\n",
    "* `y = x` $\\Longrightarrow$ `y` becomes **the same list** as `x`;\n",
    "* `z = x[:]` $\\Longrightarrow$ `z` becomes **a copy** of `x`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Observe the difference:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before the change:\n",
      "  x = [17, 19, 23]\n",
      "  y = [17, 19, 23]\n",
      "  z = [17, 19, 23]\n",
      "After the change:\n",
      "  x = [17, 13, 23]\n",
      "  y = [17, 13, 23]\n",
      "  z = [17, 19, 11]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23]\n",
    "y = x\n",
    "z = x[:]\n",
    "\n",
    "print(\"Before the change:\")\n",
    "print(\"  x =\", x)\n",
    "print(\"  y =\", y)\n",
    "print(\"  z =\", z)\n",
    "\n",
    "y[1] = 13\n",
    "z[2] = 11\n",
    "\n",
    "print(\"After the change:\")\n",
    "print(\"  x =\", x)\n",
    "print(\"  y =\", y)\n",
    "print(\"  z =\", z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The `x[:]` makes a so called *shallow copy* (equicalent to `x.copy()`), which is not exactly what one would consider a \"copy\". For a \"real\" copy, one needs to use a *deep copy*. To learn more about this, read [the on-line documentation on copy module](https://docs.python.org/3/library/copy.html)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "For this same reason that the above change of `y[1]` also changed `x[1]`, changing a list parameter in a function will result in the change of the argument:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def f(a, b, c):\n",
    "    a = 19\n",
    "    b = [2, 3, 5]\n",
    "    c[0] = 11\n",
    "\n",
    "x = 17\n",
    "y = [17, 19, 23]\n",
    "z = [29, 31, 37]\n",
    "\n",
    "print(\"Initial values:\")\n",
    "print(\"  x =\", x)\n",
    "print(\"  y =\", y)\n",
    "print(\"  z =\", z)\n",
    "\n",
    "f(x, y, z)\n",
    "\n",
    "print(\"After a call to the function `f`:\")\n",
    "print(\"  x =\", x)\n",
    "print(\"  y =\", y)\n",
    "print(\"  z =\", z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## The length of a list\n",
    "\n",
    "Getting the length of a list is easy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before change:\n",
      "  x = [17, 19, 23, 29, 31]\n",
      "  Length of x: 5\n",
      "After change:\n",
      "  x = [17, 2, 29, 31]\n",
      "  Length of x: 4\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23, 29, 31]\n",
    "\n",
    "print(\"Before change:\")\n",
    "print(\"  x =\", x)\n",
    "print(\"  Length of x:\", len(x))\n",
    "\n",
    "x[1:3] = [2]\n",
    "\n",
    "print(\"After change:\")\n",
    "print(\"  x =\", x)\n",
    "print(\"  Length of x:\", len(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Appending a list\n",
    "\n",
    "We can add a single element to a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before appending: [17, 19, 23]\n",
      "After appending:  [17, 19, 23, 29]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23]\n",
    "print(\"Before appending:\", x)\n",
    "x.append(29)\n",
    "print(\"After appending: \", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Warning:** `append` accepts only one argument. If it gets more, an error occurs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "append() takes exactly one argument (2 given)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-14-3ee62ca73cbf>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m31\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m37\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: append() takes exactly one argument (2 given)"
     ]
    }
   ],
   "source": [
    "x.append(31, 37)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Also, if we `append` a list, it will be appended as a single element:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "After appending:  [17, 19, 23, 29, [31, 37]]\n"
     ]
    }
   ],
   "source": [
    "x.append([31, 37])\n",
    "print(\"After appending: \", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "To do the latter, i.e., to append more than one element to the list, you need extending it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before extending: [17, 19, 23]\n",
      "After extending:  [17, 19, 23, 29, 31]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23]\n",
    "print(\"Before extending:\", x)\n",
    "x.extend([29,31])\n",
    "print(\"After extending: \", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "One can also create a new extended list using a `+` operator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = [17, 19, 23]\n",
      "y = [17, 19, 23, 29, 31]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23]\n",
    "print(\"x =\", x)\n",
    "y = x + [29,31]\n",
    "print(\"y =\", y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can also insert elements to the beginning or somewhere in the middle of a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before inserting:                                 [17, 19, 23]\n",
      "After inserting to the beginning:                 [13, 17, 19, 23]\n",
      "After inserting to the position with the index 2: [13, 17, 11, 19, 23]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23]\n",
    "print(\"Before inserting:                                \", x)\n",
    "x.insert(0, 13)\n",
    "print(\"After inserting to the beginning:                \", x)\n",
    "x.insert(2, 11)\n",
    "print(\"After inserting to the position with the index 2:\", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Like `append`, `insert` takes a single element that it inserts in the list.\n",
    "\n",
    "However, inserting a list in the middle of an existing list is not a problem: we put the new list in place of the sublist between, for example, indices 2 and 2, excluding the last one (so, a sublist of a zero legth, starting at index 2):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before inserting:           [17, 19, 23]\n",
      "After inserting at index 2: [17, 19, 2, 3, 5, 7, 23]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23]\n",
    "print(\"Before inserting:          \", x)\n",
    "x[2:2] = [2, 3, 5, 7]\n",
    "print(\"After inserting at index 2:\", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Or, maybe a bit easier to read, we can take the elements up to (but excluding) index 2, append the new list, and then append that with the elements of the original list starting at index 2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before inserting:           [17, 19, 23]\n",
      "After inserting at index 2: [17, 19, 2, 3, 5, 7, 23]\n",
      "[17, 19, 23]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23]\n",
    "print(\"Before inserting:          \", x)\n",
    "y = x[:2] + [2, 3, 5, 7] + x[2:]\n",
    "print(\"After inserting at index 2:\", y)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This method is practical to create a new list, i.e.,\n",
    "\n",
    "```python\n",
    "new_list = old_list[:2] + [2, 3, 5, 7] + old_list[2:]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Like using the `+` operator to concatenate a list, we can use `*` to create a list made of concatenated copies of a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17, 19, 23, 17, 19, 23, 17, 19, 23]\n"
     ]
    }
   ],
   "source": [
    "print([ 17, 19, 23 ] * 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "However, be careful when using this with list of lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[17, 19], [17, 19], [17, 19], [17, 19], [17, 19]]\n",
      "[[17, 19], 23, [17, 19], [17, 19], [17, 19]]\n"
     ]
    }
   ],
   "source": [
    "x = [ [17, 19] ] * 5\n",
    "print(x)\n",
    "x[1] = 23\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "You probably wanted this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[17, 19], [17, 19], [17, 19], [17, 19], [17, 19]]\n",
      "[[17, 23], [17, 19], [17, 19], [17, 19], [17, 19]]\n"
     ]
    }
   ],
   "source": [
    "x = [ [17, 19] for _ in range(5) ]\n",
    "print(x)\n",
    "x[0][1] = 23\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why didn't\n",
    "```python\n",
    "x = [ [17, 19] ] * 5\n",
    "```\n",
    "work as expected?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Types of the elements\n",
    "\n",
    "In strongly typed languages the elements of a list have to be of a same type. However, in Python, this is not the case:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x[0] = 17\n",
      "  type(x[0]) = <class 'int'>\n",
      "x[1] = 1.7\n",
      "  type(x[1]) = <class 'float'>\n",
      "x[2] = [23, 29]\n",
      "  type(x[2]) = <class 'list'>\n",
      "x[2][0] = 23\n",
      "  type(x[2][0]) = <class 'int'>\n"
     ]
    }
   ],
   "source": [
    "x = [17, 1.7, [23, 29]]\n",
    "for i in range(len(x)):\n",
    "    print(\"x[\" + str(i) + \"] =\", x[i])\n",
    "    print(\"  type(x[\" + str(i) + \"]) =\", type(x[i]))\n",
    "print(\"x[2][0] =\", x[2][0])\n",
    "print(\"  type(x[2][0]) =\", type(x[2][0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Notice the indexing of the elements in a list that is an element of another list:\n",
    "\n",
    "* `x` is a list.\n",
    "* `x[2]` is the third element of the list `x`; that element is, in our example, another list.\n",
    "* `x[2][0]` is the first element of the list `x[2]`.\n",
    "\n",
    "Of course, we cannot do that for elements of the original list that are not indexable. For example, we cannot access `x[1][1]` because `x[1]` is a real number that is not *subscriptable* (i.e., it cannot be indexed):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'float' object is not subscriptable",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-28-6fac658adf42>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: 'float' object is not subscriptable"
     ]
    }
   ],
   "source": [
    "print(x[1][1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Reversing a list\n",
    "\n",
    "How can we reverse the order of the list's elements?\n",
    "\n",
    "The Python way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[23, 19, 17]\n",
      "[17, 19, 23]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23]\n",
    "y = list(reversed(x))\n",
    "print(y)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The function `reversed` returns its argument in a reverse order. However, the return value is not a new list, but a something called *iterator*, which is the same object that `range` returns. For that reason, we need to print `list(reversed(x))`, but we don't need the `list(...)` conversion if we just want to use it in a `for`-loop. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = [17, 19, 23]\n",
      "Reversed, one by one element:\n",
      "23\n",
      "19\n",
      "17\n"
     ]
    }
   ],
   "source": [
    "print(\"x =\", x)\n",
    "print(\"Reversed, one by one element:\")\n",
    "for i in reversed(x):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can also reverse the existing list, without creating a new one (a so called *in-place reversing*):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before reversing: [17, 19, 23]\n",
      "After reversing:  [23, 19, 17]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23]\n",
    "print(\"Before reversing:\", x)\n",
    "x.reverse()\n",
    "print(\"After reversing: \", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is faster and uses less memory than creating a new list and then assigning it to the same variable (`x = reversed(x)`)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Sorting\n",
    "\n",
    "Sorting is rearranging of the list in a way that its elements come in some order. For example, a list `[17, 13, 19, 11, 23]` can be sorted in many ways (i.e., by many criteria):\n",
    "\n",
    "* ascending by the value: `[11, 13, 17, 19, 23]`,\n",
    "* descending by the value: `[23, 19, 17, 13, 11]`,\n",
    "* ascending by the sum of the digits: `[11, 13, 23, 17, 19]` (because the sums of the digits are `[2, 4, 5, 8, 10]`,  \n",
    "etc.\n",
    "\n",
    "When we talk about sorting without mentioning a criterion, a sorting by value is implied. If we ommit the direction (ascending or descending), ascending is assumed. So, \"sort a list\" would mean \"sort a list ascendingly by the value\".\n",
    "\n",
    "**A question:** Why do we sort the data?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Basic sorting in Python is simple. First, we define the function `digit_sum` from the previous lecture, in order to be able to sort our list by the sum of the digits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def digit_sum(n, d=1, r=0):\n",
    "    \"\"\"\n",
    "    ...\n",
    "    \"\"\"\n",
    "\n",
    "    # Initializations\n",
    "    res = 0 # Result (do not use \"sum\", because there is a built-in function with that name)\n",
    "    n = abs(n) # Lose the sign\n",
    "\n",
    "    while n > 0:\n",
    "        digit = n % 10\n",
    "        if digit % d == r:\n",
    "            res += digit\n",
    "        n //= 10\n",
    "\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Now, we can sort by all three criteria:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The original list:                  [17, 13, 19, 11, 23]\n",
      "Ascending by the value:             [11, 13, 17, 19, 23]\n",
      "Descending by the value:            [23, 19, 17, 13, 11]\n",
      "or:                                 [23, 19, 17, 13, 11]\n",
      "or (the best approach):             [23, 19, 17, 13, 11]\n",
      "Ascending by the sum of the digits: [11, 13, 23, 17, 19]\n",
      "or:                                 [11, 13, 23, 17, 19]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 13, 19, 11, 23]\n",
    "print(\"The original list:                 \", x)\n",
    "print(\"Ascending by the value:            \", sorted(x))\n",
    "print(\"Descending by the value:           \", list(reversed(sorted(x))))\n",
    "print(\"or:                                \", sorted(x, key=lambda t: -t))\n",
    "print(\"or (the best approach):            \", sorted(x, reverse=True))\n",
    "print(\"Ascending by the sum of the digits:\", sorted(x, key=lambda t: digit_sum(t)))\n",
    "print(\"or:                                \", sorted(x, key=digit_sum))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The function `sorted` creates a new list with the same elements as the function's argument, but in a sorted order. There is also an in-line version for sorting a list without creating a new one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The original list:                  [17, 13, 19, 11, 23]\n",
      "Ascending by the value:             [11, 13, 17, 19, 23]\n",
      "Descending by the value:            [23, 19, 17, 13, 11]\n",
      "or:                                 [23, 19, 17, 13, 11]\n",
      "Ascending by the sum of the digits: [11, 13, 23, 17, 19]\n",
      "or:                                 [11, 13, 23, 17, 19]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 13, 19, 11, 23]\n",
    "print(\"The original list:                 \", x)\n",
    "x.sort()\n",
    "print(\"Ascending by the value:            \", x)\n",
    "x.sort()\n",
    "x.reverse()\n",
    "print(\"Descending by the value:           \", x)\n",
    "x.sort(reverse=True)\n",
    "print(\"or:                                \", x)\n",
    "x.sort(key=lambda t: digit_sum(t))\n",
    "print(\"Ascending by the sum of the digits:\", x)\n",
    "x.sort(key=digit_sum)\n",
    "print(\"or:                                \", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Membership\n",
    "\n",
    "Does some element exist in a list?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is 17 in lst? True\n",
      "Is 17 not in lst? False\n",
      "Is 19 in lst? True\n",
      "Is 19 not in lst? False\n",
      "Is 11 in lst? False\n",
      "Is 11 not in lst? True\n"
     ]
    }
   ],
   "source": [
    "lst = [17, 13, 23, 17, 19]\n",
    "print(\"Is 17 in lst?\", 17 in lst)\n",
    "print(\"Is 17 not in lst?\", 17 not in lst)\n",
    "print(\"Is 19 in lst?\", 19 in lst)\n",
    "print(\"Is 19 not in lst?\", 19 not in lst)\n",
    "print(\"Is 11 in lst?\", 11 in lst)\n",
    "print(\"Is 11 not in lst?\", 11 not in lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "So, we can check if some element is in the list, but this does not tell us **where** it is, nor **how many** of the list elements are equal to it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Finding a list element\n",
    "\n",
    "One of the more useful list operations is finding an element (any one or all of them) with a given value or some characteristic. Python has a simple way to find one element with a given value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index of the first 17 in the list: 0\n",
      "Index of the first 11 in the list: 2\n"
     ]
    },
    {
     "ename": "ValueError",
     "evalue": "53 is not in list",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-37-ac0e925f2f71>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Index of the first 17 in the list:\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mindex\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m17\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Index of the first 11 in the list:\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mindex\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m11\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Index of the first 53 in the list:\"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mindex\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m53\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mValueError\u001b[0m: 53 is not in list"
     ]
    }
   ],
   "source": [
    "x = [17, 13, 11, 19, 7, 23, 17, 2, 31, 29, 3, 5]\n",
    "print(\"Index of the first 17 in the list:\", x.index(17))\n",
    "print(\"Index of the first 11 in the list:\", x.index(11))\n",
    "print(\"Index of the first 53 in the list:\", x.index(53))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "As you can see, if an element is not found, an error occurs. While this may seem strange, it is a very natural thing in modern languages, as there is a simple way to \"catch\" and \"handle\" errors like that. We will do this on the lectures in two weeks time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Python also makes it easy to find how many times a certain element appears in a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number 17 appears 2 times in the list.\n",
      "Number 11 appears 1 times in the list.\n",
      "Number 53 appears 0 times in the list.\n"
     ]
    }
   ],
   "source": [
    "x = [17, 13, 11, 19, 7, 23, 17, 2, 31, 29, 3, 5]\n",
    "print(\"Number 17 appears\", x.count(17), \"times in the list.\")\n",
    "print(\"Number 11 appears\", x.count(11), \"times in the list.\")\n",
    "print(\"Number 53 appears\", x.count(53), \"times in the list.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "As you can see, one can easily use `count` function to find out if an element exists in a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index of the first 17 in the list: 0\n",
      "Index of the first 11 in the list: 2\n",
      "Number 53 is not in the list.\n"
     ]
    }
   ],
   "source": [
    "x = [17, 13, 11, 19, 7, 23, 17, 2, 31, 29, 3, 5]\n",
    "\n",
    "if x.count(17) != 0:\n",
    "    print(\"Index of the first 17 in the list:\", x.index(17))\n",
    "else:\n",
    "    print(\"Number 17 is not in the list.\")\n",
    "\n",
    "if x.count(11):\n",
    "    print(\"Index of the first 11 in the list:\", x.index(11))\n",
    "else:\n",
    "    print(\"Number 11 is not in the list.\")\n",
    "\n",
    "if x.count(53):\n",
    "    print(\"Index of the first 53 in the list:\", x.index(53))\n",
    "else:\n",
    "    print(\"Number 53 is not in the list.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A somewhat better approach is to just check if an element exists in the list (instead of counting how many times it appears in it):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index of the first 17 in the list: 0\n",
      "Index of the first 11 in the list: 2\n",
      "Number 53 is not in the list.\n"
     ]
    }
   ],
   "source": [
    "x = [17, 13, 11, 19, 7, 23, 17, 2, 31, 29, 3, 5]\n",
    "\n",
    "if 17 in x:\n",
    "    print(\"Index of the first 17 in the list:\", x.index(17))\n",
    "else:\n",
    "    print(\"Number 17 is not in the list.\")\n",
    "\n",
    "if 11 in x:\n",
    "    print(\"Index of the first 11 in the list:\", x.index(11))\n",
    "else:\n",
    "    print(\"Number 11 is not in the list.\")\n",
    "\n",
    "if 53 in x:\n",
    "    print(\"Index of the first 53 in the list:\", x.index(53))\n",
    "else:\n",
    "    print(\"Number 53 is not in the list.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Without using Python specific functions `count` and `index`, we can search for a list element by testing each of them one by one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index of the first 17 in the list: 0\n",
      "Index of the first 11 in the list: 2\n",
      "Index of the first 53 in the list: None\n"
     ]
    }
   ],
   "source": [
    "x = [17, 13, 11, 19, 7, 23, 17, 2, 31, 29, 3, 5]\n",
    "\n",
    "def find(L, x):\n",
    "    \"\"\"\n",
    "    Returns index of `x` in `L`, or `None` if `x` doesn't exist in `L`.\n",
    "    \"\"\"\n",
    "    i = 0\n",
    "    for el in L:\n",
    "        if el == x:\n",
    "            return i\n",
    "        i += 1\n",
    "    return None\n",
    "\n",
    "print(\"Index of the first 17 in the list:\", find(x, 17))\n",
    "print(\"Index of the first 11 in the list:\", find(x, 11))\n",
    "print(\"Index of the first 53 in the list:\", find(x, 53))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This is called [**sequential** or **linear** search](http://en.wikipedia.org/wiki/Linear_search) and it can be easily adapted to different criteria (for example \"in the list `L` find the first/last number with the sum of digits equal to $17$\") and it can be also adapted to find **all** the instances of an element.\n",
    "\n",
    "**Example:** Print **all** the prime numbers in a given list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "Let us first define a function that will check if a given number is a prime:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def is_prime(n):\n",
    "    \"\"\"\n",
    "    Returns `True` if `n` is prime, and `False` otherwise.\n",
    "    \"\"\"\n",
    "    if n < 2:\n",
    "        return False\n",
    "    for i in range(2, n):\n",
    "        if n % i == 0:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A more Pythonic way (not covered in the materials so far):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def is_prime(n):\n",
    "    \"\"\"\n",
    "    Returns `True` if `n` is prime, and `False` otherwise.\n",
    "    \"\"\"\n",
    "    return (n >= 2) and all(n % i for i in range(2, n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "If we were given a list of numbers written on a piece of paper and asked to somehow mark the primes, how would we do it?\n",
    "\n",
    "Probably like this:\n",
    "\n",
    "> Look at the first one. If it is prime, mark it.  \n",
    "> Look at the second one. If it is prime, mark it.  \n",
    "> ...\n",
    "\n",
    "We can do the same here. For simplicity, we will just provide a list of numbers for now (usually, we would have loaded the numbers)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13\n",
      "17\n",
      "2\n",
      "24631669"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "19\n"
     ]
    }
   ],
   "source": [
    "lst = [-17, 13, 26, 17, -1, 0, 1, 2, 165351462, 24631669, 19]\n",
    "for x in lst:\n",
    "    if is_prime(x):\n",
    "        print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "There are faster ways to check if a number is prime. We shall see some of those in the later lectures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Example:** Print **indices** of **all** the prime numbers in a given list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "7\n",
      "9"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "lst = [-17, 13, 26, 17, -1, 0, 1, 2, 165351462, 24631669, 19]\n",
    "for i in range(len(lst)):\n",
    "    if is_prime(lst[i]):\n",
    "        print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "or, a more Pythonic way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, -17), (1, 13), (2, 26), (3, 17), (4, -1), (5, 0), (6, 1), (7, 2), (8, 165351462), (9, 24631669), (10, 19)]\n",
      "1\n",
      "3\n",
      "7\n",
      "9"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "lst = [-17, 13, 26, 17, -1, 0, 1, 2, 165351462, 24631669, 19]\n",
    "print(list(enumerate(lst)))\n",
    "for i, x in enumerate(lst):\n",
    "    if is_prime(x):\n",
    "        print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Example:** Print **indices and values** of **all** the prime numbers in a given list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13, at index 1\n",
      "17, at index 3\n",
      "2, at index 7\n",
      "24631669, at index"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 9\n",
      "19, at index 10\n"
     ]
    }
   ],
   "source": [
    "lst = [-17, 13, 26, 17, -1, 0, 1, 2, 165351462, 24631669, 19]\n",
    "for i in range(len(lst)):\n",
    "    if is_prime(lst[i]):\n",
    "        print(str(lst[i]) + \", at index\", i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or, a more Pythonic way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13, at index 1\n",
      "17, at index 3\n",
      "2, at index 7\n",
      "24631669, at index"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 9\n",
      "19, at index 10\n"
     ]
    }
   ],
   "source": [
    "lst = [-17, 13, 26, 17, -1, 0, 1, 2, 165351462, 24631669, 19]\n",
    "for i, x in enumerate(lst):\n",
    "    if is_prime(x):\n",
    "        print(str(x) + \", at index\", i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exercises\n",
    "\n",
    "Try to write a program that prints value/index/both of:\n",
    "\n",
    "1. only the first prime element; for the above list `lst`, that would be $13$;\n",
    "2. only the second prime element; for the above list `lst`, that would be $17$;\n",
    "3. prime elements with odd indices; for the above list `lst`, those would be all except $19$ (which is at an even index $10$);\n",
    "4. all elements with prime indices; for the above list `lst`, those would be $26$ (index $2$), $17$ (index $3$), $0$ (index $5$), and $2$ (index $7$);\n",
    "5. every second prime in the list, starting from the first one; for the above list `lst`, those would be $13$ (the first one), $2$ (the third one), and $19$ (the fifth one)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Inputing a list\n",
    "\n",
    "It is convenient to define the value of a list in program as we are writing it, so that it doesn't have to be loaded with each test. However, a program with the built-in input values is not very useful. Like integers, reals, and strings, lists also have to be loaded from the user.\n",
    "\n",
    "While there are various Pythonic ways to input a list, depending on what kind of input is requested, we shall show more general ways that should work with all kinds of inputs (and in most of the modern languages that suport data structures similar to Python lists)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Example:** Load a natural number `n`, then load a list of `n` numbers, sort it, and print it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How many numbers do you want to sort? -5\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please type a positive integer: -3\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please type a positive integer: 0\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please type a positive integer: 1\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input a real number: 17\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sorted list: [17.0]\n"
     ]
    }
   ],
   "source": [
    "lst = list()  # Create an empty list\n",
    "n = int(input(\"How many numbers do you want to sort? \"))\n",
    "while n <= 0:\n",
    "    n = int(input(\"Please type a positive integer: \"))\n",
    "for _ in range(n):\n",
    "    lst.append(float(input(\"Input a real number: \")))\n",
    "print(\"The sorted list:\", sorted(lst))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Example:** Input integers until $-17$ is loaded, then print them all (**except** $-17$) sorted descendingly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please type an integer: 2\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please type an integer: 7\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please type an integer: 5\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please type an integer: -17\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sorted list: [7, 5, 2]\n"
     ]
    }
   ],
   "source": [
    "lst = list()  # Create an empty list\n",
    "not_done = True\n",
    "while not_done:\n",
    "    x = int(input(\"Please type an integer: \"))\n",
    "    if x == -17:\n",
    "        not_done = False\n",
    "    else:\n",
    "        lst.append(x)\n",
    "print(\"The sorted list:\", sorted(lst, reverse=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Example:** Input integers until $-17$ is loaded, then print them all (**including** $-17$) sorted descendingly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please type an integer: 5\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please type an integer: -17\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sorted list: [5, -17]\n"
     ]
    }
   ],
   "source": [
    "lst = []  # Create an empty list\n",
    "not_done = True\n",
    "while not_done:\n",
    "    x = int(input(\"Please type an integer: \"))\n",
    "    lst.append(x)\n",
    "    if x == -17:\n",
    "        not_done = False\n",
    "print(\"The sorted list:\", sorted(lst, reverse=True))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Note:** There is a slightly better way to do this, which we shall cover in two weeks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Deleting elements from a list\n",
    "\n",
    "We have already seen one way to remove some element(s) from the list: replacing them with an empty list. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The list:                                       [17, 19, 23, 29, 31, 37]\n",
      "The list without its last two elements:         [17, 19, 23, 29]\n",
      "The list without its third element:             [17, 19, 29]\n",
      "The list with wrongly \"deleted\" second element: [17, [], 29]\n",
      "The list with wrongly \"deleted\" second element: [17, None, 29]\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23, 29, 31, 37]\n",
    "print(\"The list:                                      \", x)\n",
    "x[-2:] = list()\n",
    "print(\"The list without its last two elements:        \", x)\n",
    "x[2:3] = list()\n",
    "print(\"The list without its third element:            \", x)\n",
    "x[1] = list()\n",
    "print('The list with wrongly \"deleted\" second element:', x)\n",
    "x[1] = None\n",
    "print('The list with wrongly \"deleted\" second element:', x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "However, it is much better to use the dedicated [`del`](https://docs.python.org/3/reference/simple_stmts.html#the-del-statement) statement, as it makes the code easier to read and the intention more obvious:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The list:                                       [17, 19, 23, 29, 31, 37]\n",
      "The list without its last two elements:         [17, 19, 23, 29]\n",
      "The list without its third element:             [17, 19, 29]\n",
      "An empty list:                                  []\n"
     ]
    },
    {
     "ename": "NameError",
     "evalue": "name 'x' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-56-548630bf23cb>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      8\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"An empty list:                                 \"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m \u001b[1;32mdel\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 10\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Completely removed variable:                   \"\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m: name 'x' is not defined"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23, 29, 31, 37]\n",
    "print(\"The list:                                      \", x)\n",
    "del x[-2:]\n",
    "print(\"The list without its last two elements:        \", x)\n",
    "del x[2]\n",
    "print(\"The list without its third element:            \", x)\n",
    "del x[:]\n",
    "print(\"An empty list:                                 \", x)\n",
    "del x\n",
    "print(\"Completely removed variable:                   \", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Apart from using somewhat confusing `del x[:]`, we can also empty the list like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The list:                                       [17, 19, 23, 29, 31, 37]\n",
      "An empty list:                                  []\n"
     ]
    }
   ],
   "source": [
    "x = [17, 19, 23, 29, 31, 37]\n",
    "print(\"The list:                                      \", x)\n",
    "x.clear()\n",
    "print(\"An empty list:                                 \", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Note that this is different from `x = list()` which creates a new empty list and assigns it to `x` instead of clearing the elements of `x`. While the result will usually be the same, there is a difference:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The list:                 [17, 19, 23, 29, 31, 37]\n",
      "Whoops! Nothing happened: [17, 19, 23, 29, 31, 37]\n",
      "No more elements:         []\n",
      "The list:                 [17, 19, 23, 29, 31, 37]\n",
      "No more elements:         []\n"
     ]
    }
   ],
   "source": [
    "def clear_through_assignment(x):\n",
    "    \"\"\"Clear the list `x` using the assignment `x = []`.\"\"\"\n",
    "    x = list()\n",
    "\n",
    "def clear_through_clear(x):\n",
    "    \"\"\"Clear the list `x` using `x.clear()`.\"\"\"\n",
    "    x.clear()\n",
    "\n",
    "def clear_through_del(x):\n",
    "    \"\"\"Clear the list `x` using `del x[:]`.\"\"\"\n",
    "    del x[:]\n",
    "\n",
    "x = [17, 19, 23, 29, 31, 37]\n",
    "print(\"The list:                \", x)\n",
    "clear_through_assignment(x)\n",
    "print(\"Whoops! Nothing happened:\", x)\n",
    "clear_through_clear(x)\n",
    "print(\"No more elements:        \", x)\n",
    "\n",
    "x = [17, 19, 23, 29, 31, 37]\n",
    "print(\"The list:                \", x)\n",
    "clear_through_del(x)\n",
    "print(\"No more elements:        \", x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Wrap it up\n",
    "\n",
    "**Example:** Write a program that loads integers until it loads a zero (which is not included in the subsequent computations), and then writes:\n",
    "\n",
    "1. the arithmetic mean of all the loaded numbers,\n",
    "2. the [median](http://en.wikipedia.org/wiki/Median) of all the loaded numbers,\n",
    "3. all the loaded numbers bigger than or equal to the median, in their original order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Arithmetic mean** should be easy enough to compute. It is simply the sum of the loaded numbers divided by how many of them there are.\n",
    "\n",
    "Notice that if we load no numbers, the arithmetic mean is $0/0$, which is undefined. We have to make sure that the program behaves properly in this case.\n",
    "\n",
    "**The median** of a list is the numerical value separating the higher half of data from the lower half. For the finite data, this simply means sorting the list and taking the middle element (if the list has an odd length) or an arithmetic mean of the two middle elements (if the list has an even length).\n",
    "\n",
    "**Printing** the numbers bigger than some given number is a simple matter of running through the list and printing those that satisfy an appropriate condition. However, there are two things to consider:\n",
    "\n",
    "1. The original order of the list elements is required.  \n",
    "   This means that we need to preserve the original ordering. In other words, we must not sort the existing list to find the mean, but we need to create a new sorted list for that purpose, preserving the original one.\n",
    "\n",
    "2. Printing one number in each line is not always desirable.  \n",
    "   We shall create a new list of numbers that are bigger than the mean, and then print it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "# Input:\n",
    "lst = list()  # Create an empty list\n",
    "not_done = True\n",
    "while not_done:\n",
    "    x = int(input(\"Please type an integer: \"))\n",
    "    if x == 0:\n",
    "        not_done = False\n",
    "    else:\n",
    "        lst.append(x)\n",
    "\n",
    "# Check that the list has a non-zero length\n",
    "if len(lst) == 0:\n",
    "    print(\"Cowardly refusing to work with means and medians of an empty list!\")\n",
    "    sys.exit(1)\n",
    "\n",
    "# We'll need this several times, so better put it in a variable\n",
    "list_length = len(lst)\n",
    "\n",
    "# Find the arithmetic mean\n",
    "mean = 0\n",
    "for x in lst:\n",
    "    mean += x\n",
    "mean /= list_length\n",
    "\n",
    "# Find the median\n",
    "sorted_list = sorted(lst)\n",
    "median_index = list_length // 2\n",
    "if list_length % 2 == 0:\n",
    "    # The length of the list is even\n",
    "    median = (sorted_list[median_index - 1] + sorted_list[median_index]) / 2\n",
    "else:\n",
    "    # The length of the list is odd\n",
    "    median = sorted_list[median_index]\n",
    "\n",
    "# Create the list of elements bigger than or equal to the median\n",
    "list_bigger = list()\n",
    "for x in lst:\n",
    "    if x >= median:\n",
    "        list_bigger.append(x)\n",
    "\n",
    "# Print the results\n",
    "print(\"Arithmetic mean:\", mean)\n",
    "print(\"Median:\", median)\n",
    "print(\"Elements >= median:\", list_bigger)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "**Note:** `sys.exit(1)` is used to stop a program's execution (it doesn't work in IPython). The number in the parenthesis can be any integer and it should be zero if the program successfully did what it had to do, or a non-zero value unique for each of the errors for which the program was stopped. Here, we used $1$ to describe \"the list is empty, hence we cannot work with it\".\n",
    "\n",
    "In order for `sys.exit(...)` to work, we need `import sys` somewhere before it (almost always at the beginning of the program)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A more Pythonic solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "# Input:\n",
    "lst = []  # Create an empty list\n",
    "while True:\n",
    "    x = int(input(\"Please type an integer: \"))\n",
    "    if x == 0:\n",
    "        break\n",
    "    lst.append(x)\n",
    "\n",
    "# Check that the list has a non-zero length\n",
    "if len(lst) == 0:\n",
    "    print(\"Cowardly refusing to work with means and medians of an empty list!\")\n",
    "    sys.exit(1)\n",
    "\n",
    "# We'll need this several times, so better put it in a variable\n",
    "list_length = len(lst)\n",
    "\n",
    "# Find the median\n",
    "sorted_list = sorted(lst)\n",
    "median_index = list_length // 2\n",
    "median = sorted_list[median_index] if list_length % 2 else \\\n",
    "    sum(sorted_list[median_index-1:median_index+1]) / 2\n",
    "\n",
    "# Print the results\n",
    "print(\"Arithmetic mean:\", sum(lst) / list_length)\n",
    "print(\"Median:\", median)\n",
    "print(\"Elements >= median:\", [x for x in lst if x >= median])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or, using `NumPy` (a widely used numerical library for Python):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# Input:\n",
    "lst = []  # Create an empty list\n",
    "while True:\n",
    "    x = int(input(\"Please type an integer: \"))\n",
    "    if x == 0:\n",
    "        break\n",
    "    lst.append(x)\n",
    "\n",
    "if len(lst) == 0:\n",
    "    print(\"Cowardly refusing to work with means and medians of an empty list!\")\n",
    "else:\n",
    "    median = np.median(lst)\n",
    "    print(\"Arithmetic mean:\", sum(lst) / len(lst))\n",
    "    print(\"Median:\", median)\n",
    "    print(\"Elements >= median:\", [x for x in lst if x >= median])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or, using `statistics` (a Python library of statistical functions, available since Python 3.4):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import statistics\n",
    "\n",
    "# Input:\n",
    "lst = []  # Create an empty list\n",
    "while True:\n",
    "    x = int(input(\"Please type an integer: \"))\n",
    "    if x == 0:\n",
    "        break\n",
    "    lst.append(x)\n",
    "\n",
    "try:\n",
    "    median = statistics.median(lst)\n",
    "except StatisticsError:\n",
    "    print(\"Cowardly refusing to work with means and medians of an empty list!\")\n",
    "else:\n",
    "    print(\"Arithmetic mean:\", statistics.mean(lst))\n",
    "    print(\"Median:\", median)\n",
    "    print(\"Elements >= median:\", [x for x in lst if x >= median])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Iterables\n",
    "\n",
    "Lists are one type of Python's *iterables* -- objects that contain some members that can be accessed one at a time. In other words, any variable `var` contains an iterable if you can iterate through it:\n",
    "\n",
    "```python\n",
    "for some_other_var in var:\n",
    "    ...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "While each iterable has its own specific characteristics and/or operations, they are generally used in the same manner as lists. Their functionality can be, with more or less effort, emulated by lists (and is often done like that in some of the other languages).\n",
    "\n",
    "We now bring a short preview of some other iterables that exist in Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Other built-in iterables\n",
    "\n",
    "Python has several built-in data structures other than lists."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tuples\n",
    "\n",
    "A [tuple](https://docs.python.org/3/library/stdtypes.html#sequence-types-list-tuple-range) is basically an immutable (unchangeable) list. It can be assigned a new value (as any variable), but its elements cannot be changed or deleted, nor can the new ones be added.\n",
    "\n",
    "A tuple is defined simlarly to a list, but the values are enclosed in parentheses."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "an_empty_tuple = tuple()\n",
    "a_less_preferred_empty_tuple = ()\n",
    "a_tuple = (17, 13, 19, 23)\n",
    "print(\"A tuple:                                               \", a_tuple)\n",
    "print(\"Its first element:                                     \", a_tuple[0])\n",
    "print(\"Its last element:                                      \", a_tuple[-1])\n",
    "print(\"Without the first and the last element:                \", a_tuple[1:-1])\n",
    "print(\"A sorted tuple:                                        \", sorted(a_tuple))\n",
    "another_tuple = (1, 2, 3)\n",
    "print(\"Another tuple appended to the first one:               \", a_tuple + another_tuple)\n",
    "print(\"Another tuple inserted in the middle of the first one: \",\n",
    "      a_tuple[:2] + another_tuple + a_tuple[2:])\n",
    "print(\"All the membership stuff works, i.e., is 17 in a tuple:\", 17 in a_tuple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Notice that\n",
    "```python\n",
    "a_tuple.extend(another_tuple)\n",
    "```\n",
    "and\n",
    "```python\n",
    "a_tuple.insert(position, another_tuple)\n",
    "```\n",
    "would not work because `a_tuple` is a tuple and cannot be changed. For the same reason, `reverse` and `sort` wouldn't work either, but `sorted` and `reversed` would. Furthermore, `sorted(a_tuple)` returns a (new) **list** with the same elements that `a_tuple` had, ordered as required.\n",
    "\n",
    "However, we can insert a tuple's elements into a list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = [17, 19, 23]  # a list\n",
    "y = (13, 11, 7)  # a tuple\n",
    "x.extend(y)  # append the tuple y to the list x\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Since `y` is a tuple (i.e., immutable), the opposite won't work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = [17, 19, 23]  # a list\n",
    "y = (13, 11, 7)  # a tuple\n",
    "y.extend(x)  # append the list x to the tuple y\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "**Note:** Be careful when creating single-element tuples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = (1)\n",
    "y = (1,)\n",
    "print(\"An integer:             {:4} (type: {})\".format(x, type(x)))\n",
    "print(\"A single-element tuple: {:4} (type: {})\".format(y, type(y)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Tuples are often used for multiple assignments. For example, a traditional way to swap two variables is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = input(\"x = \")\n",
    "y = input(\"y = \")\n",
    "\n",
    "temp = x\n",
    "x = y\n",
    "y = temp\n",
    "\n",
    "print(\"x =\", x)\n",
    "print(\"y =\", y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "However, using tuples, it boils down to:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = input(\"x = \")\n",
    "y = input(\"y = \")\n",
    "\n",
    "(x, y) = (y, x)\n",
    "\n",
    "print(\"x =\", x)\n",
    "print(\"y =\", y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The parentheses are not needed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = input(\"x = \")\n",
    "y = input(\"y = \")\n",
    "\n",
    "x, y = y, x\n",
    "\n",
    "print(\"x =\", x)\n",
    "print(\"y =\", y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Another common use for them is returning more than one value from a function. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def modiv(x, y):\n",
    "    \"\"\"Returns mod and div together, i.e., x//y and x%y.\"\"\"\n",
    "    return x // y, x % y\n",
    "\n",
    "a, b = modiv(19, 17)\n",
    "print(\"19 // 17 =\", a)\n",
    "print(\"19 % 17 = \", b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To ignore one or more of the return values, one can use a \"throwaway variable\" `_`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a, _ = modiv(19, 17)\n",
    "print(\"19 // 17 =\", a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Note that this is **not** the same as"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = modiv(19, 17)\n",
    "print(\"19 // 17 =\", a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The above can also be done with lists (although it almost never is).\n",
    "\n",
    "So, why would anyone want a list with reduced functionality (i.e., without the ability to change)?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Traversing both the indices and the elements of an iterator\n",
    "\n",
    "Sometimes, using \"`for x in L`\" or \"`for i in range(len(L))`\" is not enough because we need both the index and the value of each element. Of course, we can always do\n",
    "```python\n",
    "for i in range(len(L)):\n",
    "    print(\"index:\", i)\n",
    "    print(\"value:\", L[i])\n",
    "```\n",
    "but there is a more Pythonic (and easier way): the function [`enumerate`](https://docs.python.org/3/library/functions.html#enumerate) which returns an iterator of two-member tuples, each containing the index and the value of the given iterator.\n",
    "\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "L = [ 17, 19, 23 ]\n",
    "print(list(enumerate(L)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A more common way to use this is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "L = [ 17, 19, 23 ]\n",
    "for idx, el in enumerate(L):\n",
    "    print(\"L[{}] = {}\".format(idx, el))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can also have the index counter start from a value other than zero. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "L = [ 17, 19, 23 ]\n",
    "for idx, el in enumerate(L, start=1):\n",
    "    print(\"Position #{} in L has the value {}.\".format(idx, el))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The argument's name \"`start`\" can be ommited, but it's better to leave it for clarity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Sets\n",
    "\n",
    "A set is like a list in which all elements are unique and they have no ordering defined (hence, we cannot index its elements). Sets are changed by using the standard sets operations, and the membership is checked in the same manner that it was check with lists and tuples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "an_empty_set = set()\n",
    "this_is_NOT_a_set = {}\n",
    "a = {17, 13, 19, 23}\n",
    "b = {11, 17, 19, 31}\n",
    "c = {17, 19, 13}\n",
    "print(\"a:                          \", a)\n",
    "print(\"b:                          \", b)\n",
    "print(\"The union of a and b:       \", a.union(b))\n",
    "print(\"  or:                       \", a | b)\n",
    "print(\"The intersection of a and b:\", a.intersection(b))\n",
    "print(\"  or:                       \", a & b)\n",
    "print(\"Difference a \\\\ b:           \", a.difference(b))\n",
    "print(\"  or:                       \", a - b)\n",
    "print(\"Symmetric difference a △ b: \", a.symmetric_difference(b))\n",
    "print(\"  or:                       \", a ^ b)\n",
    "print(\"Is 17 in the set a union b? \", 17 in a|b)\n",
    "print(\"Is c a subset of a?         \", c.issubset(a))\n",
    "print(\"  or:                       \", c <= a)\n",
    "print(\"Is c a strict subset of a?  \", c < a)\n",
    "print(\"Is c a superset of a?       \", c.issuperset(a))\n",
    "print(\"  or:                       \", c >= a)\n",
    "print(\"Is c a strict superset of a?\", c > a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Sets are muttable because they can be changed using their functions `update`, `intersection_update`, `difference_update`, and `symmetric_difference_update`. Immutable version of a set is called `frozenset`. You can read more about both in the [official Python documentation for `set` and `frozenset`](https://docs.python.org/3/library/stdtypes.html#set)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Dictionaries\n",
    "\n",
    "A [dictionary](https://docs.python.org/3/library/stdtypes.html#mapping-types-dict) is like a list that uses indices of various types, not just zero-based integers. These \"indices\" are called *keys*.\n",
    "\n",
    "There are many ways to define a dictionary. This is from the official Python documentation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = dict(one=1, two=2, three=3)\n",
    "b = {'one': 1, 'two': 2, 'three': 3}\n",
    "c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))\n",
    "d = dict([('two', 2), ('one', 1), ('three', 3)])\n",
    "e = dict({'three': 3, 'one': 1, 'two': 2})\n",
    "a == b == c == d == e"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "An empty dictionary should be defined by"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "an_empty_dictionary = dict()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "even though `an_empty_dictionary = {}` would also work. The latter should be avoided due to ambiguity (it can easily be confused for an empty set)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Accessing all the elements of a dictionary, one by one\n",
    "\n",
    "We can use `for` to access the elements of a dictionary one by one (in an order that is not predetermined):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for key in a:\n",
    "    print(key, \"->\", d[key])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "or, through keys and values together, using a function `a.items` that returns a dictionary as a list of `(key, value)` tuples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for key, value in a.items():\n",
    "    print(key, \"->\", value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Since the default sort of a list of tuple will first compare the first elements of the tuples, then the second ones, etc, we can easily access the items sorted by their key values (incidentally revealing the original quote by "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for key, value in sorted(a.items()):\n",
    "    print(key, \"->\", value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Of course, Python does not interpret \"one\", \"two\", and \"three\", so the keys are sorted alphabetically (often called *lexically*)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Printing a dictionary\n",
    "\n",
    "A dictionary can be printed using `print`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "However, this is usually hard to read:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "d = {\n",
    "    \"xyz\": \"something\",\n",
    "    \"2\": 1719,\n",
    "    1719: [1, 2, [3, \"python\"], (\"a\", 13)],\n",
    "    \"xyz\": \"something else\",\n",
    "    (1,0): \"the key is a tuple\",\n",
    "}\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "There is a nicer way to print a dictionary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pprint import pprint\n",
    "pprint(d, indent=4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We can also write our own function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def dict_print(name, d, indent=4):\n",
    "    \"\"\"\n",
    "    Very crude pretty printer for dictionaries\n",
    "    \n",
    "    Parameters:\n",
    "    `name`:\n",
    "        The name to be printed on top of the data.\n",
    "    `d`:\n",
    "        The dictionary to be printed.\n",
    "    `indent`:\n",
    "        Number of spaces to prepend to each of the printed lines.\n",
    "    \"\"\"\n",
    "    print(name + \":\")\n",
    "    for key, value in d.items():\n",
    "        print(\" \" * (indent-1), \"*\", key, \"->\", value)\n",
    "\n",
    "dict_print(\"Dictionary d\", d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Note that the multiple values assigned to the same key will override each other: `\"something\"` was overriden by `\"something else\"` because we tried to assign both of them to the key `\"xyz\"`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "As we can see above, the values in a dictonary can be whatever we want. However, the keys cannot be exactly anything. Mutables, like lists, cannot be used as keys:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = {\n",
    "    \"1719\": \"A string is OK\",\n",
    "    (17, 19): \"A tuple is also OK\",\n",
    "    [17, 19]: \"A list is not\",\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before using the values of a certain type as keys, it is always best to try out if it will actually work, or the code needs to be done differently. If the desired type cannot be used for keys, we can usually fix it by converting what we want to use as keys to a more appropriate data type. For example, lists are trivially converted to tuples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Of course, when keys or values hold the values of uncomparable types, we cannot sort them (an error will occur):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for key, value in sorted(d.items()):\n",
    "    print(\" \" * (indent-1), \"*\", key, \"->\", value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Adding, changing, and deleting the data\n",
    "\n",
    "Much like sets, dictionaries don't have the \"first\", the \"second\", etc. element.\n",
    "\n",
    "Adding new data or changing the existing one is done by using its key:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "d = {\n",
    "    \"xyz\": \"something\",\n",
    "    \"2\": 1719,\n",
    "    1719: [1, 2, [3, \"python\"], (\"a\", 13)],\n",
    "    \"xyz\": \"something else\",\n",
    "    (1,0): \"the key is a tuple\",\n",
    "}\n",
    "\n",
    "dict_print(\"Dictionary d\", d, indent=4)\n",
    "d[\"this is also a key\"] = \"something added\"\n",
    "d[\"xyz\"] = \"something changed\"\n",
    "dict_print(\"Changed dictionary d\", d, indent=4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To delete the data, we can simply use `del`, like with lists:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "del d[(1,0)], d[\"xyz\"]\n",
    "dict_print(\"Dictionary d with some keys removed\", d, indent=4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Using `for` with a dictionary\n",
    "\n",
    "When `for` is directly used with a dictionary, it gives us the items' **keys** in some order:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "d = {\n",
    "    \"first\": \"going once\",\n",
    "    \"second\": \"going twice\",\n",
    "    \"third\": \"sold\"\n",
    "}\n",
    "for x in d:\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This is enough to get the values as well:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "d = {\n",
    "    \"first\": \"going once\",\n",
    "    \"second\": \"going twice\",\n",
    "    \"third\": \"sold\"\n",
    "}\n",
    "for x in d:\n",
    "    print('d[\"{}\"] = \"{}\"'.format(x, d[x]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "However, there is a better way, very much alike `enumerated` call that we have shown above:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "d = {\n",
    "    \"first\": \"going once\",\n",
    "    \"second\": \"going twice\",\n",
    "    \"third\": \"sold\"\n",
    "}\n",
    "for key, value in d.items():\n",
    "    print('d[\"{}\"] = \"{}\"'.format(key, value))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Converting between iterables\n",
    "\n",
    "Converting between lists, sets, and tuples can be easily done with their namesake functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lst = [17, 19, 11, 23]\n",
    "print(\"List:\")\n",
    "print(\"  - as a list: \", lst)\n",
    "print(\"  - as a tuple:\", tuple(lst))\n",
    "print(\"  - as a set:  \", set(lst))\n",
    "tup = (17, 19, 11, 23)\n",
    "print(\"Tup:\")\n",
    "print(\"  - as a list: \", list(tup))\n",
    "print(\"  - as a tuple:\", tup)\n",
    "print(\"  - as a set:  \", set(tup))\n",
    "st = {17, 19, 11, 23}\n",
    "print(\"Set:\")\n",
    "print(\"  - as a list: \", list(st))\n",
    "print(\"  - as a tuple:\", tuple(st))\n",
    "print(\"  - as a set:  \", st)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "In lists and tuples, the keys are assigned in order: 0, 1,...; in sets, they are simply disregarded. However, dictionaries are a bit more complex, as Python cannot just make the keys up.\n",
    "\n",
    "One way to create a dictionary is from a list, tuple, or a set of two-member lists, tuples, or sets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "d = dict([ (17, 19), {\"a\", \"b\"}, [13, 11]])\n",
    "dict_print(\"d\", d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Notice that sets do not define the order of their elements, so keys and values may end up swapped."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "More often we want to create a dictionary from two lists, tuples, or sets, one containing keys and another containing their corresponding values. For this purpose, we use the built-in function [`zip`](https://docs.python.org/3/library/functions.html#zip). Of course, the lengths of these two lists must be equal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "keys = [\"a\", \"b\", (1,0)]\n",
    "values = (1, {17, 19}, \"xyz\")\n",
    "print(list(zip(keys, values)))\n",
    "dict_print(\"A dictionary created from a list and a tuple\", dict(zip(keys, values)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, sets are unreliable for this purpose, due to the lack of their elements' ordering."
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 0
}