10-more-lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8z5cONg8rUrX",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Working with lists\n",
    "\n",
    "## Programming Fundamentals (NB10)\n",
    "\n",
    "### MIEIC/2020-21\n",
    "\n",
    "#### João Correia Lopes\n",
    "\n",
    "FEUP/DEI and INESC TEC"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "MZzE7pYorju5",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Goals\n",
    "\n",
    "By the end of this class, the student should be able to:\n",
    "\n",
    "- Use the main methods available to work with lists\n",
    "\n",
    "- Use generalised `for` loops with lists\n",
    "\n",
    "- Describe pure functions and modifiers (that make *side-effects*)\n",
    "\n",
    "- Describe type conversions (`list` and `range`)\n",
    "\n",
    "- Use nested lists to work with matrices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "eR5Lh1jNroE2",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Bibliography\n",
    "\n",
    "- Peter Wentworth, Jeffrey Elkner, Allen B. Downey, and Chris Meyers, *How to Think Like a Computer Scientist — Learning with Python 3* (Section 5.3)\n",
    "\n",
    "- Brad Miller and David Ranum, Learning with Python: Interactive Edition. Based on material by Jeffrey Elkner, Allen B. Downey, and Chris Meyers (Chapter 10)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xoyVeYtG9dP_",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Data types: Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SvEjkKDXnaaA",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### A compound data type (recap)\n",
    "\n",
    "- So far we have seen built-in types like `int`, `float`, `bool`,\n",
    "    `str` and we've seen lists and pairs\n",
    "\n",
    "- Strings, **lists**, and tuples are qualitatively different from the\n",
    "    others because they are made up of smaller pieces\n",
    "\n",
    "- **Lists (and tuples) group any number of items, of different types,\n",
    "    into a single compound value**\n",
    "\n",
    "- Types that comprise smaller pieces are called **collection** or\n",
    "    **compound data types**\n",
    "\n",
    "- Depending on what we are doing, we may want to treat a compound data\n",
    "    type as a single thing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "9tZKDON_IwFg",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## 5.3.12 Lists and for loops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "vTCz3m6inp7g",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Lists and `for` loops\n",
    "\n",
    "- The `for` loop also works with lists, as we've already seen\n",
    "\n",
    "- The generalized syntax of a `for` loop is:\n",
    "\n",
    "```\n",
    "   for <VARIABLE> in <LIST>:\n",
    "       <BODY>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "iuQclvxaBOG8",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\"For (every) friend in (the list of) friends, print (the name of the) friend\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "gVSlhxo2BDA7",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "friends = [\"Joe\", \"Zoe\", \"Brad\", \"Angelina\", \"Zuki\", \"Thandi\", \"Paris\"]\n",
    "for friend in friends:\n",
    "    print(friend)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wx5xbc8Vn4ha",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### List expressions in for loops\n",
    "\n",
    "\n",
    "- Any list expression can be used in a `for` loop\n",
    "\n",
    "- `enumerate` generates pairs of both *(index, value)* during the list\n",
    "    traversal\n",
    "\n",
    "```\n",
    "   xs = [1, 2, 3, 4, 5]\n",
    "\n",
    "   for (i, val) in enumerate(xs):\n",
    "       xs[i] = val**2\n",
    "```\n",
    "\n",
    "$\\Rightarrow$ \n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/10/for-lists.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "u69dF0B6yCrS",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Any list expression can be used in a for loop:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Kv91rTEbx7eH",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for fruit in [\"banana\", \"apple\", \"quince\"]:\n",
    "    print(\"I like to eat \" + fruit + \"s!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7t0yPDhGyNq8",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Since lists are *mutable*, we often want to traverse a list, changing each of its elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "TK9FhCCTyTRe",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "xs = [1, 2, 3, 4, 5]\n",
    "\n",
    "for i in range(len(xs)):\n",
    "    xs[i] = xs[i]**2\n",
    "\n",
    "print(xs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "OCWQ0sXEyfa7",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Often we are interested in the value and also in the index; and there's a *pattern* in Python for that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "6j2fZYO6yaaj",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "xs = [1, 2, 3, 4, 5]\n",
    "\n",
    "for (i, val) in enumerate(xs):\n",
    "    xs[i] = val**2\n",
    "\n",
    "print(xs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rgRJaKLQyrJ6",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "`enumerate` generates pairs of both `(index, value)` during the list traversal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ImXaYiSoyxCC",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "for (i, v) in enumerate([\"banana\", \"apple\", \"pear\", \"lemon\"]):\n",
    "    print(i, v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "LsWiW_k2oET7",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.3.13 List parameters\n",
    "\n",
    "- Passing a list as a function argument actually passes a *reference* to the\n",
    "    list, **not a copy** or clone of the list\n",
    "\n",
    "- So parameter passing creates an alias<sup>1</sup>\n",
    "\n",
    "```\n",
    "  def double_stuff(things):\n",
    "      \"\"\" Overwrite each element in a_list with double its value. \"\"\"\n",
    "      ...\n",
    "  a_list = [2, 5, 9]\n",
    "  double_stuff(a_list)\n",
    "```\n",
    "\n",
    "<sup>1</sup> The caller has one variable referencing the list, and the called\n",
    "    function has an alias, but there is only one underlying list object"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "\n",
    "![double_stuff](images/10/double_stuff.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try it here:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "G9lw6mlvzAFT",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# A modifier or inpure function (see later)\n",
    "def double_stuff(a_list):\n",
    "    \"\"\" Overwrite each element in a_list with double its value. \"\"\"\n",
    "    for (index, stuff) in enumerate(a_list):\n",
    "        a_list[index] = 2 * stuff\n",
    "\n",
    "things = [2, 5, 9]\n",
    "print(things)\n",
    "\n",
    "double_stuff(things)\n",
    "print(things)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0wqO_CrOCc4H",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "See it in [Python tutor](http://www.pythontutor.com/visualize.html#code=%23%20A%20modifier%20or%20inpure%20function%20%28see%20later%29%0Adef%20double_stuff%28a_list%29%3A%0A%20%20%20%20%22%22%22%20Overwrite%20each%20element%20in%20a_list%20with%20double%20its%20value.%20%22%22%22%0A%20%20%20%20for%20%28index,%20stuff%29%20in%20enumerate%28a_list%29%3A%0A%20%20%20%20%20%20%20%20a_list%5Bindex%5D%20%3D%202%20*%20stuff%0A%0Athings%20%3D%20%5B2,%205,%209%5D%0Aprint%28things%29%0A%0Adouble_stuff%28things%29%0Aprint%28things%29&cumulative=false&curInstr=14&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false), now!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "whdHu_ClI3uP",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## 5.3.14 List methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rjC_4AQvue81",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### List methods\n",
    "\n",
    "- The dot operator can also be used to access built-in methods of list\n",
    "    objects\n",
    "\n",
    "```\n",
    "    >>> mylist = []\n",
    "    >>> mylist.append(5)      # Add 5 onto the end of mylist\n",
    "    >>> mylist.append(12)\n",
    "    >>> mylist\n",
    "    [5, 12]\n",
    "\n",
    "    >>> mylist.insert(1, 12)  # Insert 12 at pos 1, shift others\n",
    "    >>> mylist.count(12)      # How many times is 12 in mylist?\n",
    "\n",
    "    >>> mylist.extend([5, 9, 5, 11])\n",
    "    >>> mylist.index(9)       # Find index of first 9 in mylist\n",
    "    >>> mylist.reverse()\n",
    "    >>> mylist.sort()\n",
    "    >>> mylist.remove(12)     # Remove the first 12 in mylist\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "GnDR_NxF8BrV",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### List Methods (summary)\n",
    "\n",
    "| Method  | Parameters      | Result   | Description  |\n",
    "|:--------|:----------------|:---------|:-------------|\n",
    "| append  | item            | mutator  | Adds a new item to the end of a list  |\n",
    "| extend  | iterable        | mutator  | Adds the iterable elements to the end of a list  |\n",
    "| insert  | position, item  | mutator  | Inserts a new item at the position given  |\n",
    "| pop     | none            | hybrid   | Removes and returns the last item  |\n",
    "| pop     | position        | hybrid   | Removes and returns the item at position  |\n",
    "| sort    | none            | mutator  | Modifies a list to be sorted  |\n",
    "| reverse | none            | mutator  | Modifies a list to be in reverse order  |\n",
    "| index   | item            | return idx | Returns the position of first occurrence of item  |\n",
    "| count   | item            | return ct  | Returns the number of occurrences of item  |\n",
    "| remove  | item            | mutator  | Removes the first occurrence of item  |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "- **mutator** means that the list is changed by the method but nothing is returned (actually `None` is returned)\n",
    "- **hybrid** method is one that not only changes the list but also returns a value as its result. \n",
    "- if the result is simply a **return**, then the list is unchanged by the method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SJjOm5VBI8d2",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## 5.3.15 Pure functions and modifiers (make *side-effects*)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "k0GEbt0HuoE6",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Pure functions and modifiers\n",
    "\n",
    "\n",
    "- As seen before, *there is a difference between a pure function and\n",
    "    one with side-effects*\n",
    "\n",
    "- Functions which take lists as arguments and change them during\n",
    "    execution are called **modifiers** and the changes they make are\n",
    "    called **side effects**\n",
    "\n",
    "- A **pure function** does not produce side effects\n",
    "\n",
    "    - It communicates with the calling program only through\n",
    "        parameters, which it does not modify, and a return value\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/10/double_stuff.py>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "YO6bfKASzRSq",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A version of `double_stuff()` as a pure function (does not change its arguments):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "tPEeRoXozVKX",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def double_stuff2(a_list):\n",
    "    \"\"\" Return a new list which contains doubles of the elements in a_list. \"\"\"\n",
    "    new_list = []\n",
    "    for value in a_list:\n",
    "        new_elem = 2 * value\n",
    "        new_list.append(new_elem)\n",
    "    return new_list\n",
    "\n",
    "things = [2, 5, 9]\n",
    "print(things)\n",
    "\n",
    "double_stuff2(things)\n",
    "print(things)\n",
    "\n",
    "things = double_stuff2(things)\n",
    "print(things)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "9Ls3g-PgDlwN",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "See it in [Python tutor](http://www.pythontutor.com/visualize.html#mode=edit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BNdgVyqPEA1u",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Functional Programming (style)\n",
    "\n",
    "- Anything that can be done with modifiers can also be done with pure functions. \n",
    "- In fact, some programming languages only allow pure functions (                               [Scheme](https://en.wikipedia.org/wiki/Scheme_(programming_language) ), [Haskel](https://en.wikipedia.org/wiki/Haskell_(programming_language) )). \n",
    "- There is some evidence that programs that use pure functions are faster to develop and less error-prone than programs that use modifiers. \n",
    "- Nevertheless, modifiers are convenient at times, and in some cases, functional programs are less efficient.\n",
    "\n",
    "\n",
    "> In general, it is recommended that you write pure functions whenever it is reasonable to do so and resort to modifiers only if there is a compelling advantage."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7jnRns3sEnEw",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.3.16 Functions that produce lists\n",
    "\n",
    "- Whenever you need to write a function that creates and returns a\n",
    "    list, the *pattern* is usually:\n",
    "\n",
    "```\n",
    "   initialize a result variable to be an empty list\n",
    "   loop\n",
    "      create a new element\n",
    "      append it to result\n",
    "   return the result\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "TYLk2f-mvAD8",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "```\n",
    "   def primes_lessthan(n):\n",
    "       \"\"\" Return a list of all prime numbers less than n. \"\"\"\n",
    "       result = []\n",
    "       for i in range(2, n):\n",
    "           if is_prime(i):\n",
    "               result.append(i)\n",
    "   return result\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ud3yYphvvWIJ",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.3.17 Strings and lists\n",
    "\n",
    "\n",
    "- Two of the most useful methods on strings involve conversion to and\n",
    "    from lists of substrings\n",
    "\n",
    "- The `split` method breaks a string into a list of words\n",
    "\n",
    "- By default, any number of whitespace characters is considered a word\n",
    "    boundary\n",
    "\n",
    "- An optional argument called a **delimiter** can be used to specify\n",
    "    which string to use as the boundary marker between substrings\n",
    "\n",
    "- The inverse of the `split` method is `join`\n",
    "\n",
    "- You choose a desired **separator** string and join the list with the\n",
    "    glue between each of the elements\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/10/strings.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Js_VF_Njzl62",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "gIe-sa4Lzo0C",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "song = \"The rain in Spain stays mainly in the plain!\"\n",
    "words = song.split()\n",
    "print(words)\n",
    "\n",
    "words = song.split(\"ai\")\n",
    "print(words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aBgl5B2P0KlT",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Join"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "iPN_soRM0HmF",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "words = song.split()\n",
    "glue = \";\"\n",
    "phrase = glue.join(words)\n",
    "print(phrase)\n",
    "\n",
    "print(\" --- \".join(words))\n",
    "print(\"\".join(words))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6kh_ynd8Ff9q",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "What is printed by the following statements?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "HFY8P4RBFiI5",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "myname = \"Edgar Allan Poe\"\n",
    "namelist = myname.split()\n",
    "init = \"\"\n",
    "\n",
    "for aname in namelist:\n",
    "    init = init + aname[0]\n",
    "\n",
    "print(init)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "fthNH83pJGM7",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.3.18 Type conversions: list and range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "S7VSrJtov4hu",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### `list`\n",
    "\n",
    "- Python has a built-in type conversion function called `list` that\n",
    "    tries to turn whatever you give it into a list\n",
    "\n",
    "```\n",
    "   >>> letters = list(\"Crunchy Frog\")\n",
    "   >>> letters\n",
    "   [\"C\", \"r\", \"u\", \"n\", \"c\", \"h\", \"y\", \" \", \"F\", \"r\", \"o\", \"g\"]\n",
    "   >>> \"\".join(letters)\n",
    "   'Crunchy Frog'\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "vzKJzuNdv9Es",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### `range`\n",
    "\n",
    "\n",
    "- One particular feature of `range` is that it doesn't instantly\n",
    "    compute all its values:\n",
    "\n",
    "    - it \"puts off\" the computation, and does it on demand, or\n",
    "        \"lazily\"\n",
    "\n",
    "    - We'll say that it gives a **promise** to produce the values when\n",
    "        they are needed\n",
    "\n",
    "    - This is very convenient if your computation short-circuits a\n",
    "        search and returns early\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/10/lazy-eval.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "KSYEZWZf0kKj",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Before Python3, *range* was not lazy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "y3FjUUfA0vYw",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def f(n):\n",
    "    \"\"\" Find the first positive integer between 101 and less\n",
    "        than n that is divisible by 21\n",
    "    \"\"\"\n",
    "    for i in range(101, n):\n",
    "        if (i % 21 == 0):\n",
    "            return i\n",
    "\n",
    "print(f(110))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kCWohqNO06Hs",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "If range were to *eagerly* go about building a list with all those elements, you would soon exhaust your computer’s available memory and crash the program:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "48Mfojan1DeY",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "print(f(1000000000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "539Wtkv2wAUa",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### `list` and `range`\n",
    "\n",
    "- You'll sometimes find the lazy range wrapped in a call to list\n",
    "\n",
    "- This forces Python to turn the *lazy promise* into an actual list\n",
    "\n",
    "```\n",
    "   >>> range(10)          # Create a lazy promise\n",
    "   range(0, 10)\n",
    "\n",
    "   >>> list(range(10))    # Call in the promise, to produce a list\n",
    "   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "gcqczAxUwEnd",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.3.19 Looping and lists\n",
    "\n",
    "\n",
    "- Computers are useful because they can repeat computation, accurately\n",
    "    and fast\n",
    "\n",
    "- So loops are going to be a central feature of almost all programs\n",
    "    you encounter\n",
    "\n",
    "Tip: Don't create unnecessary lists\n",
    "\n",
    "> Lists are useful if you need to keep data for later computation.\n",
    ">\n",
    "> But if you don't need lists, it is probably better not to generate them.\n",
    "\n",
    "Try the next in python3:\n",
    "\n",
    "$\\Rightarrow$\n",
    "<https://github.com/fpro-feup/public/tree/master/lectures/10/sums.py>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "dCTGYCorw5_5",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.3.20 Nested lists\n",
    "\n",
    "- A nested list is a list that appears as an element in another list\n",
    "\n",
    "```\n",
    "   >>> nested = [\"hello\", 2.0, 5, [10, 20]]\n",
    "   >>> print(nested[3])\n",
    "   [10, 20]\n",
    "\n",
    "   >>>  nested[3][1]\n",
    "   20\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "LzWbnqGTFJVX",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    " What is printed by the following statements?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "bZiBJmmiFGpA",
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "alist = [ [4, [True, False], 6, 8], [888, 999] ]\n",
    "if alist[0][1][0]:\n",
    "   print(alist[1][0])\n",
    "else:\n",
    "   print(alist[1][1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "FFafDUVWw--a",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## 5.3.21 Matrices\n",
    "\n",
    "- Nested lists are often used to represent matrices<sup>2</sup>\n",
    "\n",
    "- For example, the matrix:\n",
    "\n",
    "$$\\left[\n",
    "    \\begin{array}{ccc}\n",
    "    1  & 2  & 3 \\\\\n",
    "    4  & 5  & 6 \\\\\n",
    "    7  & 8  & 9\n",
    "    \\end{array}\n",
    "  \\right]$$\n",
    "\n",
    "```\n",
    "   >>> mx = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]\n",
    "\n",
    "   >>> mx[1]       # select a row\n",
    "   [4, 5, 6]\n",
    "\n",
    "   >>> mx[1][2]    # extract a single element\n",
    "   6\n",
    "```\n",
    "\n",
    "<sup>2</sup> Later we will see a more radical alternative using a dictionary."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Zz-UtV8ORH_t",
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Ticket to leave"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "C-hchAExRRVh",
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Moodle activity\n",
    "\n",
    "[LE10: Working with lists](https://moodle.up.pt/course/view.php?id=1738#section-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "uV1OP6ahRYne",
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "\n",
    "$\\Rightarrow$ \n",
    "[Go back to the Table of Contents](00-contents.ipynb)\n",
    "\n",
    "$\\Rightarrow$ \n",
    "[Read the Preface](00-preface.ipynb)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "10-more-lists.ipynb",
   "private_outputs": true,
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  },
  "rise": {
   "enable_chalkboard": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}