p1/dodatna predavanja/07 map, filter in reduce.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dva, trije strici iz ozadja\n",
    "\n",
    "Python ni imel izpeljanih seznamov od vedno. Dobil jih je, ko je imel okrog 9 let, večine študentov pa še ni bilo med nami. Z verzijo 2.0, leta 2000.\n",
    "\n",
    "Predtem sta tej sceni vladali dve funkciji: `map` in `filter`.\n",
    "\n",
    "## Map\n",
    "\n",
    "Funkcija `map` kot argument prejme funkcijo in nekaj, prek česar je možno nagnati zanko. Vsak element tega, nečesa, \"premapira\" čez funkcijo. Če imamo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import sqrt\n",
    "\n",
    "k = [9, 25, 16, 81]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "bo `map(sqrt, k)` vrnil korene vseh števil v `k`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in map(sqrt, k):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Funkcija `map` dela, približno tole:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def map(func, s):\n",
    "    t = []\n",
    "    for x in s:\n",
    "        t.append(func(x))\n",
    "    return t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do Pythona 3.0 je funkcija `map` v resnici vračala seznam, od različica 3.0 naprej pa vrne *iterator*. Za tiste, ki ne veste, kaj je to: vede se kot seznam, samo da ni; čezenj lahko gremo z zanko `for`. Za tiste, ki ne veste, pa bi radi izvedeli: preberite zapiske o generatorjih in iteratorjih. Za tiste, ki veste: ja, takšen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def map(func, s):\n",
    "    for x in s:\n",
    "        yield func(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Funkcijo `map` od Pythona 2.0 naprej uporabljamo zelo redko. `map(func, s)` je isto kot `(func(x) for x in s)`. Prednost novejše različice je v tem, da\n",
    "\n",
    "- ne zahteva funkcije, temveč izraz; generatorja `(x ** 2 for x in s)` ne moremo prepisati v `map(**2, s)`, temveč potrebujemo lambdo: `map(lambda x: x ** 2, s)`;\n",
    "- je `map` počasnejši, ker vedno kliče funkcijo, medtem ko je novejši zapis, generator, ne (vsak, dokler lahko vse opravimo z izrazom).\n",
    "\n",
    "Osebno `map` rad uporabim, kadar imam funkcijo ravno pri roki in kadar izgleda sintaktično lepše.\n",
    "\n",
    "Se pravi: redko.\n",
    "\n",
    "## Filter\n",
    "\n",
    "Funkcija `filter` je druga funkcija, ki so jo izpeljani seznami spravili ob delo. `filter(func, s)` vrne vse tiste elemente `s`, pri katerih `func` vrne `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vsebuje_i(s):\n",
    "    return \"i\" in s\n",
    "\n",
    "imena = [\"Ana\", \"Berta\", \"Cilka\", \"Dani\", \"Ema\"]\n",
    "\n",
    "for x in filter(vsebuje_i, imena):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To je seveda isto kot `(x for x in imena if vsebuje_i(x))`, kar je tako ali tako le bolj zapletena različica `(x for x in imena if \"i\" in x)`. Resnici na ljubo tudi `filter` ne potrebuje poprej definirane funkcije, saj bi lahko pisali `filter(lambda x: \"i\" in x, imena)`. Vendar je očitno, zakaj filtra ne vidimo več velikokrat.\n",
    "\n",
    "Izpeljani seznami, slovarji, množice in generatorji v enem zamahu naredijo oboje, mapirajo in filtrirajo.\n",
    "\n",
    "## Reduce\n",
    "\n",
    "Funkcija `reduce` je edina iz te družbe, ki ni ostala brezposelna. No, hkrati pa tudi najmanj uporabna od njih, saj Python ni ravno jezik za te hece. Mogoče je tudi to razlog, da jo dobimo v modulu `functools` in ne kar tako, na prostem.\n",
    "\n",
    "`reduce(func, s)` je nekako ekvivalenten temu `func(func(func(func(s[0], s[1])), s[2]), s[3]), s[4])` - če je `s` seznam s petimi elementi. Ali, v kodi (ki sicer ne zna vsega, kar zna `reduce`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reduce(func, s):\n",
    "    acc = s[0]\n",
    "    for x in s[1:]:\n",
    "        acc = func(acc, x)\n",
    "    return acc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Po domače: `reduce` pokliče funkcijo na prvih dveh elementih, nato na rezultatu tega klica in tretjem elementu, nato na rezultatu tega klica in četrtem elementu... Spremenljivko `acc` pa smo poimenovali po njeni vlogi: akumulator.\n",
    "\n",
    "Če vemo, kaj so iteratorji in kaj počne `next`, znamo bolj natančno (če ne, pa nič narobe, tudi gornje je dovolj dobro za razumevanje, ki ga potrebujemo za uporabo funkcije):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reduce(func, s, acc=None):\n",
    "    t = iter(s)\n",
    "    if acc is None:\n",
    "        acc = next(t)\n",
    "        \n",
    "    for x in t:\n",
    "        acc = func(acc, x)\n",
    "    return acc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Z `reduce` se da početi zanimive stvari. Pripravimo si nekaj funkcij (ki bi lahko bile tudi lambde, ampak recimo, da jih ne znamo pisati)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sestej(a, b):\n",
    "    return a + b\n",
    "\n",
    "def zmnozi(a, b):\n",
    "    return a * b\n",
    "\n",
    "def vrni_vecjega(a, b):\n",
    "    if a > b:\n",
    "        return a\n",
    "    else:\n",
    "        return b\n",
    "    \n",
    "def oba_resnicna(a, b):\n",
    "    return a and b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pripravimo si še priložnostni seznam števil."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = [4, 2, 6, 3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Z `reduce` lahko zdaj izračunamo vsoto elementov seznama"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(sestej, s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "produkt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "144"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(zmnozi, s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "in poiščemo največji element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(vrni_vecjega, s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "mimogrede pa še 10!, se pravi produkt števil do 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3628800"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(zmnozi, range(1, 11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Če imamo seznam `True`-jev in `False`-ov, lahko z `reduce` izračunamo njegovo konjunkcijo (`and` prek vseh elementov`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(oba_resnicna, [True, True, True, True, True])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reduce(oba_resnicna, [True, True, True, False, True])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imenitna reč, problem je le, da se nam teh funkcij ne da definirati vnaprej, Pythonove lambde, s katerimi lahko funkcijo definiramo kar sproti, znotraj klica `reduce`, pa so zelo kilave in tudi nikoli ne bodo drugačne kot kilave.\n",
    "\n",
    "## Ozadje stricev iz ozadja\n",
    "\n",
    "Funkcije `map`, `filter` in `reduce` - pri čemer se slednja v drugih jezikih bolj pogosto kot ne imenuje `fold` - so osnovni elementi [funkcijskega programiranja](https://en.wikipedia.org/wiki/Functional_programming)."
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}