Rekurzia a funkcionálne programovanie

Funkcia v Pythone

blok kódu, ktorý vykonáva určitú úlohu a môže byť volaný z iných častí programu.
objekt, ktorý môže byť uložený do premennej, odovzdaný ako argument alebo vrátený z inej funkcie.
funkcia môže mať predvolené hodnoty argumentov

def ahoj(name="Daniel"):
    return f"Ahoj, {name}!"

pozdrav = ahoj
print(pozdrav())  # "Ahoj, Daniel!"
print(pozdrav("Svet"))  # "Ahoj, Svet!"

📚 Oficiálny manuál: definovanie funkcií

📖 Dive Into Python 3: Your First Python Program

Funkcie sú objekty

V Pythone sú funkcie plnohodnotné objekty, čo znamená:

môžeš ich uložiť do premennej
môžeš ich posielať ako argument
funkcia môže byť návratovou hodnotou inej funkcie

📚 Oficiálny manuál: používateľom definované funkcie

📖 Dive Into Python 3: Everything Is An Object

Funkcia môže obsahovať typové anotácie a dokumentačné reťazce

def add(a: int, b: int) -> int:
    """Vráti súčet dvoch čísel."""
    return a + b

📚 Oficiálny manuál: dokumentačné reťazce a typové anotácie

📖 Dive Into Python 3: Documentation Strings

Testy v dokumentácii funkcie:

Dokumentačný reťazec môže obsahovať aj príklady použitia, ktoré sú zároveň testovateľné pomocou modulu doctest.

def add(a: int, b: int) -> int:
    """Vráti súčet dvoch čísel.

    >>> add(2, 3)
    5
    >>> add(-1, 1)
    0
    """
    return a + b

📚 Oficiálny manuál: modul doctest

📖 Dive Into Python 3: Unit testing

Lambda funkcie

Funkciu je možné uložiť do premennej, alebo odobzdať ako hodnotu

Lambda = anonymná (krátka) funkcia

square = lambda x: x * x
print(square(4))

📚 Oficiálny manuál: lambda výrazy

Triedenie pomocou lambda funkcie

Pomocou sorted a lambda je možné triediť zoznamy slovníkov podľa kľúča. Lambda vyjadruje spôsob ako získať hodnotu, podľa ktorej sa má triediť.

data = [
    {"name": "Alice", "age": 30},
    {"name": "Bob", "age": 25},
    {"name": "Charlie", "age": 35},
]

sorted_data = sorted(data, key=lambda x: x["age"])
# sorted je generátor

📚 Oficiálny manuál: techniky triedenia

📖 Dive Into Python 3: sorted() a kľúčová funkcia

Generátor

používa sa na vytvorenie postupností na požiadavku
produkuje hodnoty postupne pomocou slovíčka yield

def generate_numbers(n):
    for i in range(n):
        yield i * 2

for number in generate_numbers(10):
    print(number)

📚 Oficiálny manuál: generátory

📖 Dive Into Python 3: Closures & Generators

Rekurzia

Rekurzia znamená, že funkcia volá samu seba.

Používa sa pri problémoch, ktoré sa dajú rozdeliť na menší problém rovnakého typu:

faktoriál,
prechádzanie stromu,
spracovanie vnorených štruktúr,
spätné prehľadávanie.

Rekurzívne prechádzanie zoznamu

def sum_list(items):
    if not items:
        return 0
    return items[0] + sum_list(items[1:])

print(sum_list([1, 2, 3, 4]))

Výsledok:

Dve časti rekurzie

Každá rekurzívna funkcia potrebuje:

podmienku ukončenia – prípad, ktorý už nevolá ďalšiu rekurziu,
rekurzívny krok – volanie tej istej funkcie s menším alebo jednoduchším vstupom.

def factorial(n):
    if n == 0:          # podmienka ukončenia
        return 1
    return n * factorial(n - 1)  # rekurzívny krok

Priebeh výpočtu

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1 * factorial(0)
= 4 * 3 * 2 * 1 * 1
= 24

Najprv sa volania skladajú na zásobník, potom sa výsledky postupne vracajú späť.

Rekurzia namiesto cyklu

Namiesto opakovania pomocou cyklu môžeme problém zmenšovať pomocou volania tej istej funkcie.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Čo je funkcionálne programovanie?

Funkcionálne programovanie (FP) je štýl programovania, kde:

funkcie sú hlavné stavebné bloky
vyhýbame sa meneniu dát (nemeniteľnosť), snažíme sa nemať vedľajšie efekty (napr. meniť globálne premenné)

📚 Oficiálny manuál: Functional Programming HOWTO

📖 Dive Into Python 3: Closures & Generators

Čisté funkcie

vždy vráti rovnaký výsledok pre rovnaký vstup
nemá vedľajšie efekty

         +---------+
vstup -> | funkcia | -> výstup
         +---------+

Čisté funkcie nemajú vedľajšie efekty

stav 1 je vstup -> funkcia -> výstup je stav 2

menej chýb spôsobených zmenou stavu
jednoduchšie testovanie a ladenie
ľahšia paralelizácia a distribuované spracovanie

def add(a, b):
    return a + b

Funkcia s vedľajším efektom

            stav
            ^   |
            |   v
         +---------+
vstup -> | funkcia | -> výstup
         +---------+
              |
              v
          vedľajší efekt

Funkcia s vedľajším efektom zmení stav sveta okolo seba (terminál, súbor, sieť, pamäť...)

Dve zavolania takej funkcie môžu mať dva rôzne výsledky

total = 0

def add(a):
    global total
    print("Ahoj Svet")
    total += a

Testovanie čistých funkcií

nepotrebujú globálny stav,
nemenia okolie programu,
rovnaký vstup vždy dá rovnaký výstup.

def add(a, b):
    return a + b

assert add(2, 3) == 5

📖 Dive Into Python 3: Unit testing

Funkcie vyššieho rádu

Funkcia, ktorá:

berie inú funkciu ako argument
alebo ju vracia

def apply_function(f, x):
    return f(x)

print(apply_function(lambda x: x * 2, 5))

📚 Oficiálny manuál: Functional Programming HOWTO 📖 Dive Into Python 3: A List Of Functions

Funkcie vyššieho rádu pre spracovanie zoznamov

map
filter
reduce

+-----------------+     +---------+   +-----------------+
| vstupný zoznam  |  →  | funkcia | → | výstupný zoznam |
+-----------------+     +---------+   +-----------------+

map()

Zoznam vstupov vytvorí zoznam výstupov podľa zadanej funkcie.

numbers = [1, 2, 3]
result = list(map(lambda x: x * 2, numbers))

📚 Oficiálny manuál: map()

📖 Dive Into Python 3: List Comprehensions

🔵 filter()

Podľa zadanej funkcie vyberie zoznam vstupov, ktoré spĺňajú podmienku.

numbers = [1, 2, 3, 4]
result = list(filter(lambda x: x % 2 == 0, numbers))

📚 Oficiálny manuál: filter()

📖 Dive Into Python 3: List Comprehensions

🔴 reduce() – redukuje na jednu hodnotu

reduce

+---------+    +---------+   +--------+
| zoznam  | →  | funkcia | → |hodnota |
+---------+    +---------+   +--------+

Funkcia má dva operandy. Prvý operand je akumulátor, druhý je aktuálny prvok zoznamu. Výsledok sa stáva novým akumulátorom.

akumlátor = f(akumulátor, prvok)

📚 Oficiálny manuál: functools.reduce()

Príklad: súčet zoznamu pomocu reduce

from functools import reduce

numbers = [1, 2, 3, 4]
result = reduce(lambda x, y: x + y, numbers)

📚 Oficiálny manuál: functools.reduce()

Odvodenie zoznamu - list comprehension

Python má elegantnejšiu alternatívu k map a filter:

numbers = [1, 2, 3, 4]

result = [x * 2 for x in numbers if x % 2 == 0]

📚 Oficiálny manuál: list comprehensions

📖 Dive Into Python 3: Comprehensions

Uzáver - Closure

Uzáver zostaví funkciu na požiadanie podľa zadaných parametrov.

def multiplier(n):
    def multiply(x):
        return x * n
    return multiply

double = multiplier(2)

print(double(5))

📚 Oficiálny manuál: definovanie funkcií a uzávery

📖 Dive Into Python 3: Closures & Generators

Dekorátory sú funkcie vyšieho rádu

Dekorátor je funkcia, ktorá:

berie funkciu ako argument,
vracia novú funkciu (uzáver) s pridanou logikou.

import time

def meraj_cas(f):
    def obalka(*args, **kwargs):
        start = time.perf_counter()
        result = f(*args, **kwargs)
        end = time.perf_counter()
        print(f"{f.__name__}: {end - start:.4f}s")
        return result
    return obalka

@mer_cas
def pomaly_vypocet():
    total = sum(i ** 2 for i in range(10_000_000))
    return total

pomalý_výpočet()
# pomalý_výpočet: 2.1342s

📚 Oficiálny manuál: dekorátory

Cache pre fukcie s `@lru_cache`

Systém si zapamätá výsledky funkcie pre rovnaké vstupy, takže sa nemusí opakovane počítať.

Funkcia by mala byť čistá (bez vedľajších efektov), aby sa dala bezpečne cache-ovať.

Urýchľuje rekurziu

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))     # 12586269025  — okamžite (niekoľko ms)
                       # bez @lru_cache by trvalo minúty

📚 Oficiálny manuál: functools.lru_cache

Dekorátor s parametrami

Parametre cez dvojitý uzáver:

def opakovane(n):
    def decorator(f):
        def obalka(*args, **kwargs):
            for _ in range(n):
                result = f(*args, **kwargs)
            return result
        return obalka
    return decorator

@opakovane(3)
def ahoj():
    print("Ahoj")

ahoj()
# Ahoj
# Ahoj
# Ahoj

📚 Oficiálny manuál: dekorátory

Praktický príklad: Dátový pipeline

Problém: Zoznam objednávok odfiltrovať tie s nulovou sumou, vypočítať DPH z každej a získať celkovú sumu bez DPH.


orders = [
    {"id": 1, "amount": 100, "vat_rate": 0.20},
    {"id": 2, "amount": 0, "vat_rate": 0.20},  # vyraď
    {"id": 3, "amount": 250, "vat_rate": 0.10},
    {"id": 4, "amount": 80, "vat_rate": 0.20},
]

Riešenie imperatívnym štýlom

total = 0
for order in orders:
    if order["amount"] > 0:
        vat = order["amount"] * order["vat_rate"]
        total += order["amount"]

Riešenie pomocou list comprehension

active = [o for o in orders if o["amount"] > 0]
with_vat = [{**o, "vat": o["amount"] * o["vat_rate"]} for o in active]
total = sum(o["amount"] for o in with_vat)

Riešenie funkcionálnym štýlom

from functools import reduce
# 1. Odfiltrujeme nulové objednávky
active = list(filter(lambda o: o["amount"] > 0, orders))
# 2. Pripočítame DPH
with_vat = list(map(
    lambda o: {**o, "vat": o["amount"] * o["vat_rate"]},
    active
))
# 3. Spočítame celkovú sumu bez DPH
total = reduce(lambda acc, o: acc + o["amount"], with_vat, 0)

📚 Oficiálny manuál: Functional Programming HOWTO

📖 Dive Into Python 3: Comprehensions

Paralelizácia pomocu funkcií vyššieho rádu

filter, map a reduce sa dajú paralelizovať, pretože každé volanie funkcie je nezávislé od ostatných.

from multiprocessing import Pool

def process_order(order):
    if order["amount"] > 0:
        vat = order["amount"] * order["vat_rate"]
        return {**order, "vat": vat}
    return None

# Vytvoríme pool procesov
with Pool() as pool:
    # spracovanie objednávok paralelne
    results = pool.map(process_order, orders)
    # odfiltrujeme None hodnoty
    results = [r for r in results if r is not None]
    # spočítame celkovú sumu bez DPH
    total = sum(r["amount"] for r in results)

📚 Oficiálny manuál: multiprocessing.Pool

Map a reduce v HPC počítačoch

Hadoop a Spark sú distribuované výpočtové systémy, ktoré využívajú map a reduce na spracovanie veľkých dát.

Príklad: počítanie počtu IP adries z logov z webového servera

MAP: rozdelíme logy na menšie časti a počítame IP adresy pre pre každú časť osobitne paralelne na viacerých uzloch.

REDUCE: zjednotíme čiastkové výsledky z jednotlivých uzlov do jedného výsledku.

Teaser: Objektové programovanie je opak funkcionálneho - metródy tried menia stav objektu..

Rekurzia a funkcionálne programovanie

Funkcia v Pythone

Funkcie sú objekty

Lambda funkcie

Triedenie pomocou lambda funkcie

Generátor

Rekurzia

Rekurzívne prechádzanie zoznamu

Dve časti rekurzie

Priebeh výpočtu

Rekurzia namiesto cyklu

Čo je funkcionálne programovanie?

Čisté funkcie

Testovanie čistých funkcií

Funkcie vyššieho rádu

📚 Oficiálny manuál: Functional Programming HOWTO 📖 Dive Into Python 3: A List Of Functions

Funkcie vyššieho rádu pre spracovanie zoznamov

map()

🔵 filter()

🔴 reduce() – redukuje na jednu hodnotu

Odvodenie zoznamu - list comprehension

Uzáver - Closure

Dekorátory sú funkcie vyšieho rádu

Cache pre fukcie s @lru_cache

Dekorátor s parametrami

Praktický príklad: Dátový pipeline

Riešenie imperatívnym štýlom

Riešenie pomocou list comprehension

Riešenie funkcionálnym štýlom

Paralelizácia pomocu funkcií vyššieho rádu

Map a reduce v HPC počítačoch

Cache pre fukcie s `@lru_cache`