functions_advanced.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0",
   "metadata": {},
   "source": [
    "# Functions (advanced)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1",
   "metadata": {},
   "source": [
    "# Table of Contents\n",
    "\n",
    "- [Recap](#Recap)\n",
    "  - [Functions are objects](#Functions-are-objects)\n",
    "  - [Scopes and namespaces](#Scopes-and-namespaces)\n",
    "- [Mutable objects as default values of function's parameters](#Mutable-objects-as-default-values-of-function's-parameters)\n",
    "- [Lambdas](#Lambdas)\n",
    "  - [Lambdas and sorting](#Lambdas-and-sorting)\n",
    "- [Closures](#Closures)\n",
    "  - [Modifying the free variable](#Modifying-the-free-variable)\n",
    "  - [Multiple instances of closures](#Multiple-instances-of-closures)\n",
    "  - [Closures can be tricky](#Closures-can-be-tricky)\n",
    "  - [Nested closures](#Nested-closures)\n",
    "  - [Closures: examples](#Closures:-examples)\n",
    "    - [Example 1](#Example-1)\n",
    "    - [Example 2](#Example-2)\n",
    "- [Decorators](#Decorators)\n",
    "  - [Decorators: examples](#Decorators:-examples)\n",
    "    - [Example 1: timer](#Example-1:-timer)\n",
    "      - [Fibonacci with recursion](#Fibonacci-with-recursion)\n",
    "      - [Fibonacci with a simple loop](#Fibonacci-with-a-simple-loop)\n",
    "      - [Fibonacci using `reduce`](#Fibonacci-using-reduce)\n",
    "    - [Example 2: memoization](#Example-2:-memoization)\n",
    "  - [Parametrized decorators](#Parametrized-decorators)\n",
    "- [Generators](#Generators)\n",
    "  - [Create an interable from a generator](#Create-an-interable-from-a-generator)\n",
    "  - [Combining generators](#Combining-generators)\n",
    "- [Exercises](#Exercises)\n",
    "  - [Password checker factory](#Password-checker-factory)\n",
    "  - [String range](#String-range)\n",
    "  - [Read `n` lines](#Read-n-lines)\n",
    "  - [Only run once](#Only-run-once)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2",
   "metadata": {},
   "source": [
    "We are going to cover the following topics:\n",
    "\n",
    "- Decorators\n",
    "- Lambdas\n",
    "- Arguments and object's mutability\n",
    "- Generators"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3",
   "metadata": {},
   "source": [
    "## Recap"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4",
   "metadata": {},
   "source": [
    "Before starting our deep dive on functions, we must revise quickly two important concepts. Have a look at the [Functions](./functions.ipynb#The-scope-of-a-function) notebook for more detail.\n",
    "\n",
    "1. Scopes and namespaces\n",
    "2. Functions are objects"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5",
   "metadata": {},
   "source": [
    "### Functions are objects"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6",
   "metadata": {},
   "source": [
    "As an example, suppose that we want to create a \"password checker\", that is, a function that can verify if an input password complies with some rules (e.g., minumum length, a given number of special characters). We could create a function with the following signature:\n",
    "\n",
    "```python\n",
    "def check_password(\n",
    "    password: str,\n",
    "    min_length: int,\n",
    "    min_uppercase: int,\n",
    "    min_punctuation:\n",
    "    int, min_digits: int\n",
    "    ) -> bool:\n",
    "    \"\"\"Check if a given password complies with pre-defined rules.\"\"\"\n",
    "```\n",
    "\n",
    "In various situations, passwords are subject to distinct rules. Once these rules are defined, our goal is to streamline the process of handling them. We aim to avoid repeatedly inputting them for every password to check, as this can become tedious."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7",
   "metadata": {},
   "source": [
    "We can instead define a so-called **higher-order function** (see [Functional programming](./functional_programming.ipynb#Higher-Order-Functions-/-Functions-as-Values)): a function that returns another function.\n",
    "It does **not** call that function, just returns it."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8",
   "metadata": {},
   "source": [
    "```python\n",
    "\n",
    "def check_password_factory(\n",
    "    min_length: int,\n",
    "    min_uppercase: int,\n",
    "    min_punctuation: int,\n",
    "    min_digits: int\n",
    "    ):\n",
    "    \"\"\"Our password checker factory\"\"\"\n",
    "\n",
    "    def check_password(password: str) -> bool:\n",
    "        \"\"\"Password checker function\"\"\"\n",
    "        # our password checking logic\n",
    "        # ...\n",
    "        return # True or False\n",
    "\n",
    "    return check_password\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9",
   "metadata": {},
   "source": [
    "You would first call your factory function with some password requirements:\n",
    "\n",
    "```python\n",
    "password_checker = check_password_factory(min_length=10, min_uppercase=4, min_punctuation=3, min_digits=1)\n",
    "```\n",
    "\n",
    "And then you could verify that an input password adheres to the constraints:\n",
    "\n",
    "```python\n",
    "password_checker(\"MyveryComplexPWD123\")\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10",
   "metadata": {},
   "source": [
    "### Scopes and namespaces"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11",
   "metadata": {},
   "source": [
    "Python's variables are just names (i.e., labels) that we can **bind** to objects. Each variable is simply telling Python where to look in our computer's memory to retrieve some data. These bindings are **not global**: some of them exist only in specific parts of our code.\n",
    "\n",
    "> The portion of code where a name binding is defined is called **lexical scope** (or just \"scope\"). The bindings are stored in a scope's **namespace**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12",
   "metadata": {},
   "source": [
    "We always have the following scopes:\n",
    "\n",
    "1. `built-in` scope\n",
    "2. `global` (or module) scope\n",
    "\n",
    "We also have the `local` scope that's created when we are **calling** a function.\n",
    "The local scope associated to any called function is **destroyed** after the function has done its job. Also the namespace associated with it will be gone."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13",
   "metadata": {},
   "source": [
    "When Python needs to retrieve which object is referenced by a given name, it always starts from the current scope (the `local` one if we are inside a function's body). If a name binding is not found there, it searches in the scope immediately up in the hierarchy.\n",
    "\n",
    "> **LEGB rule**: **L**ocal → **E**nclosing → **G**lobal → **B**uilt-in"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "14",
   "metadata": {},
   "source": [
    "When Python encounters a function **definition** (i.e., at compile-time), it does two things:\n",
    "\n",
    "1. Scans for any variables that have values **assigned** anywhere in the function. By default, names that are assigned are **local** unless we are explicitly saying that they should not with the `global` keyword.\n",
    "2. Variables that are **referenced** but **not assigned** a value anywhere in the function will **not be local**. When we are calling the function (i.e., run-time), Python will look for them in the **enclosing scope**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15",
   "metadata": {},
   "source": [
    "Examples:\n",
    "\n",
    "```python\n",
    "var = 10   # global (or module) scope\n",
    "\n",
    "def func_1():\n",
    "    print(var)   # var is referenced but not assigned. At compile-time is \"non-local\"\n",
    "\n",
    "def func_2()\n",
    "    var = 100    # var is assigned. At compile-time will be placed in the \"local\" scope\n",
    "\n",
    "def func_3():\n",
    "    global var\n",
    "    var = 1000   # var is assigned, so it should be local. But it's also declared to be \"global\" with the keyword above\n",
    "\n",
    "def func_4():\n",
    "    print(var)\n",
    "    var = 100    # what happens here?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16",
   "metadata": {},
   "source": [
    "A function gets its local scope upon calling. Since we can have function definitions inside of other functions, there can be **nested scopes**. This is where the `nonlocal` keyword becomes useful or even needed.\n",
    "\n",
    "> The `nonlocal` keyword is used to declare that a variable is not local to the current function but is defined in the **nearest enclosing scope** that is **not global**. It allows you to access and modify variables in the outer (non-global) scope from within an inner function.\n",
    "\n",
    "An example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "17",
   "metadata": {},
   "outputs": [],
   "source": [
    "def outer_function():\n",
    "    x = \"global\"\n",
    "\n",
    "    # prints \"outer\"\n",
    "    print(\"Inside outer_function:\", x)\n",
    "\n",
    "    def inner_function():\n",
    "        nonlocal x\n",
    "        x = \"inner\"\n",
    "        # prints \"inner\"\n",
    "        print(\"Inside inner_function:\", x)\n",
    "\n",
    "    inner_function()\n",
    "    # prints \"inner\" again, because we modified `x` from a nested scope\n",
    "    print(\"Inside outer_function:\", x)\n",
    "\n",
    "outer_function()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18",
   "metadata": {},
   "source": [
    "Two important notes about the `nonlocal` keyword:\n",
    "\n",
    "1. Python will search for a `nonlocal` name in the **enclosing local scopes** until it first encounters the specified variable.\n",
    "2. **Only** local scopes are searched, never the global one."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "    <h4><b>Hint</b></h4> <strong>Experiment</strong> a bit with the code above. If you didn't fully understand what <code>global</code> and <code>nonlocal</code> do, try changing the scope of <code>x</code> with the different keywords and see whether you obtain what you expect.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20",
   "metadata": {},
   "source": [
    "## Mutable objects as default values of function's parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21",
   "metadata": {},
   "source": [
    "Using mutable objects like lists or dictionaries as a function's parameters default values requires extra care, as it can lead to some unexpected or unwanted behaviors.\n",
    "They could even produce mistakes that are difficult to debug."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22",
   "metadata": {},
   "source": [
    "Consider what happens when Python evaluates the following code:\n",
    "\n",
    "```python\n",
    "def func(a=10):\n",
    "    return a ** 2\n",
    "```\n",
    "\n",
    "A new function is **created**, but it's body is run only when **executed**.\n",
    "Also, a local scope for this function is only created upon its execution.\n",
    "\n",
    "What happens at \"compile-time\" is setting the default value of the parameter `a`.\n",
    "Where's the problem, you might say? Look at this example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23",
   "metadata": {},
   "outputs": [],
   "source": [
    "from datetime import datetime\n",
    "\n",
    "def log(msg, *, dt=datetime.utcnow()):\n",
    "    print(f'{dt}: {msg}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24",
   "metadata": {},
   "source": [
    "A simple logging function.\n",
    "Let's run it a few times, waiting a bunch of seconds in between:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "25",
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import sleep\n",
    "\n",
    "log(\"my first message\")\n",
    "sleep(5)\n",
    "log(\"my first message\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26",
   "metadata": {},
   "source": [
    "Something is wrong here: we waited 5 seconds, but the timestamp of our log message **did not change**.\n",
    "Why? Because `dt` default value is set **when the function is defined**, and it's never changed afterwards – unless we pass it by ourselves."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27",
   "metadata": {},
   "source": [
    "The correct pattern to avoid this unwanted behavior is setting a default value of `None`, so that the argument remains optional.\n",
    "Then, inside the function's body, we can assign the correct or updated value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28",
   "metadata": {},
   "outputs": [],
   "source": [
    "def log(msg, *, dt=None):\n",
    "    dt = dt or datetime.utcnow()\n",
    "    print(f'{dt}: {msg}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "29",
   "metadata": {},
   "outputs": [],
   "source": [
    "log(\"my first message\")\n",
    "sleep(5)\n",
    "log(\"my first message\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30",
   "metadata": {},
   "source": [
    "Now the output is what we expected."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31",
   "metadata": {},
   "source": [
    "Another problematic context is when we're dealing with **mutable objects** (e.g., lists, sets, dictionaries).\n",
    "This definition includes custom classes, if we are not careful.\n",
    "\n",
    "Let's consider this example: we want to keep track of our groceries in different stores.\n",
    "We might create a function that adds an item to a grocery list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "32",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_item(name, quantity, unit, grocery_list):\n",
    "    grocery_list.append(f\"{name} ({quantity} {unit})\")\n",
    "    return grocery_list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33",
   "metadata": {},
   "source": [
    "We now have two stores and want to add some items to them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "34",
   "metadata": {},
   "outputs": [],
   "source": [
    "store_1 = []\n",
    "store_2 = []\n",
    "\n",
    "add_item('bananas', 2, 'units', store_1)\n",
    "add_item('grapes', 1, 'bunch', store_1)\n",
    "add_item('python', 1, 'medium-rare', store_2)\n",
    "\n",
    "print(store_1, store_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35",
   "metadata": {},
   "source": [
    "All good.\n",
    "What if we don't supply the store list where we want to add the new item?\n",
    "We could have our function create a new, empty store list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "36",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_item(name, quantity, unit, grocery_list=[]):\n",
    "    grocery_list.append(f\"{name} ({quantity} {unit})\")\n",
    "    return grocery_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "37",
   "metadata": {},
   "outputs": [],
   "source": [
    "store_1 = add_item('bananas', 2, 'units')\n",
    "add_item('grapes', 1, 'bunch', store_1)\n",
    "\n",
    "print(store_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38",
   "metadata": {},
   "source": [
    "Okay, all good.\n",
    "Let's create our second list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "39",
   "metadata": {},
   "outputs": [],
   "source": [
    "store_2 = add_item('milk', 1, 'gallon')\n",
    "\n",
    "print(store_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "40",
   "metadata": {},
   "source": [
    "Again, not what we expected, right?\n",
    "`store_2` should be a completeley new list, while Python is still adding to the empty list used to initialize the default value of the `grocery_list` parameter.\n",
    "\n",
    "The solution pattern is similar to the logging function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "41",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_item(name, quantity, unit, grocery_list=None):\n",
    "    if not grocery_list:\n",
    "        grocery_list = []\n",
    "    grocery_list.append(f\"{name} ({quantity} {unit})\")\n",
    "    return grocery_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "42",
   "metadata": {},
   "outputs": [],
   "source": [
    "store_1 = add_item('bananas', 2, 'units')\n",
    "add_item('grapes', 1, 'bunch', store_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "43",
   "metadata": {},
   "outputs": [],
   "source": [
    "store_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44",
   "metadata": {},
   "outputs": [],
   "source": [
    "store_2 = add_item('milk', 1, 'gallon')\n",
    "store_2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45",
   "metadata": {},
   "source": [
    "And now everything works as we expected."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46",
   "metadata": {},
   "source": [
    "Using mutable objects as default values usually lead to unwanted results.\n",
    "But there are some cases when this is precisely what we want.\n",
    "\n",
    "As an example where this might be useful, consider a function to calculate the factorial:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "47",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    if n < 1:\n",
    "        return 1\n",
    "    else:\n",
    "        print(f'Calculating {n}!')\n",
    "        return n * factorial(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "48",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "49",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50",
   "metadata": {},
   "source": [
    "We had to recalculate some values the second time, values that we could have saved for any subsequent call.\n",
    "We will see a much better approach later on, but now consider the following `factorial` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n, cache={}):\n",
    "    if n < 1:\n",
    "        return 1\n",
    "    elif n in cache:\n",
    "        return cache[n]\n",
    "    else:\n",
    "        print(f'Calculating {n}!')\n",
    "        result = n * factorial(n-1)\n",
    "        cache[n] = result\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "54",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55",
   "metadata": {},
   "source": [
    "Since the dictionary `cache` is initialized as an empty `dict()` **at compile-time** (when we define the function), we can update its content in any subsequent call to `factorial`.\n",
    "This is an efficient way of reducing the run-time of a computation when we know we can store previously computed results."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56",
   "metadata": {},
   "source": [
    "## Lambdas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57",
   "metadata": {},
   "source": [
    "We already now how to create a function: we use the `def` keyword:\n",
    "\n",
    "```python\n",
    "def mult(a, b):\n",
    "    return a * b\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58",
   "metadata": {},
   "source": [
    "A function can have **parameters** and a `return` statement.\n",
    "If we don't write a `return` statement, Python adds one for us and returns the `None` object."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59",
   "metadata": {},
   "source": [
    "There's another way to define a function object: with **lambda expressions** (or lambdas).\n",
    "The syntax is similar with a few differences:\n",
    "\n",
    "```python\n",
    "lambda x: x ** 2\n",
    "```\n",
    "\n",
    "- We don't have `def`\n",
    "- The function has **no name**\n",
    "- There is **no `return` statement**\n",
    "\n",
    "The \"body\" of a lambda expression follows the `:` mark.\n",
    "If the expression evaluates to something, the lambda implicitly returns that value."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60",
   "metadata": {},
   "source": [
    "Lambdas are objects, as much as functions are, so we can define a lambda and assign it to a name:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61",
   "metadata": {},
   "outputs": [],
   "source": [
    "f = lambda x: x ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62",
   "metadata": {},
   "outputs": [],
   "source": [
    "f"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63",
   "metadata": {},
   "source": [
    "We can also define lambdas with parameters **with a default value**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = lambda x, y=10: (x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "65",
   "metadata": {},
   "outputs": [],
   "source": [
    "g(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "66",
   "metadata": {},
   "outputs": [],
   "source": [
    "g(10, -10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67",
   "metadata": {},
   "source": [
    "Lambdas are very handy when we need something that behaves like a function, but we don't plan to use it many times. Examples:\n",
    "\n",
    "```python\n",
    "\n",
    "lambda x: x ** 2\n",
    "lambda x, y: x + y\n",
    "lambda: 'hello!'          # no params\n",
    "lambda s: s[::-1].upper() # what does it do?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68",
   "metadata": {},
   "source": [
    "Lambdas are **anonymous function objects**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "69",
   "metadata": {},
   "outputs": [],
   "source": [
    "type(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70",
   "metadata": {},
   "source": [
    "Since are objects, they can be passed to (or returned from) other functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "71",
   "metadata": {},
   "outputs": [],
   "source": [
    "def apply_func(fn, *args, **kwargs):\n",
    "    return fn(*args, **kwargs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72",
   "metadata": {},
   "outputs": [],
   "source": [
    "apply_func(lambda x, y: x+y, 1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "73",
   "metadata": {},
   "outputs": [],
   "source": [
    "apply_func(lambda *args: sum(args), 1, 2, 3, 4, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74",
   "metadata": {},
   "source": [
    "The previous example is **not** the suggested way to sum values of an iterable: we should use the built-in `sum()` when appropriate:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75",
   "metadata": {},
   "outputs": [],
   "source": [
    "apply_func(sum, (1, 2, 3, 4, 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "76",
   "metadata": {},
   "outputs": [],
   "source": [
    "sum((1, 2, 3, 4, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77",
   "metadata": {},
   "source": [
    "### Lambdas and sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78",
   "metadata": {},
   "source": [
    "Python has a built-in `sorted` method returns any iterable sorted according to a default ordering.\n",
    "Sometimes you may want to (or need to) specify a different criteria for sorting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79",
   "metadata": {},
   "outputs": [],
   "source": [
    "letters = list(\"ABCDzywab\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "80",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(letters)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81",
   "metadata": {},
   "source": [
    "Python's `sorted` has a keyword-only argument named `key=` that takes a function used to return the key – that is, the ordinal criteria according to which we want to sort the iterable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "82",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(letters, key=str.upper)  # sort as if all letters are CAPITALIZED"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83",
   "metadata": {},
   "source": [
    "Let's see how we can created a \"sorted dictionary\".\n",
    "Recall that a dictionary is an **unordered collection**, so it doesn't have a built-in order.\n",
    "\n",
    "_(Well, that's not completely true. The most recent versions of Python store the key-value pairs in the order they are entered or supplied.\n",
    "The thing is: accessing a dictionary **by index** doesn't make sense.)_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "84",
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {'def': 300, 'abc': 200, 'ghi': 100}\n",
    "sorted(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85",
   "metadata": {},
   "source": [
    "Iterating over a dictionary is equivalent to iterate **over keys**.\n",
    "If we wanted to sort our dictionary by its values, we need to use a lambda:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "86",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(d, key=lambda k: d[k])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87",
   "metadata": {},
   "source": [
    "But wait: now we lost our values!\n",
    "We need to do something more elaborate if we want to have a dictionary back:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "88",
   "metadata": {},
   "outputs": [],
   "source": [
    "dict(sorted(d.items(), key=lambda x: x[1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "89",
   "metadata": {},
   "source": [
    "Another useful application of lambdas is when Python doesn't know how to apply an ordering to some kind of data.\n",
    "For example, with complex numbers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90",
   "metadata": {},
   "outputs": [],
   "source": [
    "complex = [3+3j, 1+1j, 0, 4-2j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(complex)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92",
   "metadata": {},
   "source": [
    "We can sort complex numbers based on their modulus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "93",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(complex, key=lambda z: (z.real)**2 + (z.imag)**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "    <h4><b>Question</b></h4> Can you find a way to <strong>randomize</strong> a list using <code>sorted</code> and lambdas?\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "    <h4><b>Hint</b></h4> Have a look at the <a href=\"https://docs.python.org/3/library/random.html\"><code>random</code> module</a> of Python's standard library.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96",
   "metadata": {},
   "source": [
    "## Closures"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97",
   "metadata": {},
   "source": [
    "Let's consider the following code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "98",
   "metadata": {},
   "outputs": [],
   "source": [
    "def outer():\n",
    "    lang = \"Python\"\n",
    "\n",
    "    def inner():\n",
    "        print(f\"{lang} rocks!\")\n",
    "\n",
    "    inner()\n",
    "\n",
    "outer()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99",
   "metadata": {},
   "source": [
    "Here the `lang` variable is **non-local** to `inner()` because it's only referenced. `lang` is also called **free variable**.\n",
    "\n",
    "> A **free variable** is a variable referenced locally but defined in the enclosing scope.\n",
    "\n",
    "Also, `lang` and `inner()` both belongs to the local scope of `outer()`. Since this bound is particularly special, it has a special name: it's called a **closure**.\n",
    "The name \"closure\" come from the function `inner()` _enclosing_ its free variable `lang`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "100",
   "metadata": {},
   "source": [
    "Let's make a small adjustment that will change a lot of things:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "101",
   "metadata": {},
   "outputs": [],
   "source": [
    "def outer():\n",
    "    lang = \"Python\"\n",
    "\n",
    "    def inner():\n",
    "        print(f\"{lang} rocks!\")\n",
    "\n",
    "    return inner\n",
    "\n",
    "outer()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "102",
   "metadata": {},
   "source": [
    "We turned `outer()` into an higher-order function that does not return a simple function, but a closure (`inner()` + the free variable).\n",
    "\n",
    "Since functions are objects, we can assign that to a name:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "103",
   "metadata": {},
   "outputs": [],
   "source": [
    "fn = outer()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "104",
   "metadata": {},
   "source": [
    "And then call that function as any other function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "105",
   "metadata": {},
   "outputs": [],
   "source": [
    "fn()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "106",
   "metadata": {},
   "source": [
    "But wait a second! How's that possible? 🤔\n",
    "\n",
    "`fn()` is called **after** `outer()` has run: it runs when we are assigning the name `fn` to the result of calling `outer()`.\n",
    "If the local scope of a function is destroyed after the function has run, how can `fn` know that `lang = \"Python\"`?\n",
    "\n",
    "That's because Pyhon realized that we created a closure, and it's doing something unusual."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "107",
   "metadata": {},
   "source": [
    "If we look once again to the example above, we see that the name `lang` is **shared** between the local scope of `outer()` and the `print` statement inside `inner()`.\n",
    "When Python sees this, it does something different: it creates an **intermediary** object – called a _cell object_ – that only contains a memory address.\n",
    "A memory address of what? Of whatever object (i.e. data) is assigned to `lang`, the free variable."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "108",
   "metadata": {},
   "source": [
    "![](./images/cell_object.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "109",
   "metadata": {},
   "source": [
    "We can see all that by inspecting some _hidden_ attributes of `fn`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "110",
   "metadata": {},
   "outputs": [],
   "source": [
    "fn.__code__.co_freevars"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "111",
   "metadata": {},
   "outputs": [],
   "source": [
    "fn.__closure__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "112",
   "metadata": {},
   "source": [
    "We can see now the reason why we can call `fn()` and see the string \"Python rocks!\" printed although the variable `lang` is now out of scope (it's been destroyed).\n",
    "There is another reference to the cell object, that from the closure created by `inner()` plus the free variable.\n",
    "When running `outer()`, `inner()` is **not called**, and Python still knows how to retrieve the value of the string object."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "113",
   "metadata": {},
   "source": [
    "### Modifying the free variable"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "114",
   "metadata": {},
   "source": [
    "We know that the `nonlocal` keyword allows us to modify variables from the **enclosing scope**. Therefore, the following closure will work as expected:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "115",
   "metadata": {},
   "outputs": [],
   "source": [
    "def counter():\n",
    "    count = 0 # local variable\n",
    "\n",
    "    def inc():\n",
    "        nonlocal count\n",
    "        count += 1\n",
    "        return count\n",
    "    return inc\n",
    "\n",
    "c = counter()\n",
    "\n",
    "c()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "116",
   "metadata": {},
   "source": [
    "The `inc()` function and the `count` variable are the closure, but the `count` variable is not only accessed, but also modified."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "117",
   "metadata": {},
   "source": [
    "We can also have multiple closures that reference (and modify) the same free variable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "118",
   "metadata": {},
   "outputs": [],
   "source": [
    "def adders():\n",
    "    count = 0\n",
    "\n",
    "    def add_1():\n",
    "        nonlocal count\n",
    "        count += 1\n",
    "        return count\n",
    "\n",
    "    def add_2():\n",
    "        nonlocal count\n",
    "        count += 2\n",
    "        return count\n",
    "\n",
    "    return add_1, add_2\n",
    "\n",
    "fn1, fn2 = adders()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "119",
   "metadata": {},
   "outputs": [],
   "source": [
    "fn1()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "120",
   "metadata": {},
   "outputs": [],
   "source": [
    "fn2()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "121",
   "metadata": {},
   "source": [
    "### Multiple instances of closures"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "122",
   "metadata": {},
   "source": [
    "As we saw before when talking about scopes, every time a function is **called** a new **local scope** is created.\n",
    "A closure can then be created multiple times, and each time we are calling it a new **extended scope** is created.\n",
    "\n",
    "Consider the following example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "123",
   "metadata": {},
   "outputs": [],
   "source": [
    "def power(n):\n",
    "    # `n` is a local variable\n",
    "    def op(x):\n",
    "        return x ** n\n",
    "    return op"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "124",
   "metadata": {},
   "source": [
    "`n` is our free variable, and we have a closure that contains the function `op()` and the free variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "125",
   "metadata": {},
   "outputs": [],
   "source": [
    "square = power(2)\n",
    "cube = power(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "126",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(square(10))\n",
    "print(cube(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "127",
   "metadata": {},
   "source": [
    "We can verify that the two closures are completely different even though they were created from the same `power()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "128",
   "metadata": {},
   "outputs": [],
   "source": [
    "square.__closure__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "129",
   "metadata": {},
   "outputs": [],
   "source": [
    "cube.__closure__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "130",
   "metadata": {},
   "source": [
    "As we expected, the free variable `n` (of type `int`) is referenced by the cell objects of both closures.\n",
    "And since a new value for `n` is created in the local namespace of `power()` every time it's called, we obtained two **different** `int` objects."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "131",
   "metadata": {},
   "source": [
    "### Closures can be tricky"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "132",
   "metadata": {},
   "source": [
    "One important aspect of closures can be the source of nasty bugs if we don't understand it well.\n",
    "\n",
    "> A free variable is **referenced** when the closure is created, but its value is **looked up** upon calling."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "133",
   "metadata": {},
   "source": [
    "Let's say we want to create a function to sum different factors to an arbitrary number.\n",
    "We could do:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "134",
   "metadata": {},
   "outputs": [],
   "source": [
    "def adder(n):\n",
    "    def op(x):\n",
    "        return n + x\n",
    "    return op"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "135",
   "metadata": {},
   "outputs": [],
   "source": [
    "add_1 = adder(1)\n",
    "add_2 = adder(2)\n",
    "add_3 = adder(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "136",
   "metadata": {},
   "source": [
    "This works as expected:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "137",
   "metadata": {},
   "outputs": [],
   "source": [
    "add_1(10), add_2(10), add_3(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "138",
   "metadata": {},
   "source": [
    "Now we have the following idea to improve our code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "139",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fancy_adders():\n",
    "    adders = []\n",
    "    for n in range(1, 5):\n",
    "        def op(x):\n",
    "            return x + n\n",
    "        adders.append(op)\n",
    "    return adders"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "140",
   "metadata": {},
   "outputs": [],
   "source": [
    "adders = fancy_adders()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "141",
   "metadata": {},
   "source": [
    "We have now 4 functions in the `adders` list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "142",
   "metadata": {},
   "outputs": [],
   "source": [
    "adders"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "143",
   "metadata": {},
   "source": [
    "Let's see what happens when we call them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "144",
   "metadata": {},
   "outputs": [],
   "source": [
    "adders[0](10), adders[1](10), adders[2](10), adders[3](10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "145",
   "metadata": {},
   "source": [
    "Wait, why?! It seems that we picked up the **same value** of the free variable.\n",
    "The free variable is always `n`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "146",
   "metadata": {},
   "outputs": [],
   "source": [
    "adders[0].__code__.co_freevars"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "147",
   "metadata": {},
   "source": [
    "And we can indeed verify that its value referenced by each closure is exactly the same:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "148",
   "metadata": {},
   "outputs": [],
   "source": [
    "[x.__closure__ for x in adders]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "149",
   "metadata": {},
   "source": [
    "Which value? The last iteration of our loop, `n=4`.\n",
    "In fact:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "150",
   "metadata": {},
   "outputs": [],
   "source": [
    "hex(id(4))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "151",
   "metadata": {},
   "source": [
    "The key to understand this behavior is remembering that **closures captures _variables_ and not _values_**.\n",
    "This means that every `op()` function created in the loop is closing over the same variable `n`.\n",
    "\n",
    "By the time the call to `fancy_adders()` is over, the value of `n` is incremented to its final value, that is, 4.\n",
    "This is the value that will be looked up when calling our closures! And this is why we can see that `hex(id(4))` – the memory address of the integer `4` – is indeed the same for all closures."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "152",
   "metadata": {},
   "source": [
    "If we wanted to fix the example as we intended, we need to capture the **current** value of `n` when defining the closure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "153",
   "metadata": {},
   "outputs": [],
   "source": [
    "def truly_fancy_adders():\n",
    "    adders = []\n",
    "    for n in range(1, 5):\n",
    "        def op(x, n=n):  # Capture the current value of n as a default argument\n",
    "            return x + n\n",
    "        adders.append(op)\n",
    "    return adders"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "154",
   "metadata": {},
   "outputs": [],
   "source": [
    "correct_adders = truly_fancy_adders()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "155",
   "metadata": {},
   "outputs": [],
   "source": [
    "correct_adders[0](10), correct_adders[1](10), correct_adders[2](10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "156",
   "metadata": {},
   "source": [
    "Now, let's inspect our correct closures:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "157",
   "metadata": {},
   "outputs": [],
   "source": [
    "[x.__closure__ for x in correct_adders]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "158",
   "metadata": {},
   "source": [
    "Hey, why `None`? Let's check our free variable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "159",
   "metadata": {},
   "outputs": [],
   "source": [
    "correct_adders[0].__code__.co_freevars"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "160",
   "metadata": {},
   "source": [
    "Nothing yet?\n",
    "Can you think why you don't get any output?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "161",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "    <h4><b>Hint</b></h4> Think about <strong>your</strong> answer before evaluating the cell below.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "162",
   "metadata": {},
   "outputs": [],
   "source": [
    "from tutorial.quiz.functions_advanced import tricky_closures as answer\n",
    "answer"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "163",
   "metadata": {},
   "source": [
    "### Nested closures"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "164",
   "metadata": {},
   "source": [
    "We can also nest closures, as much as we can nest functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "165",
   "metadata": {},
   "outputs": [],
   "source": [
    "def incrementer(n):\n",
    "    def inner(start):\n",
    "        current = start\n",
    "        def inc():\n",
    "            a = 10  # local variable, NOT a free variable\n",
    "            nonlocal current\n",
    "            current += n\n",
    "            return current\n",
    "        return inc\n",
    "    return inner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "166",
   "metadata": {},
   "outputs": [],
   "source": [
    "f = incrementer(2)\n",
    "f.__code__.co_freevars"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "167",
   "metadata": {},
   "source": [
    "We create an incrementer function with the default increment, `n=2`, starting from `100`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "168",
   "metadata": {},
   "outputs": [],
   "source": [
    "inc_2 = f(100)\n",
    "inc_2()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "169",
   "metadata": {},
   "source": [
    "We can also create another _custom_ incrementer with a different increment value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "170",
   "metadata": {},
   "outputs": [],
   "source": [
    "inc_10 = incrementer(10)(100)\n",
    "inc_10()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "171",
   "metadata": {},
   "source": [
    "### Closures: examples"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "172",
   "metadata": {},
   "source": [
    "#### Example 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "173",
   "metadata": {},
   "source": [
    "Let's see a practical example of using closures.\n",
    "We're going to see how closures can replace classes and be more straightforward for simple tasks.\n",
    "\n",
    "Say that we want to calculate a running average of some numbers that we don't know in advance.\n",
    "We could create a class as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "174",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Averager:\n",
    "    def __init__(self):\n",
    "        self.numbers = []\n",
    "\n",
    "    def add(self, number):\n",
    "        self.numbers.append(number)\n",
    "        return sum(self.numbers) / len(self.numbers)\n",
    "\n",
    "a = Averager()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "175",
   "metadata": {},
   "outputs": [],
   "source": [
    "a.add(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "176",
   "metadata": {},
   "outputs": [],
   "source": [
    "a.add(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "177",
   "metadata": {},
   "outputs": [],
   "source": [
    "a.add(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "178",
   "metadata": {},
   "source": [
    "How can we rewrite the our class as a closure?\n",
    "The free variable will be the list `numbers`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "179",
   "metadata": {},
   "outputs": [],
   "source": [
    "def averager():\n",
    "    numbers = []\n",
    "    def add(number):\n",
    "        numbers.append(number)\n",
    "        return sum(numbers) / len(numbers)\n",
    "    return add\n",
    "\n",
    "a = averager()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "180",
   "metadata": {},
   "outputs": [],
   "source": [
    "a.__closure__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "181",
   "metadata": {},
   "outputs": [],
   "source": [
    "a.__code__.co_freevars"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "182",
   "metadata": {},
   "outputs": [],
   "source": [
    "a(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "183",
   "metadata": {},
   "outputs": [],
   "source": [
    "a(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "184",
   "metadata": {},
   "source": [
    "We can make it better: instead of accumulating all the numbers in a list, we only need to keep a running total and count."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "185",
   "metadata": {},
   "outputs": [],
   "source": [
    "def averager():\n",
    "    total = 0\n",
    "    count = 0\n",
    "    def add(number):\n",
    "        nonlocal total\n",
    "        nonlocal count\n",
    "        \n",
    "        total += number\n",
    "        count += 1\n",
    "        return total / count\n",
    "    return add\n",
    "\n",
    "a = averager()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "186",
   "metadata": {},
   "outputs": [],
   "source": [
    "a(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "187",
   "metadata": {},
   "outputs": [],
   "source": [
    "a(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "188",
   "metadata": {},
   "outputs": [],
   "source": [
    "a(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "189",
   "metadata": {},
   "source": [
    "#### Example 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "190",
   "metadata": {},
   "source": [
    "We want to create a counter function, that is, a function that increments a variable every time it's called:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "191",
   "metadata": {},
   "outputs": [],
   "source": [
    "def counter(initial_value):\n",
    "    def inc(increment=1):\n",
    "        nonlocal initial_value\n",
    "        initial_value += increment\n",
    "        return initial_value\n",
    "    return inc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "192",
   "metadata": {},
   "outputs": [],
   "source": [
    "c1 = counter(0)\n",
    "c100 = counter(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "193",
   "metadata": {},
   "outputs": [],
   "source": [
    "c1()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "194",
   "metadata": {},
   "outputs": [],
   "source": [
    "c100()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "195",
   "metadata": {},
   "outputs": [],
   "source": [
    "c1(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "196",
   "metadata": {},
   "outputs": [],
   "source": [
    "c100(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "197",
   "metadata": {},
   "source": [
    "As you can see, each closure maintains a reference to the `initial_value` variable that was created when the `counter()` function was **called**.\n",
    "\n",
    "Each time that function was called, a new local variable `initial_value` was created (with a value assigned from the argument), and it became a nonlocal (captured) variable in the inner scope."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "198",
   "metadata": {},
   "source": [
    "Let's extend this example to a **function counter**: a counter that keeps track how many times a function is run."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "199",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fcounter(function):\n",
    "    count = 0\n",
    "\n",
    "    def inner(*args, **kwargs):\n",
    "        nonlocal count\n",
    "        count += 1\n",
    "        print(f\"Function '{function.__name__}' has beel called {count} times.\")\n",
    "        return function(*args, **kwargs)\n",
    "\n",
    "    return inner"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "200",
   "metadata": {},
   "source": [
    "Let's define a function we want to keep track of:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "201",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add(a, b):\n",
    "    return a + b\n",
    "\n",
    "counter_add = fcounter(add)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "202",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter_add.__code__.co_freevars"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "203",
   "metadata": {},
   "source": [
    "We have **two** free variables, one of which is a function (remember: functions are objects)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "204",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter_add(1, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "205",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter_add(2, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "206",
   "metadata": {},
   "source": [
    "## Decorators"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "207",
   "metadata": {},
   "source": [
    "Now that we know what closures are and what we can do with them, understanding what is a decorator is a (small) step away.\n",
    "\n",
    "Consider again the last example in the previous section: a counter for functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "208",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fcounter(function):\n",
    "    count = 0\n",
    "\n",
    "    def inner(*args, **kwargs):\n",
    "        nonlocal count\n",
    "        count += 1\n",
    "        print(f\"Function '{function.__name__}' has beel called {count} times.\")\n",
    "        return function(*args, **kwargs)\n",
    "\n",
    "    return inner"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "209",
   "metadata": {},
   "source": [
    "And then create a function we want to keep track:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "210",
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    product = 1\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    for i in range(2, n+1):\n",
    "        product *= i\n",
    "    return product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "211",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter_fact = fcounter(factorial)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "212",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter_fact.__closure__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "213",
   "metadata": {},
   "outputs": [],
   "source": [
    "counter_fact(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "214",
   "metadata": {},
   "source": [
    "Of course, `counter_fact` is an arbitrary name.\n",
    "Nothing prevents us from calling it `factorial`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "215",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial = fcounter(factorial)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "216",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "217",
   "metadata": {},
   "source": [
    "This way of defining a function, creating a closure that \"wraps\" a function object, and then **renaming** the initial function is so common in Python that gained a special syntax:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "218",
   "metadata": {},
   "outputs": [],
   "source": [
    "@fcounter\n",
    "def mult(a: float, b: float) -> float:\n",
    "    \"\"\"Multiplies two floats\"\"\"\n",
    "    return a * b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "219",
   "metadata": {},
   "outputs": [],
   "source": [
    "mult(2.0, 4.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "220",
   "metadata": {},
   "source": [
    "The function `fcounter` is called a **decorator**, because it's placed **before** the function definition line with the special symbol `@`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "221",
   "metadata": {},
   "source": [
    "There's one problem, though.\n",
    "If we inspect our `mult` function, we could see that it has lost something:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "222",
   "metadata": {},
   "outputs": [],
   "source": [
    "mult.__name__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "223",
   "metadata": {},
   "outputs": [],
   "source": [
    "help(mult)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "224",
   "metadata": {},
   "source": [
    "As you can see, we've also lost our docstring and type hints!\n",
    "What's left is the docstring and the type annotations of the `inner` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "225",
   "metadata": {},
   "outputs": [],
   "source": [
    "import inspect\n",
    "\n",
    "print(inspect.getsource(mult))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "226",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(inspect.signature(mult))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "227",
   "metadata": {},
   "source": [
    "We _could_ put back that information, but it might not be straighforward:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "228",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fcounter(function):\n",
    "    count = 0\n",
    "\n",
    "    def inner(*args, **kwargs):\n",
    "        nonlocal count\n",
    "        count += 1\n",
    "        print(f\"Function '{function.__name__}' has beel called {count} times.\")\n",
    "        return function(*args, **kwargs)\n",
    "\n",
    "    inner.__name__ = function.__name__\n",
    "    inner.__doc__ = function.__doc__\n",
    "\n",
    "    return inner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "229",
   "metadata": {},
   "outputs": [],
   "source": [
    "@fcounter\n",
    "def add(a: int, b: int = 10) -> int:\n",
    "    \"\"\"Sum two integers\"\"\"\n",
    "    return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "230",
   "metadata": {},
   "outputs": [],
   "source": [
    "help(add)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "231",
   "metadata": {},
   "outputs": [],
   "source": [
    "add.__name__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "232",
   "metadata": {},
   "source": [
    "Okay, at least our docstring and function's name are back.\n",
    "What about the type annotations?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "233",
   "metadata": {},
   "outputs": [],
   "source": [
    "inspect.signature(add).parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "234",
   "metadata": {},
   "source": [
    "Unfortunately, they stil belong to the `inner` function.\n",
    "There's a way to bring them back, and we have to use a built-in function from the `functolls` module called `wraps`.\n",
    "\n",
    "Curiously, `functools.wraps` is **itself a decorator**!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "235",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import wraps\n",
    "\n",
    "def fcounter(function):\n",
    "    count = 0\n",
    "\n",
    "    @wraps(function)\n",
    "    def inner(*args, **kwargs):\n",
    "        nonlocal count\n",
    "        count += 1\n",
    "        print(f\"Function '{function.__name__}' has beel called {count} times.\")\n",
    "        return function(*args, **kwargs)\n",
    "\n",
    "    return inner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "236",
   "metadata": {},
   "outputs": [],
   "source": [
    "@fcounter\n",
    "def add(a: int, b: int = 10) -> int:\n",
    "    \"\"\"Sum two integers\"\"\"\n",
    "    return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "237",
   "metadata": {},
   "outputs": [],
   "source": [
    "help(add)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "238",
   "metadata": {},
   "outputs": [],
   "source": [
    "inspect.signature(add)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "239",
   "metadata": {},
   "outputs": [],
   "source": [
    "inspect.signature(add).parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "240",
   "metadata": {},
   "source": [
    "And now everything is back to normal."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "241",
   "metadata": {},
   "source": [
    "### Decorators: examples"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "242",
   "metadata": {},
   "source": [
    "#### Example 1: timer"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "243",
   "metadata": {},
   "source": [
    "This is classic example of using decorators: creating a timer for a generic function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "244",
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import perf_counter\n",
    "from functools import wraps\n",
    "\n",
    "def timed(function):\n",
    "\n",
    "    @wraps(function)\n",
    "    def inner(*args, **kwargs):\n",
    "        start = perf_counter()\n",
    "        \n",
    "        result = function(*args, **kwargs)\n",
    "        \n",
    "        end = perf_counter()\n",
    "        elapsed = end - start\n",
    "        \n",
    "        args_ = [str(a) for a in args]\n",
    "        kwargs_ = [f'{k}={v}' for (k, v) in kwargs.items()]\n",
    "        all_args = args_ + kwargs_\n",
    "        args_str = ','.join(all_args)\n",
    "        \n",
    "        print(f'{function.__name__}({args_str}) took {elapsed:.6f}s to run.')\n",
    "\n",
    "        return result\n",
    "    \n",
    "    return inner"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "245",
   "metadata": {},
   "source": [
    "Let's test it with a function to calculate the n-th Fibonacci number: `1, 1, 2, 3, 5, 8, 11, ...`\n",
    "\n",
    "We're going to write **three** Fibonacci implementations to compare their efficiency:\n",
    "\n",
    "1. With recursion\n",
    "2. With a simple loop\n",
    "3. A functional approach\n",
    "\n",
    "**NOTE**: while Python indexes start from 0, our Fibonacci sequence starts from 1 (by choice)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "246",
   "metadata": {},
   "source": [
    "##### Fibonacci with recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "247",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_fib_recursive(n):\n",
    "    if n <= 2:\n",
    "        return 1\n",
    "    return calc_fib_recursive(n - 1) + calc_fib_recursive(n - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "248",
   "metadata": {},
   "outputs": [],
   "source": [
    "calc_fib_recursive(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "249",
   "metadata": {},
   "outputs": [],
   "source": [
    "calc_fib_recursive(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "250",
   "metadata": {},
   "outputs": [],
   "source": [
    "@timed\n",
    "def fib_recursive(n):\n",
    "    return calc_fib_recursive(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "251",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib_recursive(33)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "252",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib_recursive(35)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "253",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib_recursive(40)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "254",
   "metadata": {},
   "source": [
    "Sounds a bit long, doesn't it?\n",
    "Well, it's: we are calculating the same numbers **every time**.\n",
    "When we're past the 30th number, we start seeing some considerable slow down."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "255",
   "metadata": {},
   "source": [
    "##### Fibonacci with a simple loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "256",
   "metadata": {},
   "outputs": [],
   "source": [
    "@timed\n",
    "def fib_loop(n):\n",
    "    fib_1 = 1\n",
    "    fib_2 = 1\n",
    "    \n",
    "    for i in range(3, n + 1):\n",
    "        fib_1, fib_2 = fib_2, fib_1 + fib_2\n",
    "    \n",
    "    return fib_2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "257",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in (3, 10, 30, 35, 40):\n",
    "    fib_loop(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "258",
   "metadata": {},
   "source": [
    "Incredibly more efficient!\n",
    "This is just getting rid of multiple (useless) calculations."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "259",
   "metadata": {},
   "source": [
    "##### Fibonacci using `reduce`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "260",
   "metadata": {},
   "source": [
    "First, a quick refresher:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "261",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "262",
   "metadata": {},
   "outputs": [],
   "source": [
    "reduce(lambda x, y: x + y, (1, 2, 3, 4, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "263",
   "metadata": {},
   "source": [
    "It's just the progressive sum of pairs of numbers.\n",
    "`reduce` applies an operation (1st argument) to pairs of element in an interable (2nd argument)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "264",
   "metadata": {},
   "source": [
    "To calculate the Fibonacci sequence with `reduce`:\n",
    "\n",
    "```\n",
    "n=1:\n",
    "(1, 0) --> (1, 1)\n",
    "\n",
    "n=2:\n",
    "(1, 0) --> (1, 1) --> (1 + 1, 1) = (2, 1)  : result = 2 \n",
    "\n",
    "n=3\n",
    "(1, 0) --> (1, 1) --> (2, 1) --> (2+1, 2) = (3, 2)  : result = 3\n",
    "\n",
    "n=4\n",
    "(1, 0) --> (1, 1) --> (2, 1) --> (3, 2) --> (5, 3)  : result = 5\n",
    "```\n",
    "\n",
    "In general each step in the reduction is as follows:\n",
    "\n",
    "```\n",
    "previous value = (a, b)\n",
    "new value = (a+b, a)\n",
    "```\n",
    "\n",
    "If we start our reduction with an initial value of `(1, 0)`, we need to run our \"loop\" `n` times.\n",
    "We therefore use a \"dummy\" sequence of length `n` to create `n` steps in our reduce."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "265",
   "metadata": {},
   "outputs": [],
   "source": [
    "@timed\n",
    "def fib_reduce(n):\n",
    "    initial = (1, 0)\n",
    "    fib_n = reduce(lambda prev, n: (prev[0] + prev[1], prev[0]), range(n), initial)\n",
    "    return fib_n[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "266",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in (3, 10, 30, 35, 40):\n",
    "    fib_reduce(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "267",
   "metadata": {},
   "source": [
    "If we compare the three methods:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "268",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib_recursive(35)\n",
    "fib_loop(35)\n",
    "fib_reduce(35)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "269",
   "metadata": {},
   "source": [
    "Although the recursive method is the __easiest__ to understand, it's also the slowest because it's written inefficiently.\n",
    "How can we improve it? Let's see a second example of using decorators."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "270",
   "metadata": {},
   "source": [
    "#### Example 2: memoization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "271",
   "metadata": {},
   "source": [
    "The previous example showed one task that a decorator can accomplish pretty well: adding some feature to a predefined function.\n",
    "But what about __changing__ the behavior of the function itself?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "272",
   "metadata": {},
   "source": [
    "Remember the Fibonacci sequence example.\n",
    "We discovered that the recursive approach is by far the most intuitive, yet it's tremendously inefficient because a number gets calculated multiple times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "273",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    print (f'Calculating fib({n})')\n",
    "    return 1 if n < 3 else fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "274",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "275",
   "metadata": {},
   "source": [
    "You can see that `fib(2)` is calculated **three times**.\n",
    "And the larger the number, the more often a number is recalculated.\n",
    "That's why with `fib(40)` the recursive approach is taking ages to finish."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "276",
   "metadata": {},
   "source": [
    "We'll see how we can improve this approach using a decorator and a caching mechanism for previously calculated numbers.\n",
    "This approach is well-known in computer science, and it's called **memoization**."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "277",
   "metadata": {},
   "source": [
    "For the sake of comparison, let's first approach this problem with a simple class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "278",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Fib:\n",
    "    def __init__(self):\n",
    "        self.cache = {1: 1, 2: 1} # initial values already known\n",
    "    \n",
    "    def fib(self, n):\n",
    "        if n not in self.cache:\n",
    "            print(f'Calculating fib({n})')\n",
    "            self.cache[n] = self.fib(n-1) + self.fib(n-2)\n",
    "        return self.cache[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "279",
   "metadata": {},
   "outputs": [],
   "source": [
    "f = Fib()\n",
    "f.fib(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "280",
   "metadata": {},
   "outputs": [],
   "source": [
    "f.fib(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "281",
   "metadata": {},
   "source": [
    "You can see that numbers $\\leq 10$ are **not** recalculated, but are fetched from the cache.\n",
    "\n",
    "Let's see how we can do this with a closure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "282",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib():\n",
    "    # `cache` is our free variable\n",
    "    cache = {1: 1, 2: 2}\n",
    "    \n",
    "    def calc_fib(n):\n",
    "        if n not in cache:\n",
    "            print(f'Calculating fib({n})')\n",
    "            cache[n] = calc_fib(n-1) + calc_fib(n-2)\n",
    "        return cache[n]\n",
    "    \n",
    "    return calc_fib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "283",
   "metadata": {},
   "outputs": [],
   "source": [
    "f = fib() # create our closure\n",
    "f(10)     # call it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "284",
   "metadata": {},
   "outputs": [],
   "source": [
    "f(15)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "285",
   "metadata": {},
   "source": [
    "Once again, cached valued are just returned and not recalculated."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "286",
   "metadata": {},
   "source": [
    "How can we implement this as a decorator?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "287",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import wraps\n",
    "\n",
    "def memoize_fib(fn):\n",
    "    cache = {}\n",
    "    \n",
    "    @wraps(fn)\n",
    "    def inner(n):\n",
    "        if n not in cache:\n",
    "            cache[n] = fn(n)\n",
    "        return cache[n]\n",
    "    \n",
    "    return inner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "288",
   "metadata": {},
   "outputs": [],
   "source": [
    "@memoize_fib\n",
    "def fib(n):\n",
    "    print (f'Calculating fib({n})')\n",
    "    return 1 if n < 3 else fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "289",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "290",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "291",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "292",
   "metadata": {},
   "source": [
    "`fib(6)` was literally instantaneous because we already had it in the cache."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "293",
   "metadata": {},
   "source": [
    "How to create a generic decorator that caches the return values of **any** function?\n",
    "We know how to do it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "294",
   "metadata": {},
   "outputs": [],
   "source": [
    "def memoize(fn):\n",
    "    cache = {}\n",
    "    \n",
    "    @wraps(fn)\n",
    "    def inner(*args):\n",
    "        if args not in cache:\n",
    "            cache[args] = fn(*args)\n",
    "        return cache[args]\n",
    "    \n",
    "    return inner"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "295",
   "metadata": {},
   "source": [
    "And we can now give any function a cache to store previously calculated results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "296",
   "metadata": {},
   "outputs": [],
   "source": [
    "@memoize\n",
    "def fact(n):\n",
    "    print(f'Calculating {n}!')\n",
    "    return 1 if n < 2 else n * fact(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "297",
   "metadata": {},
   "outputs": [],
   "source": [
    "fact(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "298",
   "metadata": {},
   "outputs": [],
   "source": [
    "fact(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "299",
   "metadata": {},
   "outputs": [],
   "source": [
    "fact(9)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "300",
   "metadata": {},
   "source": [
    "Caching and decorators play a crucial role in optimizing function performance.\n",
    "By caching previously calculated results in memory (or on disk), we can drastically reduce the time required for the calculation.\n",
    "\n",
    "However, our simple memoizer has a limitation: the cache size is **unbounded**, which may not be ideal.\n",
    "In practice, it's often desirable to restrict the cache to a specific number of entries.\n",
    "This helps strike a balance between computational efficiency and memory utilization."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "301",
   "metadata": {},
   "source": [
    "Additionally, our current implementation does not handle keyword arguments (`**kwargs`), which can be a significant limitation in more complex scenarios.\n",
    "\n",
    "Fortunately, Python provides a built-in solution for memoization in the `functools` module, known as `lru_cache`.\n",
    "This decorator is designed to address the drawbacks of our basic memoization example.\n",
    "`lru_cache` stands for **Least Recently Used** caching, meaning that when the cache reaches its limit, the least recently used entries are automatically removed to make room for new ones.\n",
    "This feature ensures efficient memory management while improving performance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "302",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "303",
   "metadata": {},
   "outputs": [],
   "source": [
    "@lru_cache()\n",
    "def fact(n):\n",
    "    print(f\"Calculating fact({n})\")\n",
    "    return 1 if n < 2 else n * fact(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "304",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in (2, 5, 6, 10, 15, 8):\n",
    "    print(fact(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "305",
   "metadata": {},
   "source": [
    "Once again, the last value `fact(8)` was simply fetched from the cache."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "306",
   "metadata": {},
   "source": [
    "Now let's see if we have improved on our recursive approach of calculating Fibonacci numbers.\n",
    "Recall the naive implementation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "307",
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import perf_counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "308",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib_no_memo(n):\n",
    "    return 1 if n < 3 else fib_no_memo(n-1) + fib_no_memo(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "309",
   "metadata": {},
   "outputs": [],
   "source": [
    "start = perf_counter()\n",
    "result = fib_no_memo(35)\n",
    "done = perf_counter() - start\n",
    "\n",
    "print(f\"result={result}, elapsed: {done}s\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "310",
   "metadata": {},
   "outputs": [],
   "source": [
    "@lru_cache()\n",
    "def fib_memo(n):\n",
    "    return 1 if n < 3 else fib_memo(n-1) + fib_memo(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "311",
   "metadata": {},
   "outputs": [],
   "source": [
    "start = perf_counter()\n",
    "result = fib_memo(35)\n",
    "done = perf_counter() - start\n",
    "\n",
    "print(f\"result={result}, elapsed: {done}s\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "312",
   "metadata": {},
   "source": [
    "It's about **4 orders of magnitude** faster than the naive approach! 🔥\n",
    "Let's time it again to see what happens:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "313",
   "metadata": {},
   "outputs": [],
   "source": [
    "start = perf_counter()\n",
    "result = fib_memo(35)\n",
    "done = perf_counter() - start\n",
    "\n",
    "print(f\"result={result}, elapsed: {done}s\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "314",
   "metadata": {},
   "outputs": [],
   "source": [
    "start = perf_counter()\n",
    "result = fib_memo(35)\n",
    "done = perf_counter() - start\n",
    "\n",
    "print(f\"result={result}, elapsed: {done}s\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "315",
   "metadata": {},
   "source": [
    "Not the same time, but about the same order of magnitude.\n",
    "It means that no extra calculation was needed."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "316",
   "metadata": {},
   "source": [
    "You may have noticed that `lru_cache` was called an **empty list of arguments**, but it supports some.\n",
    "One of them is the **cache size**: by default, it can hold up to **128 items**.\n",
    "The best is to use powers of 2 for performance reasons, but you can change it to anything you want, including `None` for an **unbounded** cache (not recommended)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "317",
   "metadata": {},
   "outputs": [],
   "source": [
    "@lru_cache(maxsize=8)\n",
    "def fib(n):\n",
    "    print(f\"Calculating fib({n})\")\n",
    "    return 1 if n < 3 else fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "318",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "319",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "320",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "321",
   "metadata": {},
   "source": [
    "We had to recalculate `fib(1)` because when we called `fib(9)` the least recent item in the cache (the result of `fib(1)`) was evicted from the cache."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "322",
   "metadata": {},
   "source": [
    "### Parametrized decorators"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "323",
   "metadata": {},
   "source": [
    "Here comes a natural question: what if I need to pass some argument to my decorator?\n",
    "Think again of the `functools.lru_cache`: it takes one parameters, the cache size called `maxsize`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "324",
   "metadata": {},
   "source": [
    "Let's bring back our `timed` decorator and make a small change.\n",
    "Instead of calculating the time of a **single run**, we want to calculate an **average** of, say, `10` runs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "325",
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import perf_counter\n",
    "\n",
    "def timed(fn):\n",
    "    def inner(*args, **kwargs):\n",
    "        total_elapsed = 0\n",
    "        \n",
    "        for i in range(10):\n",
    "            start = perf_counter()\n",
    "            result = fn(*args, **kwargs)\n",
    "            end = perf_counter()\n",
    "            total_elapsed += (perf_counter() - start)\n",
    "        \n",
    "        avg_elapsed = total_elapsed / 10\n",
    "        \n",
    "        print(f'Avg runtime: {avg_elapsed:.6f}s')\n",
    "        \n",
    "        return result\n",
    "    \n",
    "    return inner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "326",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_fib_recurse(n):\n",
    "    return 1 if n < 3 else calc_fib_recurse(n-1) + calc_fib_recurse(n-2)\n",
    "\n",
    "@timed\n",
    "def fib(n):\n",
    "    return calc_fib_recurse(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "327",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "328",
   "metadata": {},
   "source": [
    "But what if I wanted to time this function **100 times**?\n",
    "Or say that I have different functions that should be timed with a different number of repetitions?\n",
    "It's not the best to have the value `10` hard-coded, right?\n",
    "\n",
    "Let's change this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "329",
   "metadata": {},
   "outputs": [],
   "source": [
    "def timed(fn, num_reps):  \n",
    "    def inner(*args, **kwargs):\n",
    "        total_elapsed = 0\n",
    "        \n",
    "        for i in range(num_reps):\n",
    "            start = perf_counter()\n",
    "            result = fn(*args, **kwargs)\n",
    "            end = perf_counter()\n",
    "            total_elapsed += (perf_counter() - start)\n",
    "        \n",
    "        avg_elapsed = total_elapsed / num_reps\n",
    "        \n",
    "        print(f'Avg runtime: {avg_elapsed:.6f}s ({num_reps} reps)')\n",
    "        return result\n",
    "    \n",
    "    return inner"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "330",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    return calc_fib_recurse(n)\n",
    "\n",
    "fib = timed(fib, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "331",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(28)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "332",
   "metadata": {},
   "source": [
    "But wait: why did we use the fancy `@-` syntax?\n",
    "The reason is simple: with `@` the decorating function (`timed` here) can only take a **single argument**, that is, the function to be decorated."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "333",
   "metadata": {},
   "source": [
    "To fix this behavior we need to rethink of what `@` is doing.\n",
    "Writing\n",
    "\n",
    "```python\n",
    "@timed\n",
    "def my_func():\n",
    "    pass\n",
    "```\n",
    "\n",
    "is equivalent to\n",
    "\n",
    "```python\n",
    "my_func = timed(my_func)\n",
    "```\n",
    "\n",
    "When called, `timed` returns the **inner closure**, where the original function is the free variable.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "334",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib.__closure__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "335",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib.__code__.co_freevars"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "336",
   "metadata": {},
   "source": [
    "So, for the syntax `@timed(10)` to work, where `10` is the number of repetition, `timed` should return **a decorator itself**, and not our closure.\n",
    "In practice, the `timed` function is a **decorator factory**: something that's able to return a \"parametrized\" decorator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "337",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import wraps\n",
    "from time import perf_counter\n",
    "\n",
    "def timed(num_reps=10):\n",
    "    \n",
    "    def decorator(fn):\n",
    "\n",
    "        @wraps(fn)\n",
    "        def inner(*args, **kwargs):\n",
    "            total_elapsed = 0\n",
    "            \n",
    "            for i in range(num_reps):\n",
    "                start = perf_counter()\n",
    "                result = fn(*args, **kwargs)\n",
    "                end = perf_counter()\n",
    "                total_elapsed += (perf_counter() - start)\n",
    "            \n",
    "            avg_elapsed = total_elapsed / num_reps\n",
    "            \n",
    "            print(f'Avg Run time: {avg_elapsed:.6f}s ({num_reps} reps)')\n",
    "            return result\n",
    "        \n",
    "        return inner\n",
    "    \n",
    "    return decorator  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "338",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_fib_recurse(n):\n",
    "    return 1 if n < 3 else calc_fib_recurse(n-1) + calc_fib_recurse(n-2)\n",
    "\n",
    "@timed(10)\n",
    "def fib(n):\n",
    "    return calc_fib_recurse(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "339",
   "metadata": {},
   "outputs": [],
   "source": [
    "fib(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "340",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "\n",
    "def calc_fact(n):\n",
    "    return 1 if n < 2 else n * calc_fact(n-1)\n",
    "\n",
    "@timed(20)\n",
    "@lru_cache()\n",
    "def fact(n):\n",
    "    return calc_fact(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "341",
   "metadata": {},
   "outputs": [],
   "source": [
    "fact(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "342",
   "metadata": {},
   "source": [
    "And yes, you can **stack multiple decorators**! 😎"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "343",
   "metadata": {},
   "source": [
    "## Generators"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "344",
   "metadata": {},
   "source": [
    "The concept of generators is very much tied to that of \"looping over some kind of container\".\n",
    "And we already used generators many time without realizing it.\n",
    "The easiest example is a standard `for` loop over some range of integers:\n",
    "\n",
    "```python\n",
    "for i in range(10):\n",
    "    # do something\n",
    "```\n",
    "\n",
    "The object that Python builds for us with `range(10)` is something very close to a generator. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "345",
   "metadata": {},
   "source": [
    "To understand generators, we first need to review what it means to be **iterable** and, more importantly, what is an **iterator**.\n",
    "\n",
    "1. An **iterable** is any object that can return one item at time until there are no items left.\n",
    "2. An **iterator** is an object that represents a stream of data and keeps track of the current position while processing the stream. It must implement two methods of the _iterator protocol_: `__next__` (returns the next element in the stream and advances the position) and `__iter__` (returns the iterator object itself)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "346",
   "metadata": {},
   "source": [
    "Delving deep into iterators is out of the scope of this section, so we are going to show you a practical example of a class that implements the \"iterator protocol\".\n",
    "\n",
    "Example: we want an iterator that build squares of successive integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "347",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Squares:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.i = 0\n",
    "\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "    def __next__(self):\n",
    "        if self.i >= self.n:\n",
    "            raise StopIteration\n",
    "\n",
    "        self.i += 1\n",
    "        return self.i ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "348",
   "metadata": {},
   "outputs": [],
   "source": [
    "for sq in Squares(5):\n",
    "    print(sq)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "349",
   "metadata": {},
   "source": [
    "We see that we can indeed loop over our custom `Squares` class.\n",
    "How Python is able to do this?\n",
    "\n",
    "1. The `__next__` method returns the next item, without going past the last one\n",
    "2. We raise a special exception if we are at the last item (or past)\n",
    "3. The `__iter__` method returns an instance of the class, meaning that the object itself _is_ an iterator"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "350",
   "metadata": {},
   "source": [
    "As you might have learned by now, we can implement some built-in behavior in our classes by using the so-called \"special methods\" or **dunder methods**: those with this naming schema `__method__`.\n",
    "\n",
    "A few examples:\n",
    "\n",
    "- The `len()` built-in can be defined with the `__len__` method\n",
    "- The string returned by `str()` can be defined with the `__str__` method. The same goes for an object's representation with `repr()` (and `__repr__`)\n",
    "- The `[]` (fetching an item by index from an ordered collection) can be defined with the `__getitem__` method"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "351",
   "metadata": {},
   "source": [
    "Python also has the built-in `next()` which does what you think it does: it takes an **iterator** object and returns the next element in the stream of data by calling the `__next__` method implemented by that object.\n",
    "\n",
    "It the same way, we can call `iter()` on an object as the **only** argument and return an iterator.\n",
    "Our class is doing that by implementing the `__iter__` method.\n",
    "\n",
    "But there's another way of calling `iter()` with **two arguments**: the first must be a **callable** (i.e., a function) and the second argument is a **sentinel**. As soon as the callable returns the sentinel value, then a `StopIteration` is raised."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "352",
   "metadata": {},
   "source": [
    "We could've written our `Squares` class using a closure instead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "353",
   "metadata": {},
   "outputs": [],
   "source": [
    "def square():\n",
    "    i = 0\n",
    "    def inner():\n",
    "        nonlocal i\n",
    "        i += 1\n",
    "        return i ** 2\n",
    "    return inner\n",
    "\n",
    "square_iter = iter(square(), 5**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "354",
   "metadata": {},
   "outputs": [],
   "source": [
    "for sq in square_iter:\n",
    "    print(sq)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "355",
   "metadata": {},
   "source": [
    "If the value returned by `square()` is 25 (our sentinel), then a `StopIteration` is raised."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "356",
   "metadata": {},
   "source": [
    "These two ways are identical: in the first case (the class), we built the iterator ourselves. In the second case, Python built it for us.\n",
    "\n",
    "The second example is a shorter code, but maybe a bit more difficult to understand if we didn't write it.\n",
    "There's a better way to do the same, and it's using **generators** with their special keyword `yield`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "357",
   "metadata": {},
   "source": [
    "The `yield` statement is used almost like a `return` statement in a function, but there is a huge difference.\n",
    "When the `yield` statement is encountered, Python returns whatever value `yield` specifies, but it **pauses** execution of the function.\n",
    "We can then _call_ the same function again and it will _resume_ from where the last `yield` was encountered.\n",
    "\n",
    "We do **not** resume the function by calling it the standard way, but we have to use the built-in `next()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "358",
   "metadata": {},
   "outputs": [],
   "source": [
    "def my_func():\n",
    "    print('line 1')\n",
    "    yield 'Python'\n",
    "    print('line 2')\n",
    "    yield 'Is'\n",
    "    print('line 3')\n",
    "    yield 'Great'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "359",
   "metadata": {},
   "outputs": [],
   "source": [
    "gen_my_func = my_func()\n",
    "type(gen_my_func)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "360",
   "metadata": {},
   "source": [
    "Here it is: our function returned _something_ different than the usual \"function\" object.\n",
    "We did not run anything in the function body until we use it as an argument of `next()`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "361",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(gen_my_func)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "362",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(gen_my_func)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "363",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(gen_my_func)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "364",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(gen_my_func)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "365",
   "metadata": {},
   "source": [
    "A `StopIteration` is raised if we are trying to go past the last `yield` statement.\n",
    "This should ring a bell: the `next()` method, a `StopIteration`... it seems that `gen_my_func` is very similar to an iterator.\n",
    "\n",
    "How can we check it?\n",
    "We know that an iterator **must** implement an `__iter__` method, right?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "366",
   "metadata": {},
   "outputs": [],
   "source": [
    "'__iter__' in dir(gen_my_func)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "367",
   "metadata": {},
   "source": [
    "And also the `__next__` method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "368",
   "metadata": {},
   "outputs": [],
   "source": [
    "'__next__' in dir(gen_my_func)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "369",
   "metadata": {},
   "source": [
    "We can also check that `iter()` applied on our object returns indeed the same thing.\n",
    "That is, our object is itself an iterator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "370",
   "metadata": {},
   "outputs": [],
   "source": [
    "gen_my_func"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "371",
   "metadata": {},
   "outputs": [],
   "source": [
    "iter(gen_my_func)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "372",
   "metadata": {},
   "source": [
    "Precisely the same object."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "373",
   "metadata": {},
   "source": [
    "How Python knows when to stop the iteration?\n",
    "When should it raise the `StopIteration`?\n",
    "In the simple example above, it's easy: when there's nothing else after the last `yield`.\n",
    "\n",
    "Well, not really \"nothing\". Remember that Python returns `None` for us if we don't specify any `return` statement.\n",
    "So, in general, the iteration will terminate **when we return something from the function** using the `return` statement.\n",
    "\n",
    "Let's go back to our `squares` example and refactor it to have a generator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "374",
   "metadata": {},
   "outputs": [],
   "source": [
    "def squares(sentinel):\n",
    "    i = 0\n",
    "    while True:\n",
    "        if i < sentinel:\n",
    "            yield i ** 2\n",
    "            i += 1\n",
    "        else:\n",
    "            return 'Finished.'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "375",
   "metadata": {},
   "outputs": [],
   "source": [
    "sq = squares(3)\n",
    "next(sq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "376",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(sq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "377",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(sq) # this is the last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "378",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(sq) # a StopIteration is raised"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "379",
   "metadata": {},
   "source": [
    "Note how in the generator function above we incremented the number `i` **after** the `yield` statement.\n",
    "That is, as soon as we resume our function, we make sure to be in the correct position of our _stream of data_ – in this case, a sequence of integers squared."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "380",
   "metadata": {},
   "source": [
    "### Create an interable from a generator"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "381",
   "metadata": {},
   "source": [
    "As we know, generators are iterators.\n",
    "This means that we can **consume** them (i.e., exhaust the elements they can return).\n",
    "However, sometimes we want to create an interable instead, like a list, that we can loop over as many time as we want.\n",
    "\n",
    "We know all the pieces to put together to obtain such a thing: we need a class that implements the iterator protocol."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "382",
   "metadata": {},
   "source": [
    "Let's consider again the example of generating squares of integers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "383",
   "metadata": {},
   "outputs": [],
   "source": [
    "def squares_gen(n):\n",
    "    for i in range(n):\n",
    "        yield i ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "384",
   "metadata": {},
   "outputs": [],
   "source": [
    "sq = squares_gen(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "385",
   "metadata": {},
   "outputs": [],
   "source": [
    "for num in sq:\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "386",
   "metadata": {},
   "source": [
    "But our generator is now exhausted and it has nothing left to return:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "387",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(sq)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "388",
   "metadata": {},
   "source": [
    "To restart the iteration, we need to create another instance of the generator.\n",
    "We can wrap this behavior in an **iterable class**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "389",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Squares:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "\n",
    "    def __iter__(self):\n",
    "        return squares_gen(self.n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "390",
   "metadata": {},
   "outputs": [],
   "source": [
    "sq = Squares(5)\n",
    "[num for num in sq]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "391",
   "metadata": {},
   "source": [
    "And we can do it again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "392",
   "metadata": {},
   "outputs": [],
   "source": [
    "[num for num in sq]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "393",
   "metadata": {},
   "source": [
    "We can put everything is a single class to make things easier to read:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "394",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Squares:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        \n",
    "    @staticmethod\n",
    "    def squares_gen(n):\n",
    "        for i in range(n):\n",
    "            yield i ** 2\n",
    "        \n",
    "    def __iter__(self):\n",
    "        return Squares.squares_gen(self.n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "395",
   "metadata": {},
   "outputs": [],
   "source": [
    "sq = Squares(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "396",
   "metadata": {},
   "outputs": [],
   "source": [
    "[num for num in sq]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "397",
   "metadata": {},
   "outputs": [],
   "source": [
    "[num for num in sq]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "398",
   "metadata": {},
   "source": [
    "### Combining generators"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "399",
   "metadata": {},
   "source": [
    "We have to be careful when using a generator with one another.\n",
    "For example, the `enumerate()` built-in returns a generator to iterate over an indexed container."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "400",
   "metadata": {},
   "outputs": [],
   "source": [
    "def squares(n):\n",
    "    for i in range(n):\n",
    "        yield i ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "401",
   "metadata": {},
   "outputs": [],
   "source": [
    "sq = squares(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "402",
   "metadata": {},
   "outputs": [],
   "source": [
    "enum_sq = enumerate(sq)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "403",
   "metadata": {},
   "source": [
    "Now, `enumerate` builds a generator itself, so `sq` had not been consumed yet at this point:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "404",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(sq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "405",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(sq)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "406",
   "metadata": {},
   "source": [
    "But since we now have consumed **2 elements** from `sq`, when we use `enumerate` it will also have two less items from `sq`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "407",
   "metadata": {},
   "outputs": [],
   "source": [
    "next(enum_sq)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "408",
   "metadata": {},
   "source": [
    "And this might not be what you expected: the value is the **third** element of `sq` ($2^2$), while the index is `0`, as if we were starting from the beginning.\n",
    "From the point of view of the generator returned by `enumerate`, **we are at the beginning**.\n",
    "\n",
    "So, beware when you are combining multiple generators, and think carefully what's the behavior you expect."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "409",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "410",
   "metadata": {},
   "outputs": [],
   "source": [
    "%reload_ext tutorial.tests.testsuite"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "411",
   "metadata": {},
   "source": [
    "### Password checker factory"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "412",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "Create a function called `password_checker_factory` that can be used to generate different password checkers.\n",
    "This function will take **four parameters**: `min_uppercase`, `min_lowercase`, `min_punctuation`, and `min_digits`.\n",
    "They represents the constraints on a given password:\n",
    "\n",
    "1. The minimum number of uppercase letters.\n",
    "2. The minimum number of lowercase letters.\n",
    "3. The minimum number of punctuation characters.\n",
    "4. The minimum number of digits.\n",
    "\n",
    "\n",
    "The `create_password_checker` function generates another function that assesses a given password (string).\n",
    "This resulting function returns a **tuple with two elements**:\n",
    "\n",
    "1. The first element is a **boolean** indicating if the password passed validation.\n",
    "2. The second element is a **dictionary** mapping `uppercase`, `lowercase`, `punctuation`, and `digits` to the difference between the actual count of each type in the password and its minimum requirement. Positive values denote exceeding, and negative values denote not meeting these minimums."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "413",
   "metadata": {},
   "source": [
    "For example, to create a password checker that requires a password to have at least 2 uppercase letters, at least 3 lowercase letters, at least 1 punctuation mark, and at least 4 digits, we can write\n",
    "\n",
    "```python\n",
    "pc1 = create_password_checker(2, 3, 1, 4)\n",
    "```\n",
    "\n",
    "If we test the following passwords:\n",
    "\n",
    "```python\n",
    "print(pc1('Ab!1'))\n",
    "print(pc1('ABcde!1234'))\n",
    "```\n",
    "\n",
    "We should get these results:\n",
    "\n",
    "```python\n",
    "(False, {'uppercase': -1, 'lowercase': -2, 'punctuation': 0, 'digits': -3})\n",
    "(True, {'uppercase': 0, 'lowercase': 0, 'punctuation': 0, 'digits': 0})\n",
    "```\n",
    "\n",
    "In this example, the first password `Ab!1` is **invalid**: it lacks `1` uppercase character, `2` lowercase, and `3` digits.\n",
    "Instead, the second password is **valid**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "414",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%ipytest\n",
    "\n",
    "def solution_password_checker_factory(min_up: int, min_low: int, min_pun: int, min_dig: int):\n",
    "    \"\"\"Password checker factory\"\"\"\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "415",
   "metadata": {},
   "source": [
    "### String range"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "416",
   "metadata": {},
   "source": [
    "Create a function called `str_range` that emulates the the built-in `range`, but for characters.\n",
    "That is, when you call `str_range('j', 'm')`, you will get back a generator that produces each of the letters in between.\n",
    "\n",
    "The function takes two **mandatory** parameters, `start` and `end`, plus an **optional** `step` value, with default value of `1`.\n",
    "\n",
    "As opposed to Python's numeric `range()`, the string ranges generated by `str_range` are **including** their final string (that is, `end`).\n",
    "Moreover, since Python 3 supports non-Latin characters (and even non-alphabetic), it should be possible to use any of them as a `start` or `end` value."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "417",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "    <h4><b>Hint</b></h4> You might want to look up what it means to get an \"integer representing the Unicode code point of that character\". The <a href=\"https://docs.python.org/3/library/\">official docs of Python</a> might help you.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "418",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "    <h4><b>Note</b></h4> It's okay if in some languages it doesn't quite exist the idea of \"iterating over a range of characters\".\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "419",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%ipytest\n",
    "\n",
    "def solution_str_range(start: str, end: str, step: int):\n",
    "    \"\"\"Return a generator from `start` to `end` strings (inclusive)\"\"\"\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "420",
   "metadata": {},
   "source": [
    "### Read `n` lines"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "421",
   "metadata": {},
   "source": [
    "Create a function called `read_n_lines` that takes two arguments: the filename from which to read, and the **maximum number of lines** that should be returned with each iteration.\n",
    "\n",
    "For example, if we had a file like\n",
    "\n",
    "```\n",
    "File line 0 aaa\n",
    "File line 1 bbb\n",
    "File line 2 ccc\n",
    "File line 3 ddd\n",
    "File line 4 eee\n",
    "File line 5 fff\n",
    "File line 6 ggg\n",
    "```\n",
    "\n",
    "Then we could use the `read_n_lines` to read pairs of lines:\n",
    "\n",
    "```python\n",
    "for two_lines in read_n_lines(filename, 2):\n",
    "    print(two_lines.rstrip())\n",
    "```\n",
    "\n",
    "And the output would be:\n",
    "\n",
    "```\n",
    "File line 0 aaa\n",
    "File line 1 bbb\n",
    "\n",
    "File line 2 ccc\n",
    "File line 3 ddd\n",
    "\n",
    "File line 4 eee\n",
    "File line 5 fff\n",
    "\n",
    "File line 6 ggg\n",
    "```\n",
    "\n",
    "The last line is returned by itself because the file has an odd number of lines."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "422",
   "metadata": {},
   "source": [
    "We could also do:\n",
    "\n",
    "```python\n",
    "for four_lines in read_n(filename, 4):\n",
    "    print(four_lines.rstrip())\n",
    "```\n",
    "\n",
    "And get back\n",
    "\n",
    "```\n",
    "File line 0 aaa\n",
    "File line 1 bbb\n",
    "File line 2 ccc\n",
    "File line 3 ddd\n",
    "\n",
    "File line 4 eee\n",
    "File line 5 fff\n",
    "File line 6 ggg\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "423",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "    <h4><b>Note</b></h4> With each iteration, <code>read_n_lines</code> shoul return a string (<strong>not</strong> a list) containing up to the number of lines specified by the parameter <code>lines</code>.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "424",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%ipytest\n",
    "\n",
    "def solution_read_n_lines(filename: str, lines: int):\n",
    "    \"\"\"Read multiple lines from a file\"\"\"\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "425",
   "metadata": {},
   "source": [
    "### Only run once"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "426",
   "metadata": {},
   "source": [
    "Create a decorator called `once` that restricts a function to run at most **once every `allowed_time` seconds**, where `allowed_time` is a parameter with a default value of `15`.\n",
    "\n",
    "If you try to invoke the function too soon, the decorator should raise an exception called `RuntimeError` which tells you how long you need to wait before running your function again.\n",
    "The error message should be `Wait another {remaining_time} seconds`, where `remaining_time` is the time left to wait before running the function again."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "427",
   "metadata": {},
   "source": [
    "For example, the following code:\n",
    "\n",
    "```python\n",
    "import time\n",
    "\n",
    "@once(15)\n",
    "def hello(name):\n",
    "    return f\"Hello, {name}!\"\n",
    "\n",
    "for i in range(30):\n",
    "    print(i)\n",
    "    try:\n",
    "        time.sleep(3)\n",
    "        print(hello(f\"attempt #{i}\"))\n",
    "    except TooSoonError as err:\n",
    "        print(f\"Too soon: {err}\")\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "428",
   "metadata": {},
   "source": [
    "Should print something like:\n",
    "\n",
    "```\n",
    "0\n",
    "Hello, attempt #0\n",
    "1\n",
    "Too soon: Wait another 12.00 seconds\n",
    "2\n",
    "Too soon: Wait another 8.99 seconds\n",
    "3\n",
    "Too soon: Wait another 5.98 seconds\n",
    "4\n",
    "Too soon: Wait another 2.98 seconds\n",
    "5\n",
    "Hello, attempt #5\n",
    "6\n",
    "Too soon: Wait another 12.00 seconds\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "429",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">\n",
    "    <h4><b>Note</b></h4> The decorator should handle <strong>any kind</strong> of function, i.e., it should not care about the kind or number of parameters the function accepts.\n",
    "</div>\n",
    "\n",
    "<div class=\"alert alert-block alert-danger\">\n",
    "    <h4><b>Important</b></h4> The tests need to run for some time to check the solution. Don't worry if the execution of the cell below seems to be hanging: it's not.\n",
    "</div>\n",
    "\n",
    "<div class=\"alert alert-block alert-info\">\n",
    "    <h4><b>Hint</b></h4> If you are stuck, you can always comment the line <code>%%ipytest</code> to skip the tests, and enable them again when you think your solution is ready.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "430",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%ipytest\n",
    "import time\n",
    "\n",
    "def solution_once(allowed_time: int = 15) -> t.Callable:\n",
    "    \"\"\"Decorator to run a function at most once per given seconds\"\"\"\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}