06_map_filter_reduce_lambdas/map_filter_reduce_lambdas.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# map, filter, reduce a anonymní funkce"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dnes se společně podíváme na trojici velmi užitečných funkcí, které tvoří základ funkcionálního programování, a dojde i na funkce anonymní, které jsou ve FP také velmi hojně využívané.\n",
    "\n",
    "`map`, `filter` a `reduce` jsou příklady tzv. funkcí vyššího řádu. Funkce vyššího řádu jsou takové funkce, které umí přijímat jiné funkce jako své argumenty nebo vytvářet funkce nové a vracet je jako svou návratovou hodnotu. V této lekci je budeme používat a příště se je naučíme vytvářet a povíme si také více o funkcionálním programování."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## map"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`map` je funkce, která umí aplikovat jinou zadanou funkci na všechny prvky sekvence. Ukažme si to na jednoduchém příkladu. Chceme opravit velká písmena u jmen a příjmení našich uživatelů."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nejdříve si definujeme samostatnou funkci, která nám bude umět velká písmena opravit:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def oprav_velka_pismena(jmeno_prijmeni):\n",
    "    jmeno, prijmeni = jmeno_prijmeni.split()\n",
    "    jmeno = jmeno.capitalize()\n",
    "    prijmeni = prijmeni.capitalize()\n",
    "    return f\"{jmeno} {prijmeni}\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Použití takové funkce na sekvencí v cyklu by mohlo vypadat například takto:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Pepa Novak', 'Karel Novotny', 'Tomas Piskal', 'Jakub Novy']\n"
     ]
    }
   ],
   "source": [
    "jmena = [\"pepa novak\", \"Karel Novotny\", \"tomas Piskal\", \"jAKUB novy\"]\n",
    "opravena_jmena = []\n",
    "\n",
    "for jmeno in jmena:\n",
    "    opravena_jmena.append(oprav_velka_pismena(jmeno))\n",
    "   \n",
    "print(opravena_jmena)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`map` umí zajistit stejný výsledek aplikací funkce na všechny prvky sekvence. `map` navíc nevrací seznam nových prvků, ale iterovatelný objekt, který šetří pamět a dává prvky k dispozici až ve chvíli, kdy si o ně řekneme. Výsledek `map` tak můžeme použít v cyklu nebo, pokud opravdu potrebujeme seznam, jej na seznam konvertovat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['Pepa Novak', 'Karel Novotny', 'Tomas Piskal', 'Jakub Novy']\n"
     ]
    }
   ],
   "source": [
    "jmena = [\"pepa novak\", \"Karel Novotny\", \"tomas Piskal\", \"jAKUB novy\"]\n",
    "\n",
    "opravena_jmena = list(map(oprav_velka_pismena, jmena))\n",
    "   \n",
    "print(opravena_jmena)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## filter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zatímco funkce `map` vytvořila nové prvky aplikací funkce na prvky z původní sekvence, funkce `filter` provede jejich filtraci na základě návratové hodnoty (`True`/`False`) ze zadané funkce.\n",
    "\n",
    "Opět využijeme jednoduchý příklad a získáme ze seznamu jen sudá čísla. Nejprve si definujeme funkci, která vrátí `True` pokud je číslo sudé."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def je_sude(cislo):\n",
    "    return cislo % 2 == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Klasické a nejupovídanější řešení pomocí cyklu:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 8, 10]\n"
     ]
    }
   ],
   "source": [
    "cisla = [1, 2, 4, 5, 6, 8, 9, 10, 11]\n",
    "suda_cisla = []\n",
    "\n",
    "for cislo in cisla:\n",
    "    if je_sude(cislo):\n",
    "        suda_cisla.append(cislo)\n",
    "\n",
    "print(suda_cisla)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Další možností je využít nám již dobře známé list comprehensions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 8, 10]\n"
     ]
    }
   ],
   "source": [
    "cisla = [1, 2, 4, 5, 6, 8, 9, 10, 11]\n",
    "suda_cisla = [cislo for cislo in cisla if je_sude(cislo)]\n",
    "\n",
    "print(suda_cisla)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A nově i s pomocí funkce `filter`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 8, 10]\n"
     ]
    }
   ],
   "source": [
    "cisla = [1, 2, 4, 5, 6, 8, 9, 10, 11]\n",
    "\n",
    "suda_cisla = list(filter(je_sude, cisla))\n",
    "\n",
    "print(suda_cisla)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## reduce"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Poslední z trojice dnes jmenovaných bude funkce `reduce`. Ta vezme funkci akceptující dva parametry a postupně ji aplikuje na prvky sekvence, zleva doprava. Výsledek předchozí aplikace se vždy použije jako první parametr funkce a jako druhý parametr se použije další nezpracovaný prvek sekvence. Takto postupuje dokud nezredukuje sekvenci na jednu výslednou hodnotu.\n",
    "\n",
    "Funkce `reduce` není, narozdíl od ostatních dnes jmenovaných, automaticky dostupná a musí se importovat z modulu `functools`.\n",
    "\n",
    "Na první pohled složitý slovní popis skrývá jednoduchý princip s řadou možností. Pojďme například vynásobit čísla v sekvenci.\n",
    "\n",
    "Opět začneme funkcí pro násobení:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nasobeni(x, y):\n",
    "    return x * y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Následuje příklad s využitím cyklu:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24\n"
     ]
    }
   ],
   "source": [
    "cisla = [1, 2, 3, 4]\n",
    "vysledek = 1\n",
    "\n",
    "for cislo in cisla:\n",
    "    vysledek = vysledek * cislo\n",
    "    \n",
    "print(vysledek)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A nyní s využitím `reduce`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "\n",
    "cisla = [1, 2, 3, 4]\n",
    "\n",
    "vysledek = reduce(nasobeni, cisla)\n",
    "    \n",
    "print(vysledek)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Anonymní funkce (tzv. lambdy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`map`, `filter` či `reduce` potřebují dostat jako první argument funkci, kterou pak budou používat. Některé funkce (například naše `nasobeni` a `je_sude`) jsou ale tak jednoduché, že by se jejich definice dala s nadsázkou označit za plýtvání místem. Pro takové situace existují tzv. anonymní funkce, které lze pomocí klíčového slova `lambda` definovat jen na jednom řádku a bez přiřazení jména.\n",
    "\n",
    "Například `nasobeni` by se dalo zapsat takto:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function __main__.<lambda>(x, y)>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lambda x, y: x * y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Definice anonymní funkce začíná klíčovým slovem `lambda` a pokračuje seznamem argumentů, které jsou klasicky oddelěné čárkou. Za argumenty pak následuje dvojtečka a za ní výraz, který se má vyhodnotit a jehož výsledek se vrátí jako návratová hodnota.\n",
    "\n",
    "S takto definovanou anonymní funkcí se toho ale moc dělat nedá, protože je anonymní a nemáme tak možnost ji jinde v programu použít.\n",
    "\n",
    "Mohli bychom si ji samozřejmě přiřadit do proměnné a následně ji volat jménem, ale to už bychom si klidně mohli definovat klasickou funkci. Daleko lepší použití se nabízí v kombinaci s funkcemi, které berou jiné funkce jako vstupní argumenty. Například právě `map`, `filter` nebo `reduce`. Pojďme si ukázat dva poslední příklady s využitím anonymních funkcí:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "\n",
    "cisla = [1, 2, 3, 4]\n",
    "\n",
    "vysledek = reduce(lambda x, y: x * y, cisla)\n",
    "    \n",
    "print(vysledek)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Příklad se od původního téměř neliší. Hlavní rozdíl je v tom, že jsme si pro jednoduchou matematickou operaci násobení nemuseli definovat klasickou pojmenovanou funkci, která by nám zabrala minimálně dva řádky. Místo toho jsme využili anonymní funkci a její definici napsali přímo jako argument funkce `reduce`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4, 6, 8, 10]\n"
     ]
    }
   ],
   "source": [
    "cisla = [1, 2, 4, 5, 6, 8, 9, 10, 11]\n",
    "\n",
    "suda_cisla = list(filter(lambda cislo: cislo % 2 == 0, cisla))\n",
    "\n",
    "print(suda_cisla)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tady je situace stejná. Rozdíl je jen v tom, že anonymní funkce bere jen jediný argument a protože výraz k vyhodnocení je porovnáním, výsledkem bude vždy `True` nebo `False`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Anonymní funkce mohou být velice užitečné v případech, kdy je definice klasické funkce opravdu zbytečná. Na druhou stranu mohou snižovat čitelnost kódu, hůře se dokumentují, mají řadu technických omezení atp. Jejich používání je tedy vždy nutné dobře rozmyslet."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MapReduce"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MapReduce je programovací model, který využívá právě kombinaci funkcí `map` a `reduce`. I když se tyto funkce zdají být jednoduché, jejich možnosti použití jsou velmi široké a celá řada algoritmů lze implementovat tak, aby využily právě jen tyto funkce. MapReduce se navíc využívá v paralelním prostředí, kde jeden požadavek může najednou zpracovávat i několik stovek počítačů. Toho se nejčastěji využívá při zpracování velkého množství dat a jejich řazení, indexaci, vyhledávání atp. S pouhou definicí mapovací a redukční funkce se tak dají provádět komplexní operace nad velkými daty.\n",
    "\n",
    "Pojďmě si to ukázat na příkladu s výpočtem výskytu slov v dokumentech:\n",
    "1. Nejdříve je třeba připravit data. Pokud máme jen jeden zdroj, je třeba jej rozdělit na části, abychom je mohli zpracovávat paralelně.\n",
    "2. Pak přichází na řadu mapovací fáze, která zpracuje data do dvojic klíč/hodnota. V našem případě bude klíčem slovo a hodnotou jeho výskyt napříč dokumenty.\n",
    "3. Protože klíče po mapování nejsou unikátní (jedno slovo bude určitě ve více dokumentech a bude zpracováno na jiném serveru) je potřeba po mapování přesunout stejné klíče k sobě.\n",
    "4. Následně přichází na řadu redukční fáze, která provádí nad daty výpočet. V našem případě sečte všechny hodnoty pro daný klíč dohromady a tím získáme celkový počet výskytů slova napříč dokumenty.\n",
    "5. Protože se i fáze redukce provádí paralelně, je třeba na konci ještě dílčí výsledky spojit do jednoho a získat tak kompletní přehled.\n",
    "\n",
    "V jednoduchosti celý proces demonstruje následující obrázek:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![MapReduce](https://dzone.com/storage/temp/1329325-111.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Úkol"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vymyslete reálný příklad, ve kterém využijete alespoň dvě ze tří dnes zmíněných funkcí případně model MapReduce.\n",
    "\n",
    "Řešení a případné dotazy zasílejte na email frenzy.madness@gmail.com"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}