4_Functional_Python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Functional Programming\n",
    "Suppose you live in a world where you don't use classes (gasp!). Why in the world would you want to do that? The reason is that some problems are better suited when you don't mutate an underlying object. OOP uses attributes to not only keep state but mutate state. Because the statefulness of an object can be mutated, there are use cases where mutations hinders rather than helps: race conditions in threaded code, debugging complex mutations across multiple method calls, non-parallelizable so cannot distribute the computation, etc. Hence, some problems are better where you don't remember something about the object after it is used--it is stateless.\n",
    "\n",
    "Functional Programming (often abbreviated as FP) treat objects as immutable and create new objects when needed--instead of mutating an object. An important nuance about FP is that it isn't about making things \"stateless\"; for example, there are still stateful things like variables and data structures (ie lists) in FP. FP is about preventing *mutating* state. In my opinion, FP tries to enforce a function as a single unit of transformation, making a function call atomic. Either a function succeeded in transforming the data or it didn't. You aren't supposed to inspect intermediate results--which is what you can do in OOP.\n",
    "\n",
    "At a high level, I want to leave you with the idea that, in contrast to OOP, FP deliberately separates data and code. In FP, data is data and code (ie functions) is code. A procedural (or imperative) style tends to run data through code, store the result, run data through more code, etc--you are manipulating data. In constrast, a functional style tends to manipulate functions: construct more complex functions out of simpler functions (like Lego bricks) and then run data through the complex function.\n",
    "\n",
    "If you are a boring, math professor who likes to think that CS is just applied math, then you probably think in terms of the textbook definitions of Functional Programming: a) **immutability**, b) **pure functions**, and **higher-order functions**.\n",
    "* **Immutability**: nothing ever changes. What you put into a function, you get something else out. Stay the way you are--never change. Don't update yourself; transform into something new.\n",
    "* **Pure functions**: functions ideally should be completely deterministic in that given a specific input, the output will ALWAYS return the same output. In fact, nothing else should change at all; a __side effect__ is something that changes outside the scope of the function. Pure functions, by definition, cannot have a side effect. Sometimes, this constrant is too difficult, so the lesser constraint is `idempotency`: if something else changes (that is not the output), then something always changes in exactly same way--the side effect is deterministic.\n",
    "* **Higher-order functions**: since functions are first-class citizens in Python, what they means is that you can pass functions into functions. You can have a function return a function. You can define functions inside a function.\n",
    "\n",
    "If you are very pedantic, you can say that Functional Programming is the implementation of *Lambda Calculus*, which is \"a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.\" This explains why FP style has a heavy \"mathy\" predisposition on approaching problems. (In fact, Python's `lambda` keyword, often used with FP's `map/filter/reduce`, comes from lambda calculus).\n",
    "\n",
    "But then again, do I *look* that old? Carpe diem! Let's go through some actual, fun examples of Functional Programming, so we can ditch the textbook answers. Books are for squares! Also, in this notebook we will be tempered in our approach to programming: when to use functional programming and when to mix functional programming with OOP.\n",
    "\n",
    "Reader tip: FP is a denser style than other programming styles when you are just beginning. Feel free to read the sections you find interesting and skip the sections you are not interested in. You don't have to understand everything. A lot of these sections are included for *completeness* and are not necessary for a reader to understand in order to use the juicy bits of FP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Something or Nothing (None)\n",
    "In Python, functions (and all callables like methods and classes) always return something. Usually, you return some calculated result. Other times, your function is really running a check on the inputs and doesn't return anything (or does it?). If your function does not explicitly return something, then it returns `None`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def double(x):  # returns something useful\n",
    "    return x * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Life is good\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "def is_even(x):  # returns None\n",
    "    if x % 2 == 0:\n",
    "        print(\"Life is good\")\n",
    "print(is_even(10))  # None is printed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "None\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "# all logically equivalent\n",
    "def do_nothing1():\n",
    "    pass\n",
    "\n",
    "def do_nothing2():\n",
    "    return\n",
    "\n",
    "def do_nothing3():\n",
    "    return None\n",
    "\n",
    "print(do_nothing1())  # None is printed\n",
    "print(do_nothing2())  # None is printed\n",
    "print(do_nothing3())  # None is printed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  3           0 LOAD_CONST               0 (None)\n",
      "              2 RETURN_VALUE\n",
      "None\n",
      "  6           0 LOAD_CONST               0 (None)\n",
      "              2 RETURN_VALUE\n",
      "None\n",
      "  9           0 LOAD_CONST               0 (None)\n",
      "              2 RETURN_VALUE\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "# identical bytecode for each of the functions\n",
    "import dis\n",
    "\n",
    "print(dis.dis(do_nothing1))\n",
    "print(dis.dis(do_nothing2))\n",
    "print(dis.dis(do_nothing3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "HI\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "print(print(\"HI\"))  # print() itself is a function, so it returns something--None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `map`/`filter`/`reduce`\n",
    "List comprehensions are generally the \"Pythonic\" way to do things. Let's try to do the same using FP syntax.  A list comprehension can do both `map` and `filter` and the reverse is true: all list comprehensions are a combination of `map` and `filter`. Instead of updating/modifying a list, just return a new one.\n",
    "\n",
    "FP does *not* use (explicit) loops; instead FP uses `map`/`filter`/`reduce` (and recursion) to achieve the same results as loops. Also remember the added bonus is that `map` and `filter` are lazy (do not immediately execute so saves on runtime) and uses low memory footprint. `reduce` is eagerly/immediately executed but also uses low memory footprint."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# double element: OOP where mutating/updating a list (using a method)\n",
    "accumulator = []  # the list is being mutated\n",
    "for i in range(10):\n",
    "    accumulator.append(i * 2)\n",
    "accumulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# double element: FP equivalent with no mutations\n",
    "list(map(lambda x: x * 2, range(10)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5, 7, 9]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# remove evens: OOP where mutating/updating a list\n",
    "accumulator = []\n",
    "for i in range(10):\n",
    "    if i % 2:\n",
    "        accumulator.append(i)\n",
    "accumulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5, 7, 9]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# remove evens: FP equivalent with no mutations\n",
    "list(filter(lambda x: x % 2, range(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A list comprehension cannot be used to emulate `reduce`. You'll need a for-loop with an accumulator to get the equivalent of FP's `reduce`. However, the accumulator is stateful (by having to explicitly store a variable) whereas `reduce` does not have any global variable that kept between function calls.\n",
    "\n",
    "Note: Guido van Rossum does not like `reduce` and prefers an explicit for-loop. That is why `reduce` is no longer a builtin function in Python 3 and thus has to be imported from `functools`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# imperative approach\n",
    "accumulator = 0\n",
    "for i in range(10):\n",
    "    accumulator += i\n",
    "accumulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# FP: not need for statefulness in the form of an intermediate/temporary accumulator variable\n",
    "from functools import reduce\n",
    "\n",
    "reduce(lambda x, y: x + y, range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# reduce can take a 3rd argument where it is an initializer. Useful when the iterable is empty\n",
    "reduce(lambda x, y: x + y, [], 42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When you are given a hammer, everything looks like a nail. Use Functional Programming when it benefits you. Also, learn when to not force FP into a problem that it is less appropriate. There are some problems that lends itself to OOP and there are some that lend themselves to FP. Let me give you an example where OOP is far superior.  \n",
    "Always keep in mind the Golden Rule of programming? ~~Do onto others whatever you would like them to do to you.~~ **Use the best tool for the problem.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ\n",
      "['Z', 'O', 'l', 'h', 'j', 'k', 'e', 'd', 'D', 'g']\n"
     ]
    }
   ],
   "source": [
    "from string import ascii_letters\n",
    "from random import choices\n",
    "\n",
    "print(ascii_letters)\n",
    "lots_of_letters = choices(ascii_letters, k=100000)\n",
    "print(lots_of_letters[:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "result_OOP = \"\".join(lots_of_letters)  # OOP is much faster since runtime is O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 171 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "result_FP = reduce(lambda accumulated_string, char: accumulated_string + char, lots_of_letters)  # FP is much slower since runtime is O(n ** 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result_OOP == result_FP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Reach for the Stars: `starmap`\n",
    "1 weakness of a regular `map` function is it usually takes 1 argument: the element itself. One way to add an additional argument is to take the other arguments and hard code them into the `lambda` function inside the `map`. However, what if the second arguments keep changing? The other (and preferred) way is to use `starmap()`. You can think of `starmap` as `map(*args)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 12, 30]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import itertools\n",
    "\n",
    "list(\n",
    "    itertools.starmap(\n",
    "        lambda x, y: x * y, \n",
    "        [(1, 2), (3, 4), (5, 6)],  # second argument is list of \"pre-zipped\" arguments\n",
    "    )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 12, 30]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# here's a rough implementation of starmap\n",
    "def starmap(function, iterable):\n",
    "    for args in iterable:\n",
    "        yield function(*args)\n",
    "\n",
    "list(\n",
    "    starmap(\n",
    "        function=lambda x, y: x * y, \n",
    "        iterable=[(1, 2), (3, 4), (5, 6)],\n",
    "    )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unstoppable Force Meets an <i>Immutable</i> Object\n",
    "Immutability means that an object cannot be changed or updated. Many useful objects are mutable: list, dict, sets. Other useful objects are immutable: string and bytes, numbers (float, int), bool, None, tuples. For example, you cannot make a 1 equal a 2 no matter how hard you try. How do you test if an object is updated or an entirely a new one? Check for identity using `id()` (which gets memory address) or `is`. Since immutable types do not have updates, they do not have the methods: `pop()`, `append()`, `add()`, `update()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1658661072328 []\n",
      "1658661072328 [1]\n",
      "1658661072328 [1, 2]\n"
     ]
    }
   ],
   "source": [
    "l = []\n",
    "print(id(l), l)\n",
    "l.append(1)\n",
    "print(id(l), l)  # same object before and after\n",
    "l += [2]\n",
    "print(id(l), l)  # same object before and after"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's show that an immutable object's identity changes every time you rebind the variable to new data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1658661570256 9000\n",
      "1658661570352 9001\n"
     ]
    }
   ],
   "source": [
    "x = 9000\n",
    "print(id(x), x)\n",
    "x += 1\n",
    "print(id(x), x)  # totally different object"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`bool` only has 2 instances: `True` and `False`. Thus, all `False`s are the SAME `False` and not only are they equivalent to each other, they are 1 and the same object--they are `id`entical to each other--in other words, there is only 1 `False`.\n",
    "\n",
    "`None` is a singleton--there is only 1 unique `None` instance of the `NoneType` class. All `None`s are identical to each other. For checking identity, use the `is` operator. For example, you often see the code `if x is None:`--the reason is `is` for checking identity while `==` is for checking value equivalence.  \n",
    "Note: the reason why we don't use `if x is True:` (even though this is logically correct) is that the `if` operator automatically casts the object to a `bool`. Hence, `if x:` is sufficient."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1794306208 True\n",
      "1794306208 True\n",
      "1794306208 True\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "x = True\n",
    "y = not False\n",
    "z = bool(10)\n",
    "print(id(x), x)\n",
    "print(id(y), y)\n",
    "print(id(z), z)\n",
    "print(x == y == z)\n",
    "print(x is y is z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1794352272\n",
      "1794352272\n",
      "1794352272\n",
      "1794352272\n",
      "1794352272\n",
      "True\n",
      "\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "    print(id(None))\n",
    "print(None is None is None is None is None is None is None is None is None is None is None) # they are exactly the same object\n",
    "print(\n",
    "    None\n",
    "    is (lambda: print())()  # print returns None\n",
    "    is type(None)()  # get the class and then create an instance of the class\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`is` and `==` are not entirely equivalent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print([] is [])\n",
    "print([] == [])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What I mean by identity check is this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# immutable object\n",
    "x = None\n",
    "y = None\n",
    "print(x is y)\n",
    "print(id(x) == id(y))  # logically equivalent to the previous line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# mutable object\n",
    "x = []\n",
    "y = []\n",
    "print(x is y)\n",
    "print(id(x) == id(y))  # logically equivalent to the previous line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1], [1], [1], [1], [1], [1], [1], [1], [1], [1]]\n",
      "[[None], [None], [None], [None], [None], [None], [None], [None], [None], [None]]\n"
     ]
    }
   ],
   "source": [
    "# mutable object\n",
    "x = [[1]] * 10\n",
    "print(x)\n",
    "x[0][0] = None\n",
    "print(x)  # everything changed! not expected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1], [1], [1], [1], [1], [1], [1], [1], [1], [1]]\n",
      "[[None], [1], [1], [1], [1], [1], [1], [1], [1], [1]]\n"
     ]
    }
   ],
   "source": [
    "# mutable object\n",
    "x = [[1] for i in range(10)]\n",
    "print(x)\n",
    "x[0][0] = None\n",
    "print(x)  # only 1 element changed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[9 2 3]\n",
      " [4 5 6]]\n",
      "[[9 2 3]\n",
      " [4 5 6]]\n"
     ]
    }
   ],
   "source": [
    "# real life problem I struggled with over 2 hours\n",
    "import numpy as np\n",
    "\n",
    "arr1 = np.array([[1, 2, 3], [4, 5, 6]])\n",
    "arr2 = arr1  # I (mistakenly) thought I made a copy\n",
    "arr1[0][0] = 9\n",
    "print(arr1)\n",
    "print(arr2)  # also changed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False 1658665249736 1658665249800\n",
      "[[1, 2, 3], [4, 5, 6], None]\n",
      "[[1, 2, 3], [4, 5, 6]]\n",
      "[[9, 2, 3], [4, 5, 6], None]\n",
      "[[9, 2, 3], [4, 5, 6]]\n"
     ]
    }
   ],
   "source": [
    "# made a \"copy\" this time: problem is it was only a shallow copy\n",
    "import copy\n",
    "\n",
    "l1 = [[1, 2, 3], [4, 5, 6]]\n",
    "l2 = copy.copy(l1) # l1.copy()\n",
    "print(l1 is l2, id(l1), id(l2))  # they are 2 different objects but not exactly decoupled\n",
    "\n",
    "l1.append(None)\n",
    "print(l1)\n",
    "print(l2)  # unchanged, whew!\n",
    "\n",
    "l1[0][0] = 9\n",
    "print(l1)\n",
    "print(l2)  # changed, why?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Small Detour on Copying\n",
    "Python has 2 ways to copy objects: shallow and deep.\n",
    "\n",
    "**Shallow copy**: copies all the pointers/memory address of the underlying objects in a data structure (ie list). However, if you have a list within a list, only the inner list's memory address is copied--not the elements themselves. You get the problem shown above.\n",
    "\n",
    "**Deep copy**: Recursively copy all pointers to the underlying objects, including nested data structures and their elements. Once you made a deep copy, the original object is completely decoupled from the copy--you can do anything to the original object and there will be changes to the copy. The problem is deep copying is a relatively slow operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False 1658661072392 1658661072840\n",
      "[[1, 2, 3], [4, 5, 6], None]\n",
      "[[1, 2, 3], [4, 5, 6]]\n",
      "[[9, 2, 3], [4, 5, 6], None]\n",
      "[[1, 2, 3], [4, 5, 6]]\n"
     ]
    }
   ],
   "source": [
    "l1 = [[1,2,3], [4,5,6]]\n",
    "l2 = copy.deepcopy(l1)\n",
    "print(l1 is l2, id(l1), id(l2))  # they are 2 different objects but completed decoupled\n",
    "\n",
    "l1.append(None)\n",
    "print(l1)\n",
    "print(l2)  # unchanged, whew!\n",
    "\n",
    "l1[0][0] = 9\n",
    "print(l1)\n",
    "print(l2)  # unchanged, yes!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### In conclusion:\n",
    "There are some confusion rules about assignment that makes the mutability of an object a liability. Updating an object is more confusing than creating a brand new object. Functional programming avoids/solves this problem by creating new objects instead of mutating an existing object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Is Your Function Pure of Heart?\n",
    "What is a `pure` function vs `idempotent` function vs functions that are neither?\n",
    "\n",
    "**Pure Function**: A function is pure if it always returns the same outputs given the same inputs. Also, a pure function does not mutate the state of things outside of its scope--ie no side effects. Pure functions are easier to reason about and test because they only do 1 thing and are totally decoupled between function calls. Nothing about the last function call is remembered--thus is stateless.\n",
    "\n",
    "**Idempotent Function**: A function that always returns the same outputs given the same inputs. An idempotent function may change variables outside of its scope. A pure function is subset of idempotent function, so all pure functions are idempotent functions but not vice versa."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def double_pure(x):  # a pure function; input always has a deterministic output. Nothing else changes\n",
    "    return x * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 Hello\n"
     ]
    }
   ],
   "source": [
    "def double_idempotent(x):  # has side effect, by doing something outside of its scope: assigning \"Hello\" to y in global scope\n",
    "    global y\n",
    "    y = \"Hello\"\n",
    "    return x * 2\n",
    "\n",
    "print(double_idempotent(1), y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[None]\n",
      "[None, None]\n",
      "[None, None, None]\n"
     ]
    }
   ],
   "source": [
    "def not_pure_nor_idempotent(x):  # has side effect of mutating the object\n",
    "    x.append(None)\n",
    "\n",
    "simple_list = []\n",
    "not_pure_nor_idempotent(simple_list)\n",
    "print(simple_list)\n",
    "not_pure_nor_idempotent(simple_list)\n",
    "print(simple_list)\n",
    "not_pure_nor_idempotent(simple_list)\n",
    "print(simple_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ~~Functions that are High~~ Higher-Order Functions\n",
    "The previous examples are definitional and more academic. Let's go through 1 last definition and then we'll see the fun, applied use cases.\n",
    "\n",
    "**Higher-order function**: A function that either takes in a function as an argument and/or returns a function. Here's simple examples of higher-order functions.\n",
    "```python\n",
    "def g(f):  # g() is a higher-order function because it takes in a function\n",
    "    f()\n",
    "\n",
    "def g(): # g() is a higher-order function because it returns a function\n",
    "    return lambda ...\n",
    "\n",
    "def h(f, g):  # h() is a higher-order function because it takes in 2 functions and returns a function\n",
    "    return lambda x: f(g(x))  # this specific example is called function composition\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def run_op(func, x):  # takes in a function\n",
    "    return func(x)\n",
    "\n",
    "run_op(sum, range(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<function add_two.<locals>.<lambda> at 0x0000024BA6FC4BF8>\n",
      "44\n"
     ]
    }
   ],
   "source": [
    "def add_two():  # returns a function\n",
    "    return lambda x: x + 2\n",
    "\n",
    "print(add_two())  # output is a function, not a value\n",
    "print(add_two()(42))  # call the returned function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<function time_func.<locals>.inner at 0x0000024BA6FC4A60>\n",
      "Runtime: 0.0\n",
      "45\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "def time_func(func):  # takes in a function and returns a function\n",
    "    def inner(*args, **kwargs):\n",
    "        start_time = time.time()\n",
    "        result = func(*args, **kwargs)\n",
    "        end_time = time.time()\n",
    "        print(\"Runtime: {}\".format(end_time - start_time))\n",
    "        return result\n",
    "    return inner\n",
    "\n",
    "print(time_func(sum))  # output is a function, not a value\n",
    "print(time_func(sum)(range(10)))  # call the returned function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Music to My Ears: Decorate and Compose\n",
    "Decorators are introduced in `1_Pragmatic_Python.ipynb`. Nonetheless, here's a refresher on decorators: you have a function that you want to change some behavior before or after the function call. Basically you want to compose a function that alter the behavior of the original function.\n",
    "\n",
    "Now you may be wondering: why would you want a decorator if you can just change the original function (if all you are going to do is change something before and/or after the original function call). The reason could be:\n",
    "* You can't change the original function because it is too complicated to understand.\n",
    "* You can't change the original function because you don't have access to change it. For example, many numpy functions are written in C, so you literally could not change the source code.\n",
    "* You can't change the original function because it is used everywhere and you don't know which ones you want to change.\n",
    "* You just wanna be ~~cool~~ a pro!\n",
    "\n",
    "Note: be careful. A decorator is not exactly function composition. A decorator is not exactly f(g(x)) but something close. If you want to see a function composition example, then look towards the bottom of this notebook or just search for \"Function Composition\".\n",
    "\n",
    "\n",
    "### My Variables and I Need Some Closure\n",
    "Quick thing. A decorator is closure. Closure is a function that has access to variable(s) defined <i>outside</i> of the function. Closure is called closure since it has access to variables that are not locally defined, which are \"closed over\" by the closure function. This academic definition is confusing even though the idea is actually quite simple. Here's a simple example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<function outer.<locals>.inner at 0x000002054B213430>\n",
      "they captured me they are closing in\n"
     ]
    }
   ],
   "source": [
    "def outer():\n",
    "    x = \"they captured me\"\n",
    "    y = \"they are closing in\"\n",
    "    def inner():\n",
    "        print(x, y)  # x and y are not defined or passed in as arguments to inner()\n",
    "    return inner\n",
    "\n",
    "inner = outer()\n",
    "print(inner)\n",
    "inner()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Closure binds late. *Late binding* means that the value of a variable is only looked up at runtime. Basically, the value of a closed over variable is only determined when the function is called.  \n",
    "Note: Late binding follows the LEGB rule. See `6_Pedantic_Python_Tricks.ipynb` to learn more about the LEGB rule.\n",
    "\n",
    "Again the technical definition sounds confusing. An easy example will be illustrate the point better."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "thanks\n",
      "bye\n"
     ]
    }
   ],
   "source": [
    "def outer():\n",
    "    variable = \"hi\"  # notice this value is never printed\n",
    "    \n",
    "    def inner():\n",
    "        print(variable)  # this variable is only looked up when this function is run\n",
    "\n",
    "    variable = \"thanks\"\n",
    "    inner()  # look up variable at this point in time\n",
    "    \n",
    "    variable = \"bye\"\n",
    "    inner()  # look up variable at this point in time\n",
    "\n",
    "outer()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now back to decorators. A decorator is closure since you pass the function (you want to decorate) to the outer function, but that same function is accessable in the inner function without being passed as an argument into the inner function. Decorators allow you to do something *before* and/or *after* your original function is called. You can also change the arguments passed into your original function, so you may consider that effect as <i>\"during\"</i> your original function call. In short, a decorate alters the original function call *before* and/or *after* and/or *during*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_my_function_polite(func):\n",
    "    def inner(arg):\n",
    "        print(\"hello!\")  # before\n",
    "        result = func(arg.upper())  # \"during\"; also notice I'm storing results if I want to do something after my function call\n",
    "        print(\"bye!\")  # after\n",
    "        return result\n",
    "    return inner  # notice I am returning a function back\n",
    "\n",
    "def double(x):\n",
    "    return x * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function __main__.make_my_function_polite.<locals>.inner(arg)>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_my_function_polite(double)  # notice that a function is returned"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello!\n",
      "bye!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'THANKSTHANKS'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_my_function_polite(double)(\"thanks\")  # apply decorator 1 time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Pythonic syntax is to use the `@` sign instead of manual function call (on original function and assigning back to original function name). The following 2 cells are logically equivalent. The first cell is the preferred syntax."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function __main__.make_my_function_polite.<locals>.inner(arg)>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def make_my_function_polite(func):\n",
    "    def inner(arg):\n",
    "        print(\"hello!\")  # before\n",
    "        result = func(arg.upper())  # \"during\"; also notice I'm storing results if I want to do something after my function call\n",
    "        print(\"bye!\")  # after\n",
    "        return result\n",
    "    return inner  # notice I am returning a function back\n",
    "\n",
    "@make_my_function_polite\n",
    "def double(x):\n",
    "    return x * 2\n",
    "\n",
    "double"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function __main__.make_my_function_polite.<locals>.inner(arg)>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def make_my_function_polite(func):\n",
    "    def inner(arg):\n",
    "        print(\"hello!\")  # before\n",
    "        result = func(arg.upper())  # during; also notice I'm storing results if I want to do something after my function call\n",
    "        print(\"bye!\")  # after\n",
    "        return result\n",
    "    return inner  # notice I am returning a function back\n",
    "\n",
    "def double(x):\n",
    "    return x * 2\n",
    "\n",
    "double = make_my_function_polite(double)  # decorator function call on original function and then assign to original function name\n",
    "double"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In fact, you can even stack/chain decorators. The decorator closest to the function the decorator is applied first. Now that I think about it, a decorator is in some sense like a generator but for functions--decorators change the function call at execution time but are effectively lazy in that nothing appears to change right now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hiiiiii! -Kirby\n",
      "I'll be back! -The Terminator\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "84"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def greetings__I_am_close(func):\n",
    "    def inner(arg):\n",
    "        print(\"Hiiiiii! -Kirby\")\n",
    "        return func(arg)\n",
    "    return inner\n",
    "    \n",
    "def farewell__I_am_far(func):\n",
    "    def inner(arg):\n",
    "        results = func(arg)\n",
    "        print(\"I'll be back! -The Terminator\")\n",
    "        return results\n",
    "    return inner\n",
    "\n",
    "@farewell__I_am_far  # this wraps second\n",
    "@greetings__I_am_close  # this wraps the original function first\n",
    "def double(x):\n",
    "    return x * 2\n",
    "\n",
    "double(42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you have another question: what if you don't know the number of argments or argument names in ahead of time for the decorated function? That's where you use `*args` and `**kwargs`! This setup covers all cases.\n",
    "\n",
    "If you need a refresher on `*args` and `**kwargs`, you can take a look at `1_Pragmatic_Python.ipynb`. Basically, `*args` is for a variable (and indeterminate) number of positional arguments and `**kwargs` is for a variable (and indeterminate) number of keyword arguments. Depending on where `*args`/`**kwargs` are used, they can either separate out the arguments or gather them together. If they are used at function call time, then `*args` and `**kwargs` will separate your list/tuple or dictionary of arguments correctly into the function's arguments. If you are using them at function definition time, then they will gather your arguments into a tuple or dictionary.  \n",
    "Fun fact #1: `*args` is pronounced phonetically: star args. `**kwargs` is also phonetic: star star kwa-args.  \n",
    "Fun fact #2: `*args` is called splatting in other languages.\n",
    "\n",
    "Here's a simple of example of `*args for transposing a matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 4, 7), (2, 5, 8), (3, 6, 9)]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# *args at function call\n",
    "list(\n",
    "    zip(\n",
    "        *[  # convert 1 argument (1 big list) into 3 arguments (3 smaller lists)\n",
    "            [1, 2, 3],\n",
    "            [4, 5, 6],\n",
    "            [7, 8, 9]]\n",
    "    )\n",
    ")\n",
    "\n",
    "# logically equivalent to:\n",
    "# list(\n",
    "#     zip(\n",
    "#         [1, 2, 3],\n",
    "#         [4, 5, 6],\n",
    "#         [7, 8, 9],\n",
    "#     )\n",
    "# )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can use `*args` and `**kwargs` multiple times in the same function call."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 4, 7, 10), (2, 5, 8, 11), (3, 6, 9, 12)]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(\n",
    "    zip(\n",
    "        *[\n",
    "            [1, 2, 3],\n",
    "            [4, 5, 6],\n",
    "            [7, 8, 9]\n",
    "        ],\n",
    "        [10, 11, 12],\n",
    "    ),\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 4, 7, 10, 13, 16), (2, 5, 8, 11, 14, 17), (3, 6, 9, 12, 15, 18)]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(\n",
    "    zip(\n",
    "        *[\n",
    "            [1, 2, 3],\n",
    "            [4, 5, 6],\n",
    "            [7, 8, 9]\n",
    "        ],\n",
    "        *[\n",
    "            [10, 11, 12],\n",
    "            [13, 14, 15],\n",
    "            [16, 17, 18],\n",
    "        ]\n",
    "    ),\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you use `**kwargs`, the keys must be valid argument names, ie the keys must be strings that have no spaces."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': 1, 'b': 2, 'c': 3}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dict(**{\"a\": 1, \"b\": 2, \"c\": 3})\n",
    "\n",
    "# logically equivalent to:\n",
    "# dict(a=1, b=2, c=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Back to decorators: a decorator that does nothing special. Just an excuse to use `*` everywhere 🎉"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3\n",
      "5 4 3\n",
      "6 7 8\n",
      "11 12 10\n"
     ]
    }
   ],
   "source": [
    "def identity_decorator(func):  # does nothing special\n",
    "    def inner(*args, **kwargs):\n",
    "        return func(*args, **kwargs)\n",
    "    return inner\n",
    "\n",
    "@identity_decorator\n",
    "def silly_function(a, b, c=3):\n",
    "    print(a, b, c)\n",
    "    \n",
    "silly_function(1, 2)\n",
    "silly_function(a=5, b=4)\n",
    "silly_function(*(6, 7, 8))\n",
    "silly_function(**{\"c\": 10, \"a\": 11, \"b\": 12})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you may ask: what about the docstring of the decorated function? Won't the outputted function contain the decorator's docstring instead of the original decorated function's docstring? You are correct. That's why we use `functools.wraps()` decorator to extract the correct docstring from the decorated function and apply it to the outputted function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on function inner in module __main__:\n",
      "\n",
      "inner(*args, **kwargs)\n",
      "    Decorator that does nothing special\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def identity_decorator(func):\n",
    "    \"\"\"This docstring is totally lost after decorating a function\"\"\"\n",
    "    def inner(*args, **kwargs):\n",
    "        \"\"\"Decorator that does nothing special\"\"\"\n",
    "        return func(*args, **kwargs)\n",
    "    return inner\n",
    "\n",
    "@identity_decorator\n",
    "def double(arg):\n",
    "    \"Double the value\"  # this docstring is lost\n",
    "    return arg * 2\n",
    "\n",
    "\n",
    "help(double)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on function double in module __main__:\n",
      "\n",
      "double(arg)\n",
      "    Double the value\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from functools import wraps\n",
    "\n",
    "def identity_decorator(func):\n",
    "    \"\"\"This docstring is totally lost after decorating a function\"\"\"\n",
    "    @wraps(func)  # I decorate the inner function, so that I extract the original function's docstring and apply it to the returned inner() function\n",
    "    def inner(*args, **kwargs):\n",
    "        \"\"\"Decorator that does nothing special\"\"\"  # now this docstring is suppressed\n",
    "        return func(*args, **kwargs)\n",
    "    return inner\n",
    "\n",
    "@identity_decorator\n",
    "def double(arg):\n",
    "    \"Double the value\"  # now this docstring is kept\n",
    "    return arg * 2\n",
    "\n",
    "\n",
    "help(double)  # life is good!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you may have a question. Does decorators work on things outside of functions? YES! Decorators also works on classes or, in general, anything that is callable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Greetings, I come in peace --Never said by the Borg\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>a</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   a\n",
       "0  0\n",
       "1  1\n",
       "2  2\n",
       "3  3\n",
       "4  4"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Greetings, I come in peace --Never said by the Borg\n",
      "<__main__.A object at 0x000001A5DE3C9F10>\n"
     ]
    }
   ],
   "source": [
    "import pandas as pd\n",
    "\n",
    "def polite_class(cls):\n",
    "    def inner(*args, **kwargs):\n",
    "        print(\"Greetings, I come in peace --Never said by the Borg\")\n",
    "        instance = cls(*args, **kwargs)  # technically you don't need the save it; you can just\n",
    "        return instance #  return it if you don't do anything special after calling the class\n",
    "    return inner\n",
    "\n",
    "pd.DataFrame = polite_class(pd.DataFrame) # function decorating a class\n",
    "display(pd.DataFrame({\"a\": range(5)}))\n",
    "\n",
    "@polite_class\n",
    "class A:\n",
    "    pass\n",
    "\n",
    "print(A())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you may another question: can decorators take any arguments other than the target function? YES! Remember, a decorator itself is just a regular function. The only difference is that instead of taking input arguments of raw data and returning processed/outputted data, a decorator takes in function and return a \"processed/enhanced/augmented\" function. That is why it is called a decorator--it decorates the original function.\n",
    "\n",
    "The decorator example below is a simple to way to make Python enforce type on the arguments. You can think of it as making Python (pseudo) statically typed. It is not real static typing (because Python does not have a compilation step) and because the invalid argument types are only caught at runtime (when you call the function)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    },
    {
     "ename": "Exception",
     "evalue": "arg 10.0 is not of type <class 'int'>",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mException\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-17-eb547c79cd4b>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m     14\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     15\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mis_even\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;31m# prints True\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 16\u001b[1;33m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mis_even\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m10.0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;31m# raises Exception\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-17-eb547c79cd4b>\u001b[0m in \u001b[0;36minner\u001b[1;34m(arg)\u001b[0m\n\u001b[0;32m      5\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0marg\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m             \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 7\u001b[1;33m                 \u001b[1;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"arg {} is not of type {}\"\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0marg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mtype_\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      8\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0minner\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m     \u001b[1;32mreturn\u001b[0m \u001b[0mouter\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mException\u001b[0m: arg 10.0 is not of type <class 'int'>"
     ]
    }
   ],
   "source": [
    "def check_type(type_): # though \"type\" is not a reserved word, it is better to use a non-conflicting variable name\n",
    "    def outer(func): # Boo! Surprise! The decorator is really here\n",
    "        def inner(arg): # both`type_` and `func` are closed over by inner()\n",
    "            if isinstance(arg, type_):\n",
    "                return func(arg)\n",
    "            else:\n",
    "                raise Exception(\"arg {} is not of type {}\".format(arg, type_))\n",
    "        return inner\n",
    "    return outer\n",
    "                \n",
    "@check_type(int)\n",
    "def is_even(x):\n",
    "    return x % 2 == 0\n",
    "\n",
    "print(is_even(10)) # prints True\n",
    "print(is_even(10.0)) # raises Exception"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursion: Turtles All the Way Down\n",
    "Functional programming does not use explicit `for` or `while` loops--FP emulates them by using `map` and `filter`. However, some computations exceed the ability of only `map` and `filter`. And that's when recursion comes in. Recursive functions *call* themselves!\n",
    "\n",
    "Sometimes, you don't know how to solve a big problem, but you know how to solve a little problem. If you solve the little problem, then the bigger problem naturally gets solved. Recursion is solving through induction rather than a head-on, direct approach. (Look at all the math majors smiling 😍)\n",
    "\n",
    "In a recursive function, there are 2 cases: base case and recursive case.\n",
    "* **Base case**: when you have arrived at a fundamental stopping point because you solved the innermost, smallest problem such that the function no longer needs to call itself (non-recursive). You can have multiple base cases. Generally, you put the base case at the top of the function's body.\n",
    "* **Recursive case**: when you still have smaller problems to solve, so you call the function itself. Every call of the recursive case should get you closer to the base case. You can have multiple recursive cases. Generally, you put the recursive case at the bottom of the function's body.\n",
    "\n",
    "NOTE: Recursion and iteration(ie loops) are 2 different approaches to repetition, and both are Turing Complete. Hence, both are equally expressive: any recursion can be written as iteration and vice versa. Hence, FP and Procedural Python are equally expressive--it is a matter of your preference.\n",
    "\n",
    "Rather than any more academic explanations, let's go through the \"hello world\" example of recursion: factorial."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def factorial(n):\n",
    "    if n == 1:  # base case\n",
    "        return 1\n",
    "    else:  # recursive case\n",
    "        return n * factorial(n-1)\n",
    "\n",
    "# 1 liner equivalent if you're fancy\n",
    "# def factorial(n):\n",
    "#     return n * factorial(n-1) if n != 0 else 1\n",
    "\n",
    "factorial(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, there's a limitation in how deep you can recurse. The reason is that suppose you wrote your recursion wrong and it never hits the base case, then the function keeps call itself infinitely--I guess you can call FP's infinite recursion as analogous to procedural programming's infinite `while` loop (where the loop is always true and can never execute the loop). To guard against that, Python has a maximum call stack depth, which limits how many nested function calls you can do. The call stack is made out of a stack frames, one for each nested function call.\n",
    "\n",
    "![SegmentLocal](images/recursion_call_stack.gif \"segment\")\n",
    "Notice that the 1st function call is at the bottom and then the recursive calls builds the call stack **up**--you are stacking things up and the things that are being stacked are each function's call. Once your function hits the base case, the result is discovered, which passes result to the function call (the one before/below in the call stack) that created this stack frame. Thus, the call stack \"pops\" off the stack frame that is resolved, so the stack is decreasing. Once the stack frame hits the bottom, your 1st function call returns you the actual result.  \n",
    "Note: animation attributed to https://realpython.com/python-thinking-recursively/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "entering stack depth: 1\n",
      "entering stack depth: 2\n",
      "entering stack depth: 3\n",
      "entering stack depth: 4\n",
      "entering stack depth: 5\n",
      "exiting stack depth: 4\n",
      "exiting stack depth: 3\n",
      "exiting stack depth: 2\n",
      "exiting stack depth: 1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import inspect\n",
    "\n",
    "def factorial_with_stack_depth(n):\n",
    "    print(\"entering stack depth: {}\".format(len(inspect.stack()) - current_depth))\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        result = n * factorial_with_stack_depth(n-1)\n",
    "        print(\"exiting stack depth: {}\".format(len(inspect.stack()) - current_depth))\n",
    "        return result\n",
    "\n",
    "current_depth = len(inspect.stack())\n",
    "factorial_with_stack_depth(5)  # stack goes up and then down"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3000"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import sys\n",
    "\n",
    "sys.getrecursionlimit()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 8.01 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1999000"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "# using a simpler function for smaller printout as factorial(LARGE_NUMBER_HERE) returns a VERY_LARGER_NUMBER\n",
    "def range_summer(n):  # equivalent to sum(range(n))\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return range_summer(n-1) + n - 1\n",
    "\n",
    "range_summer(2000)  # super fast"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Despite the following code has a terminating point and is logically correct, Python fails and triggers `RecursionError` exception. When you exceed the call stack's limit (which, by default, is 3000), then you a *stack overflow*. Tada! As a pro, you now know the inside joke for the name of the most popular Q&A forum for programmers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded in comparison",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mRecursionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-5-2c47d1cdc982>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mrange_summer\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m4000\u001b[0m\u001b[1;33m)\u001b[0m  \u001b[1;31m# maximum depth exceeded\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<timed exec>\u001b[0m in \u001b[0;36mrange_summer\u001b[1;34m(n)\u001b[0m\n",
      "... last 1 frames repeated, from the frame below ...\n",
      "\u001b[1;32m<timed exec>\u001b[0m in \u001b[0;36mrange_summer\u001b[1;34m(n)\u001b[0m\n",
      "\u001b[1;31mRecursionError\u001b[0m: maximum recursion depth exceeded in comparison"
     ]
    }
   ],
   "source": [
    "range_summer(4000)  # maximum depth exceeded"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The solution to that is to either increase the maximum depth size or do something smarter. Increasing maximum depth size is very easy, so let's think of how to approach the problem in a smarter way.\n",
    "\n",
    "### Tail Call Optimization\n",
    "Tail call optimization (also called tail call elimination) is a way that FP languages \"beat\" the call stack by not creating another stack frame when the last function call is solely itself--the next call uses the existing stack frame. Often, tail call optimization uses an *accumulator* variable.\n",
    "\n",
    "BTW, Python does **not** have tail call optimization, so why am I telling you all this technobabble when Python doesn't even support it? Because I want to help you see the problem in another way such that the solution becomes tractable. Here's what `factorial()` would look like IF written in a tail call style."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def factorial_tco(n, accumulator=1):\n",
    "    if n == 1:  # base case\n",
    "        return accumulator\n",
    "    else:  # recursive case\n",
    "        return factorial_tco(n-1, accumulator=accumulator*n)  # the return only has a function call of itself\n",
    "        # The previous implementation `return n * factorial(n-1)` is not a tail call since it contains `n * ...`\n",
    "\n",
    "factorial_tco(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, tail call optimization syntax is really logically equivalent to a `while` loop. So let's write the Procedural Python equivalent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def factorial_loop(n):\n",
    "    accumulator = 1\n",
    "    while n:\n",
    "        accumulator *= n\n",
    "        n -= 1\n",
    "    return accumulator\n",
    "\n",
    "factorial_loop(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So basically... you taught Tail Call Optimization just to tell me to write a recursive function as a procedural function (with a loop)? What a cop out! I know 🙂. If you need to recurse very deeply, you will probably want to use a loop (or another optimization). If your recursion is only hundreds deep, then just use recursion if you feel like it.\n",
    "\n",
    "Let's take a look at another beginner recursive function: fibonacci. The next number in the sequence is the sum of the previous 2 numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fibonacci_plain(n):\n",
    "    if n == 1:  # base case 1\n",
    "        return 1\n",
    "    elif n == 2:  # base case 2: you can merge with base case 1 if you want\n",
    "        return 1\n",
    "    else:  # recursive case\n",
    "        return fibonacci_plain(n-1) + fibonacci_plain(n-2)\n",
    "\n",
    "# functionally equivalent 1 liner\n",
    "# def fibonacci(n):\n",
    "#     return fibonacci(n-1) + fibonacci(n-2) if n not in (1, 2) else 1\n",
    "\n",
    "fibonacci_plain(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's the tail call optimization version. Notice the accumulator variable. I find this version harder to understand."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fibonacci_tco(n, previous=1, current=1):\n",
    "    if n == 1 or n == 2:\n",
    "        return current\n",
    "    else:\n",
    "        return fibonacci_tco(n - 1, current, previous + current)\n",
    "\n",
    "fibonacci_tco(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's the procedural iterative version. Notice the accumulator variable. I find this version easier to understand."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fibonacci_loop(n):\n",
    "    if n == 1 or n == 2:\n",
    "        return 1\n",
    "    else:\n",
    "        previous, current = 1, 1\n",
    "        for i in range(n - 2):\n",
    "            previous, current = current, previous + current  # `current` is the accumulator variable\n",
    "    return current\n",
    "\n",
    "fibonacci_loop(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you are really fancy, you can go full circle and transform the iterative style back to FP style with `reduce()`. I would have never thought of this version naturally."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from functools import reduce\n",
    "\n",
    "n = 8\n",
    "reduce(lambda previous_current, _: (previous_current[1], sum(previous_current)), range(n-2), (1, 1))[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Everybody does fibonacci. Let's do the lesser known variant: tribonacci. The next number in the sequence is the sum of the previous 3 numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "44"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def tribonacci_plain(n):\n",
    "    if n == 1:  # base case 1\n",
    "        return 1\n",
    "    elif n == 2:  # base case 2\n",
    "        return 1\n",
    "    elif n == 3:  # base case 3\n",
    "        return 2\n",
    "    else: # recursive case\n",
    "        return tribonacci_plain(n-1) + tribonacci_plain(n-2) + tribonacci_plain(n-3)\n",
    "\n",
    "tribonacci_plain(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The iterative way is easier to understand."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "44"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def tribonacci_loop(n):\n",
    "    if n == 1 or n == 2:\n",
    "        return 1\n",
    "    elif n == 3:  # base case 3\n",
    "        return 2\n",
    "    else:\n",
    "        previous1, previous2, current = 1, 1, 2\n",
    "        for i in range(n - 3):\n",
    "            previous1, previous2, current = previous2, current, previous1 + previous2 + current\n",
    "        return current\n",
    "\n",
    "tribonacci_loop(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's try a more fun example: Collatz conjecture, which states that if you follow these 2 rules, you should always end up with the number 1.\n",
    "* If the number is even, divide it by two.\n",
    "* If the number is odd, triple it and add one.\n",
    "\n",
    "So let's use recursion to figure out how many steps it takes to reach 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 5, 16, 8, 4, 2, 1]\n",
      "[19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "def collatz(n, steps=None):  # steps is the accumulator\n",
    "    steps = steps if steps else []\n",
    "    steps += [n]\n",
    "    if n == 1:\n",
    "        return steps\n",
    "    else:\n",
    "        if n % 2: # odd: recursive case 1\n",
    "            return collatz(n * 3 + 1, steps=steps)\n",
    "        else: # even: recursive case 2\n",
    "            return collatz(n // 2, steps=steps)\n",
    "\n",
    "print(collatz(10))\n",
    "print(collatz(19))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just a reminder: FP's recursion is just another way to view procedural loops--the 2 styles form a duality, 2 sides of the same coin. It's up to you to decide which style you prefer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Academic Section: You Can Skip To the Next Section If You Like\n",
    "**Currying**, **Partial Functions**, and **Function Composition** are part of FP as they are higher-order functions, but I don't use them in real life. They are more for theoretical interest and perhaps more useful in other languages.\n",
    "\n",
    "### Currying: No, Not the Japanese Dish\n",
    "If a function has multiple arguments, currying is actually separating the arguments into separate function calls. It isn't exactly function decomposition, but it is decomposing a function by its arguments. You generally know the number of arguments of the target function when you are using currying. Currying is as exactly as expressive as the original function--ie no loss of expressiveness. A curried function is called by applying the arguments 1 by 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<function decomposer.<locals>.inner1.<locals>.inner2 at 0x000002E9589E45E0>\n",
      "<function decomposer.<locals>.inner1.<locals>.inner2.<locals>.inner3 at 0x000002E9589E4820>\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "def decomposer(func):\n",
    "    def inner1(a):\n",
    "        def inner2(b):\n",
    "            def inner3(c):\n",
    "                return func(a, b, c)\n",
    "            return inner3\n",
    "        return inner2\n",
    "    return inner1\n",
    "\n",
    "@decomposer\n",
    "def multiplier(x, y, z):\n",
    "    return x * y * z\n",
    "\n",
    "print(multiplier(1))  # function\n",
    "print(multiplier(1)(2))  # function\n",
    "print(multiplier(1)(2)(3))  # actual result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Partial Function Application: Impartially (or Rather Impatiently) Filling in the Blanks\n",
    "A partial function application freezes/hardcodes/fills in 1 or more arguments of the original function. The outputted function now requires fewer arguments to actually run. The goal to build more nuanced function(s) from a base/more general function. The outputted function is less expressive than the original function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x is 2; y = 5\n",
      "10\n",
      "x is 3; y = 5\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "from functools import partial\n",
    "\n",
    "def multiplier(x, y):\n",
    "    print(\"x is {}; y = {}\".format(x, y))\n",
    "    return x * y\n",
    "\n",
    "multiply_by_2 = partial(multiplier, 2)  # setting position arguments, equivalent to *args\n",
    "multiply_by_3 = partial(multiplier, 3)\n",
    "\n",
    "print(multiply_by_2(5))\n",
    "print(multiply_by_3(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x is 5; y = 2\n",
      "10\n",
      "x is 5; y = 3\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "# you can also set keyword arguments, equivalent to **kwargs\n",
    "multiply_by_2 = partial(multiplier, y=2)\n",
    "multiply_by_3 = partial(multiplier, y=3)\n",
    "\n",
    "print(multiply_by_2(5))\n",
    "print(multiply_by_3(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# here's a simple implementation of partial of filling 1 or multiple (positional or named) arguments\n",
    "def partial(func, *_args, **_kwargs):\n",
    "    if (not _args) and (not _kwargs):\n",
    "        raise Exception(\"No arguments filled\")\n",
    "    else:\n",
    "        def inner(*args, **kwargs):\n",
    "            kwargs.update(_kwargs)\n",
    "            return func(*_args, *args, **kwargs)\n",
    "    return inner\n",
    "\n",
    "def multiplier(x, y, z):\n",
    "    return x * y * z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "multiply_by_2 = partial(multiplier, 2)\n",
    "multiply_by_2(3, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "multiply_by_6 = partial(multiplier, 2, 3)\n",
    "multiply_by_6(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "multiply_by_12 = partial(multiplier, y=3, z=4)\n",
    "multiply_by_12(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "multiply_by_8 = partial(multiplier, 2, z=4)\n",
    "multiply_by_8(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function Composition: Build me a Skyscraper out of Lego Bricks\n",
    "The mathy part of FP. If you remember high school, you might have seen this funky notation: $(f∘g)(x)$, which just means $f(g(x))$. An alternative notation is $(f1 ∘ f2)(x) = f1(f2(gx))$. Notice that the order of the application of the functions; the closer function is applied first.\n",
    "\n",
    "Here's the syntax to give a quick idea:\n",
    "```python\n",
    "def h(f, g):  # h() is a higher-order function because it takes in 2 functions and returns a function\n",
    "    return lambda x: f(g(x))  # this specific example is called function composition\n",
    "```\n",
    "\n",
    "Suppose $f(x) = x + 5$ and $g(x) = 3x + 2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "133"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here's the procedural style\n",
    "def f(x):\n",
    "    return x + 5\n",
    "\n",
    "def g(x):\n",
    "    return 3*x + 2\n",
    "\n",
    "input_value = 42\n",
    "intermediate_value = g(input_value)\n",
    "final_value = f(intermediate_value)\n",
    "final_value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In FP, you can compose a higher-order function. Here are 2 options:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "133"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here's the decorator style\n",
    "def f(func):\n",
    "    def inner(input_value):\n",
    "        return func(input_value) + 5\n",
    "    return inner\n",
    "\n",
    "def g(x):  # same as above\n",
    "    return 3*x + 2\n",
    "\n",
    "h = f(g)\n",
    "input_value = 42\n",
    "final_value = h(input_value)\n",
    "final_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "133"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here's the compose function\n",
    "def compose(f, g):\n",
    "    return lambda x: f(g(x))\n",
    "\n",
    "def f(x):\n",
    "    return x + 5\n",
    "\n",
    "def g(x):\n",
    "    return 3*x + 2\n",
    "\n",
    "h = compose(f, g)\n",
    "input_value = 42\n",
    "final_value = h(input_value)\n",
    "final_value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose you want to chain together more than 2 functions, the compose style still works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "first 42\n",
      "second 1764\n",
      "third 5294\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5299"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here's the compose function on multiple functions\n",
    "def compose(f, g):\n",
    "    return lambda x: f(g(x))\n",
    "\n",
    "def f(x):\n",
    "    print(\"third\", x)\n",
    "    return x + 5\n",
    "\n",
    "def g(x):\n",
    "    print(\"second\", x)\n",
    "    return 3*x + 2\n",
    "\n",
    "def h(x):\n",
    "    print(\"first\", x)\n",
    "    return x * x\n",
    "\n",
    "i = compose(f, compose(g, h))\n",
    "input_value = 42\n",
    "final_value = i(input_value)\n",
    "final_value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And if you are a fancy pants 🧐, here's a magic trick ✨. It's just for fun. Don't think about it too hard--unless you want to. 😃"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "first 42\n",
      "second 1764\n",
      "third 5294\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5299"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Here's the generalized compose function (for multiple functions)\n",
    "from functools import reduce\n",
    "\n",
    "def compose(list_of_functions):\n",
    "    def inner(x):\n",
    "        return reduce(lambda value, func: func(value), reversed(list_of_functions), x)\n",
    "        # Notice how I am using reduce(). reduce() is usually used to apply 1 function\n",
    "        # to multiple pieces of data, but here I am applying 1 piece of data to multiple\n",
    "        # functions iteratively.\n",
    "    return inner\n",
    "\n",
    "i = compose([f, g, h])\n",
    "input_value = 42\n",
    "final_value = i(input_value)\n",
    "final_value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extra magic trick ✨: if I want to *reduce* (pun intended!) the function composition even further, here's a 1 liner. It is very confusing. Don't do this in the real world--it's just a proof of concept that Python is awesome! If you ~~want to hurt your brain~~ really like FP, then you can figure out what is the difference between this 1 liner vs the previous function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "first 42\n",
      "second 1764\n",
      "third 5294\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "5299"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(lambda f1, f2: lambda x: f1(f2(x)), [f, g, h])(42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python's Functions, Not Necessarily Functional Programming\n",
    "Let me explain some cool things about **Python's** functions that might not be strictly applicable to FP.\n",
    "\n",
    "### Functions are First Class\n",
    "When Python says that functions are first-class citizens, it means you can do (virtually) anything with functions. Functions are at the end of a day just another object. Functions can be used as an input argument and as a function output as seen in higher-order functions, decorators, currying, partial function application, etc.\n",
    "\n",
    "Python's function can be assigned, hashable, have their own attributes, and lots of other stuff."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "42\n"
     ]
    }
   ],
   "source": [
    "# Functions can also be assigned\n",
    "def func1():\n",
    "    return 42\n",
    "\n",
    "func2 = func1\n",
    "print(func1 is func2)\n",
    "print(func2())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-9223371875365723608\n",
      "{<function func1 at 0x0000025997F62288>: <function func1 at 0x0000025997F62288>}\n",
      "{<function func1 at 0x0000025997F62288>}\n"
     ]
    }
   ],
   "source": [
    "# Functions are hashable and thus can be the key (and value) of a dict or element of a set.\n",
    "# Basically functions can be stored in a data structure\n",
    "print(hash(func1))\n",
    "print({func1: func2}) # NOTE: FP does not use dictionaries. Why? Because dicts are mutable\n",
    "print(set([func1, func2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Functions can even have their own attributes. See 3_Object_Oriented_Python.ipynb: \"everything is an object\"\n",
    "# NOTE: FP, strictly speaking, probably does NOT allow functions to have attributes, as FP prefers closure instead.\n",
    "def factorial(n):\n",
    "    if not hasattr(factorial, \"accumulator\"):\n",
    "        factorial.accumulator = 1\n",
    "    if n == 1:\n",
    "        return factorial.accumulator\n",
    "    else:\n",
    "        factorial.accumulator *= n\n",
    "        return factorial(n - 1)\n",
    "\n",
    "factorial(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cache Advance: Function Remembers What it Did\n",
    "We can make things faster with a cache and thus improve runtime efficiency. But first, what is a cache? Is it money? No, it's even better--it's an optimization trick!\n",
    "\n",
    "A cache is just a place where you keep frequently-used data, so you can look it up quicky. For example, you can think of a sticky note with frequently asked questions and answers as a cache. In Python, a cache often uses a dictionary since it is very fast to see if a key exists in a dictionary--if so, get the value. If not, calculate the answer and update the dictionary. For example, a naive implementation of fibonacci has O(n^2) runtime complexity--it has quadratic runtime."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current number is 7\n",
      "current number is 6\n",
      "current number is 5\n",
      "current number is 4\n",
      "current number is 3\n",
      "current number is 2\n",
      "current number is 1\n",
      "current number is 2\n",
      "current number is 3\n",
      "current number is 2\n",
      "current number is 1\n",
      "current number is 4\n",
      "current number is 3\n",
      "current number is 2\n",
      "current number is 1\n",
      "current number is 2\n",
      "current number is 5\n",
      "current number is 4\n",
      "current number is 3\n",
      "current number is 2\n",
      "current number is 1\n",
      "current number is 2\n",
      "current number is 3\n",
      "current number is 2\n",
      "current number is 1\n",
      "Wall time: 2.51 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "import time\n",
    "\n",
    "def fibonacci_naive(num):\n",
    "    print(\"current number is {}\".format(num))\n",
    "    time.sleep(0.1)\n",
    "    if (num == 1) or (num == 2):\n",
    "        return 1\n",
    "    else:\n",
    "        return fibonacci_naive(num - 1) + fibonacci_naive(num - 2)\n",
    "\n",
    "\n",
    "fibonacci_naive(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A faster way is to use a cache to reuse already-computed results, so you don't have run unnecessary, duplicate computations. Since functions can have attributes, I am able to persist the results across function calls. Hence, I can reduce a naive recursion's O(n^2) runtime to a sophisticated recursion's O(n) runtime."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current number is 7\n",
      "current number is 6\n",
      "current number is 5\n",
      "current number is 4\n",
      "current number is 3\n",
      "current number is 2\n",
      "current number is 1\n",
      "I looked up the answer for 2\n",
      "I looked up the answer for 3\n",
      "I looked up the answer for 4\n",
      "I looked up the answer for 5\n",
      "Wall time: 705 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "import time\n",
    "\n",
    "def fibonacci_with_cache(num):\n",
    "    try:\n",
    "        if num in fibonacci_with_cache.cache:\n",
    "            print(\"I looked up the answer for {}\".format(num))\n",
    "            return fibonacci_with_cache.cache[num]\n",
    "    except AttributeError:\n",
    "        fibonacci_with_cache.cache = {}        \n",
    "    print(\"current number is {}\".format(num))\n",
    "    time.sleep(0.1)\n",
    "    if (num == 1) or (num == 2):\n",
    "        result = 1\n",
    "    else:\n",
    "        result = fibonacci_with_cache(num - 1) + fibonacci_with_cache(num - 2)\n",
    "    fibonacci_with_cache.cache[num] = result\n",
    "    return result\n",
    "\n",
    "\n",
    "fibonacci_with_cache(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current number is 7\n",
      "current number is 6\n",
      "current number is 5\n",
      "current number is 4\n",
      "current number is 3\n",
      "current number is 2\n",
      "current number is 1\n",
      "I looked up the answer for 2\n",
      "I looked up the answer for 3\n",
      "I looked up the answer for 4\n",
      "I looked up the answer for 5\n",
      "Wall time: 708 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "# a simple implementation of a cache to be used as a general-purpose decorator to apply\n",
    "def memoize(func):  # to any function, regardless if function is recursive or non-recursive\n",
    "    cache = {}\n",
    "    def inner(num):\n",
    "        if num not in cache:\n",
    "            cache[num] = func(num)\n",
    "        else:\n",
    "            print(\"I looked up the answer for {}\".format(num))\n",
    "        return cache[num]\n",
    "    return inner\n",
    "\n",
    "@memoize\n",
    "def fibonacci_memoized(num):\n",
    "    print(\"current number is {}\".format(num))\n",
    "    time.sleep(0.1)\n",
    "    if (num == 1) or (num == 2):\n",
    "        return 1\n",
    "    else:\n",
    "        return fibonacci_memoized(num - 1) + fibonacci_memoized(num - 2)\n",
    "\n",
    "fibonacci_memoized(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But why build our own cache? Python has batteries included! With `lru_cache()` (which stands for Least-Recently-Used cache), we can calculate fibonacci with O(n) linear runtime; same as before but with a lot less code. `lru_cache()` has an argument for `maxsize`--how big do you want your cache to be? If the cache has more elements than its `maxsize`, then pop off the least-recently used key-value pair. That way, your cache never grows too large.\n",
    "\n",
    "Decorators that have arguments (such as `lru_cache(maxsize)` are basically decorators within decorators. Nested decorators is how they are written: the outer decorator takes configuration(s) as arguments; the inner decorator takes in the target function as the argument.  \n",
    "Just a side note: caches are useful in a technique called **memo**ization--not a typo, not **memor**ization. Memoization + recursion = dynamic programming."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "current number is 7\n",
      "current number is 6\n",
      "current number is 5\n",
      "current number is 4\n",
      "current number is 3\n",
      "current number is 2\n",
      "current number is 1\n",
      "Wall time: 703 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "from functools import lru_cache\n",
    "\n",
    "@lru_cache(maxsize=128)  # decorator can take an argument for max size\n",
    "def fibonacci_memoized_simplified(num):\n",
    "    print(\"current number is {}\".format(num))\n",
    "    time.sleep(0.1)\n",
    "    if (num == 1) or (num == 2):\n",
    "        return 1\n",
    "    else:\n",
    "        return fibonacci_memoized_simplified(num-1) + fibonacci_memoized_simplified(num-2)\n",
    "\n",
    "fibonacci_memoized_simplified(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A cache is just something that remembers previous results, so it is debatable about whether memoization is considered true Functional Programming style since you are updating the cache. However, remember the 9th line of \"The Zen of Python\": practicality beats purity. Purity here does not refer to pure functions; rather it is the idea of not sticking to one programming paradigm dogmatically. Practicality refers to using the best tool for the problem. For example, sorting in a FP-style with pure functions would take a lot of memory and processing time. Sorting is more efficient in both memory and processing time by having a mutable data structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Zen of Python, by Tim Peters\n",
      "\n",
      "Beautiful is better than ugly.\n",
      "Explicit is better than implicit.\n",
      "Simple is better than complex.\n",
      "Complex is better than complicated.\n",
      "Flat is better than nested.\n",
      "Sparse is better than dense.\n",
      "Readability counts.\n",
      "Special cases aren't special enough to break the rules.\n",
      "Although practicality beats purity.\n",
      "Errors should never pass silently.\n",
      "Unless explicitly silenced.\n",
      "In the face of ambiguity, refuse the temptation to guess.\n",
      "There should be one-- and preferably only one --obvious way to do it.\n",
      "Although that way may not be obvious at first unless you're Dutch.\n",
      "Now is better than never.\n",
      "Although never is often better than *right* now.\n",
      "If the implementation is hard to explain, it's a bad idea.\n",
      "If the implementation is easy to explain, it may be a good idea.\n",
      "Namespaces are one honking great idea -- let's do more of those!\n"
     ]
    }
   ],
   "source": [
    "import this"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Functional Fusion: Combining FP with OOP and Procedural\n",
    "Sometimes, using pure FP style can be restricting. For example, UIs are hard to do in a purely FP style. Let's see how we can combine (or fuse) FP with other styles. The main use case for combining FP with other styles is high-performance Python (the next notebook!), which often uses method chaining and fluent interface. Dispatch is a nifty tool that you might see once in awhile. Infinite recursion depth is quite academic, so don't worry about it in real life.\n",
    "\n",
    "### Daisy Chaining: Functional Programming + Method Chaining/Fluent Interface (OOP syntax)\n",
    "Method chaining is **not** a FP style since method chaining belongs to OOP. However, let's take a look how method chaining simplifies the syntax for functional programming. `map(map(map(lambda ..., iterable), iterable), iterable)` looks ugly. Here's how we can separate the transformations onto sequential calls (on  separate lines) instead of nested calls in order to maximize readability. Like `|` in bash, treat iterables as a data pipeline where you are applying another transformation sequentially."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0    0\n",
       "1    2\n",
       "2    1\n",
       "3    0\n",
       "4    2\n",
       "5    1\n",
       "6    0\n",
       "7    2\n",
       "8    1\n",
       "9    0\n",
       "Name: col, dtype: int64"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# using pandas map() method, which is element-wise apply() and takes only 1 argument (which is the element)\n",
    "import pandas as pd\n",
    "df = pd.DataFrame({\"col\": range(10)})\n",
    "\n",
    "df[\"col\"].map(lambda x: x * 2).map(lambda x: x % 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0       0\n",
       "1     120\n",
       "2     240\n",
       "3     360\n",
       "4     480\n",
       "5     600\n",
       "6     720\n",
       "7     840\n",
       "8     960\n",
       "9    1080\n",
       "Name: col, dtype: int64"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# pandas pipe() method can take multiple arguments, more flexible than map()\n",
    "(\n",
    "    df[\"col\"]\n",
    "    .pipe(lambda x: x * 2)  # no extra arguments, equivalent to map/apply\n",
    "    .pipe(lambda x, y: x * y, 3)  # added a second argument, argument not named\n",
    "    .pipe(lambda x, y, z: x * y * z, 4, z=5)  # added (unnamed) second and (named) third argument\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>col</th>\n",
       "      <th>new_col1</th>\n",
       "      <th>new_col2</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0</td>\n",
       "      <td>4</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>0</td>\n",
       "      <td>6</td>\n",
       "      <td>9</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0</td>\n",
       "      <td>8</td>\n",
       "      <td>12</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>0</td>\n",
       "      <td>10</td>\n",
       "      <td>15</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>0</td>\n",
       "      <td>12</td>\n",
       "      <td>18</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>0</td>\n",
       "      <td>14</td>\n",
       "      <td>21</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>0</td>\n",
       "      <td>16</td>\n",
       "      <td>24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>0</td>\n",
       "      <td>18</td>\n",
       "      <td>27</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   col  new_col1  new_col2\n",
       "0    0         0         0\n",
       "1    0         2         3\n",
       "2    0         4         6\n",
       "3    0         6         9\n",
       "4    0         8        12\n",
       "5    0        10        15\n",
       "6    0        12        18\n",
       "7    0        14        21\n",
       "8    0        16        24\n",
       "9    0        18        27"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# create new columns in dataframe without mutating existing dataframe.\n",
    "# create new dataframe after each transform so like FP with pure function but use OOP syntax with method chaining\n",
    "(\n",
    "    df\n",
    "    .assign(new_col1=lambda self: self[\"col\"] * 2)  # create new column\n",
    "    .assign(new_col2=lambda self: self[\"col\"] * 3)  # create another new column based on the new column\n",
    "    .assign(col=lambda self: self[\"col\"] * 0)  # overwrite original column\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another library is `fluentpy` that gives you the expressiveness of FP but using the fluent interface. A fluent interface is a method that returns `self` after the method call. Basically you can chain a bunch of transformations together into 1 big expression instead of multiple statements (ie `temp1 = map(..., iterable); temp2 = filter(..., temp1); temp3 = reduce(..., temp3)`).  \n",
    "Fluentpy gives you:\n",
    "* the standard FP toolkit: `map`, `filter`, `reduce`\n",
    "* useful transformations: len, `max`, `min`, `sum`\n",
    "* other useful transformations: `enumerate`, `zip`, `groupby`, `accumulate`\n",
    "* and even things you wouldn't think of as chainable: `reversed`, `sorted`, `join`, `print`\n",
    "* plus even more!\n",
    "\n",
    "Use the multi-line style (which is common in Java), so you can clearly read/understand each transformation and optionally add a comment/note to each line. After awhile, you notice how useful this style and think: \"wow, I wish more things were like this!\" It's just like bash's pipe `|` but in Python--probably useful for creating a *data pipeline*...  \n",
    "Teaser: You mean like Spark 🤩 and Dask 😍? Fluentpy is not commonly used library 😢"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('DC', 'BA')"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import fluentpy as _  # install fluentpy if you aren't using mybinder.org\n",
    "\n",
    "_(\"ba,dc\").split(\",\").sorted(reverse=True).map(str.upper)._"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0->0', '1->20', '2->40', '3->60', '4->80', '5->100', '6->120', '7->140', '8->160']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'0->0, 1->20, 2->40, 3->60, 4->80, 5->100, 6->120, 7->140, 8->160'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(\n",
    "    _(range(50))\n",
    "    .map(_.each * 2)  # fluentpy-specific syntax\n",
    "    .map(lambda element: element * 2)  # standard map + lambda\n",
    "    .filter(_.each <= 170)\n",
    "    .filter(lambda element: element % 20 == 0)\n",
    "    .enumerate()\n",
    "    .map(lambda element: \"{}->{}\".format(element[0], element[1]))\n",
    "    .reduce(lambda x, y: \", \".join([x,y]))\n",
    "    .split(\", \")\n",
    "    .print()  # print returns None\n",
    "    .self  # so use `self` to get the underlying elements\n",
    "    .join(\", \")  # basically the same as the previous reduce\n",
    "    .unwrap\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dispatcher, Can You Get Me a Function? (FP + OOP)\n",
    "`singledispatch()` (and `singledispatchmethod()`) is a way to write multiple versions of the same function--do something different for different argument types. (Multiple) dispatch is called multimethod or method overloading in other languages. Dispatch looks like Procedural Python because it is a switch statement for functions. Dispatch also looks like Object-Oriented Python because that's how you emulate method overloading in Python. Dispatch also looks like functional style because it is a decorator. But `singledispatch()` is not a pure function because it is mutating a dictionary under the hood for every `register()` call.\n",
    "\n",
    "An example will help clarify how it works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This is an integer type\n",
      "This is a string type\n",
      "Unknown type\n"
     ]
    }
   ],
   "source": [
    "from functools import singledispatch\n",
    "\n",
    "@singledispatch\n",
    "def get_type(arg):  # fallback/default function\n",
    "    print(\"Unknown type\")\n",
    "\n",
    "@get_type.register(int)  # specifically for int type\n",
    "def _(arg):\n",
    "    print(\"This is an integer type\")\n",
    "\n",
    "@get_type.register(str)  # specifically for str type\n",
    "def _(arg):\n",
    "    print(\"This is a string type\")\n",
    "\n",
    "get_type(42)  # calls the int type version of the function\n",
    "get_type(\"42\")  # calls the string type version of the function\n",
    "get_type( (42,) )  # no tuple type version of function, go to fallback/default option"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "mappingproxy({object: <function __main__.get_type(arg)>,\n",
       "              int: <function __main__._(arg)>,\n",
       "              str: <function __main__._(arg)>})"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_type.registry  # this is a dictionary that gets updated every time you do get_type.register()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The reason that Python calls it `singledispatch` is that you can only do it on the *first* argument's type. If you want to make the function differ based on the 2nd argument (and so on), then you can probably chain a bunch of `singledispatch`s together. The easier solution is to use a 3rd party, pip installable library that supports *multiple* dispatch (which there are many).\n",
    "\n",
    "### Stack Skyscraper: Infinite Recursion Depth (FP + Procedural)\n",
    "If you combine FP with Procedural Python's exception handling, you can \"beat\" the recursion depth limit. In Python, you have a maximum stack depth to limit on how many nested function calls you can make. You can exceed this maximum limit by not going deep at all. What is this mysterious koan? I'll let the code do the talking."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def range_summer(n, accumulator=0):  # equivalent to sum(range(n))\n",
    "    if n == 0:\n",
    "        return accumulator\n",
    "    else:\n",
    "        return range_summer(n=n-1, accumulator=accumulator+n-1)  # written in a tail recursive style with accumulator\n",
    "\n",
    "range_summer(4000)  # exceed call stack limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7998000"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class StackCheater(Exception):\n",
    "    def __init__(self, *args, **kwargs):\n",
    "        self.args = args\n",
    "        self.kwargs = kwargs\n",
    "\n",
    "def tail_recursive(f):\n",
    "    def decorated(*args, **kwargs):\n",
    "        while True:\n",
    "            try:\n",
    "                return f(*args, **kwargs)\n",
    "            except StackCheater as sc:\n",
    "                args = sc.args\n",
    "                kwargs = sc.kwargs\n",
    "                continue\n",
    "    return decorated\n",
    "\n",
    "@tail_recursive\n",
    "def modified_range_summer(n, accumulator=0):\n",
    "    if n == 0:\n",
    "        return accumulator\n",
    "    else:\n",
    "        raise StackCheater(n=n-1, accumulator=accumulator+n-1)  # raise, not return\n",
    "\n",
    "modified_range_summer(4000)  # exceeds the default stack limit of 3000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The trick I used is `try/except` to break out of any deep function calls. In fact, the call is only 2 levels deep, and it is technically still recursion. Deep recursion with a shallow call stack.\n",
    "\n",
    "#### In Conclusion\n",
    "The overall purpose of showing `fluentpy` (which is not commonly used), `singledispatch`, and infinite recursion isn't really to show fandangled ways to do things. The primary purpose is to show you how to think outside of the box. Don't be ~~dogmatic~~ a purist. There's a philosophical concept of thesis, antithesis, synthesis.\n",
    "* *Thesis*: you come propose an idea.\n",
    "* *Antithesis*: somebody else proposes an idea that *seems* to contradict yours.\n",
    "* *Synthesis*: find a way that reconciles both ideas.\n",
    "\n",
    "For example, somebody says Procedural Python is the best. Somebody else says Functional Python is the best. A pro says: I can make something even better by fusing the two styles. In reality, the best solution for your problem is a mixture of different styles. That's what makes Python fun! 😎"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Extra Resources\n",
    "* `itertools` library: has a bunch of tools that can be useful for FP: product, permutations, combinations, etc. Actually useful.\n",
    "* `toolz` library: has even more useful tools under `functoolz` and `itertoolz` modules. Not commonly used.\n",
    "* https://realpython.com/primer-on-python-decorators/: A long and exhaustive guide on decorators.\n",
    "* https://www.destroyallsoftware.com/talks/boundaries and https://www.destroyallsoftware.com/screencasts/catalog/functional-core-imperative-shell: Gary Bernhardt (who created the technical talk series called \"Destroy all Software\") introduces the idea of functional core and imperative shell. The elementary piece of code should be pure functions, so it is easy to test and reason about. However, the larger \"infrastructure\" in a codebase needs to manipulates stdin/stdout, database, network, etc. Hence, the larger infrastructure can mutate things using imperative or OOP.\n",
    "* David Beazley - Lambda Calculus from the Ground Up - PyCon 2019 (https://www.youtube.com/watch?v=pkCLMl0e_0k): If you want to ~~hurt yourself~~ learn more about Lambda Calculus, this video aims to teach you how to build everything from scatch starting from (very) elementary pieces: \"No modules, no classes, no control flow, no data structures, and not even any primitives like integers or regular expressions. Just functions.\" It is also equally upfront with its disclaimer: \"You will learn nothing practically useful in this tutorial.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Concluding Remarks\n",
    "If you come from OOP, then closures in FP are a poor man's objects. If you come from FP, then objects/classes in OOP are a poor man's closure. In a way, you can think of decorators as the FP version of inheritance in OOP: you extend/modify/override the behavior of the original function. The point is not to select a universal programming paradigm that you apply to everything. If you are given a hammer, then everything looks like a nail. Always keep in mind the Golden Rule of programming: **use the best tool for the problem.** Select between OOP and FP (and other styles) depending on how you think is best to attack the problem. Perhaps a less eloquent and more blunt way of saying this is: don't hurt yourself. Don't contort yourself with the mental gymnastics of fitting the problem into a fixed style; incorporate multiple styles to address the problem.\n",
    "\n",
    "A rough rule of thumb is that data transformation *can be* more suited for FP design if  you don't need to remember (intermediate) state--in this case, it is more about the function purity. Things that need state or updates states (ike a UI design or database stuff) are more suited for OOP. OOP and FP are not polar opposites or mutually exclusive paradigms. A class's static method is like a compromise between FP and OOP. For example, a static method does not read or write the state of the instance (ie instance attributes) and is totally reliant on the inputted arguments. But a static method does not guarantee purity since it can still mutate a global variable. A static method uses OOP syntax because it is attached to a class.\n",
    "\n",
    "Sometimes you can fuse OOP and FP to get the best of both worlds; a practical use case is high-performance frameworks (Apache Spark, Apache Beam, Dask [dataframe, bag, array], Ray) and graph-based engines (TensorFlow, Airflow, Prefect, Dask [delayed]).  For example since `map` and `filter` should use pure functions, they are easily parallelizable operations.\n",
    "\n",
    "Highly parallelizable operations are ones where a transformation on 1 element is not dependent on another element and thus are called **Embarrassingly Parallel** problems. For example, word count is an example of a (mostly) embarrassingly parallel problem since you can count the words on different pages of a book using different processes (embarrassingly parallel) and then add up the intermediate results (not embarrassingly parallel) at the end to get the final answer. Guess what the next section is on? High-performance Python! ⚡"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}