{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# A funkcionális programozás alapelemei\n",
"\n",
"## Programozási paradigmák\n",
"\n",
"A [funkcionális programozás](https://docs.python.org/3/howto/functional.html) (ls. még a [wikipediát](https://en.wikipedia.org/wiki/Functional_programming)) kapcsán szót ejtünk a programozási paradigmákról. A nyelvek többsége nem sorolható be egyetlen paradigma alá, inkább több különbözőből tartalmaznak elemeket, mint a Python is. A következő osztályozás leegyszerűsítő ugyan, de a legfontosabbak szerepelnek benne:\n",
"\n",
" * **Imperatív**, melyben utasítjuk a gépet, hogy hogyan változtassa meg állapotát.\n",
" * **Procedurális**, ahol a program utasítások sorozata, melyek eljárásokba (procedúrákba) vannak csoportosítva (pl. C, FORTRAN, bash).\n",
" * **Objectum alapú**, ahol objektumokat kezelünk, melyeknek belső állapotuk van, ami lekérdezhető és megváltoztatható metódusokkal (pl. Java)\n",
" * **Declaratív**, ahol leírjuk a problémát, és a program „találja ki”, hogyan oldja meg.\n",
" * **Logikai**, ami főleg a formális logikára épül (pl. Prolog)\n",
" * **Funkcionális**, amelyben az eredményt függvényhívások sorozatával deklaráljuk. (pl. Haskell, Standard ML, Lisp)\n",
" * **Adatbáziskezelő**, amelyben az adatok szerkezetének megadása után a kérdésekre a rendszer adja meg a választ. (pl. SQL)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Egy tisztán funkcionális programban egy függvény adott bemenetre mindig ugyanazt a kimenetet adja, és nem változtatja a program állapotát.\n",
"\n",
"A fenti feltétel nem teljesül, ha változóknak értéket adok majd azokat megváltoztatom, például az alábbi függvény más eredményt adhat akkor is, ha a paramétere ugyan az.\n",
"```Python\n",
" def f(y):\n",
" return x + y\n",
"\n",
" x = 1\n",
" print(f(5))\n",
" x = -5\n",
" print(f(5))\n",
"```\n",
"Ha ezt elkerüljük, akkor a függvényeink matematikai értelemben is függvények lesznek, nem pedig eljárások/procedúrák (gépi utasítások) egymás utánjai. Innen a név, _funkcionális_ programozás.\n",
"\n",
"### Történelem\n",
"Guido van Rossum eredetileg ki kívánta dobni a funkcionális programozási nyelvekből ismert alapfüggvényeket a Python 3 core-ból a listaértelmezéssel helyettesíthetőnek tartva a fontosabbakat. A funkcionális programozás híveinek kemény ellenállását látva végül a `lambda`, `map()`, `filter()` maradt, de a `reduce()` kikerült az `functools` csomagba.\n",
"\n",
"### Előnyök\n",
"A funkcionális programok helyessége könnyebben igazolható, könnyebben tesztelhetők, modulárisabbak,..."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Listaértelmezés, generátorkifejezés\n",
"Az első és legfontosabb funkcionális nyelvi elem a Pythonban az iterátor, amiről már volt szó. Végigmenni egy bejárható objektum elemein, kiválogatni közülük bizonyosakat valamilyen feltétel szerint és tenni velük valamit a funkcionális programozás legfőbb eleme.\n",
"Pythonban a listaértelmezés (*list comprehension*) és a generátorkifejezés (*generator expression*) használható e feladatokra.\n",
"\n",
"A listaértelmezés egy listát ad vissza, a generátorkifejezés egy iterátort. A szintaktikájuk azonos, kivéve hogy az előbbit `[]`-be, utóbbit `()`-be tesszük."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Példa:** Sztringek listáját kapjuk egy fájlból beolvasott sorokból. A `.strip()` metódust használva vegyük le mindegyik sor elejéről és végéről a *white space* karaktereket."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"lines = [' line1 ', 'line2\\t', ' ', ' line3 \\n ', '\\n']\n",
"stripped_iter = (line.strip() for line in lines)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"for i in stripped_iter:\n",
" print(i, end=\"\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[line.strip() for line in lines]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[line.strip() for line in lines if line.strip() != \"\"]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A generátorkifejezés általános alakja:\n",
"```Python\n",
"(expression for expr1 in seq1\n",
" if condition1\n",
" for expr2 in seq2\n",
" if condition2\n",
" ...\n",
" for exprN in seqN\n",
" if conditionN )\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A listaértelmezésé ugyanez, csak `[]`-ben. Ez a következő kóddal ekvivalens:\n",
"```Python\n",
"for expr1 in seq1:\n",
" if not (condition1):\n",
" continue\n",
" for expr2 in seq2:\n",
" if not (condition2):\n",
" continue \n",
" ...\n",
" for exprN in seqN:\n",
" if not (conditionN):\n",
" continue\n",
" expression\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[(x, y, x * y) for x in (1, 2, 3) for y in [1, 2, 3, 4] if x < y]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = []\n",
"for x in (1, 2, 3):\n",
" for y in [1, 2, 3, 4]:\n",
" if x < y:\n",
" l.append((x, y, x*y))\n",
"l"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Feladat:** Írjuk ki az 1890 és 1915 közti szökőéveket:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[ev for ev in range(1890, 1915)];"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[ev for ev in range(1890, 1915) if ev%4 == 0]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[ev for ev in range(1890, 1915) \n",
" if (ev%4 == 0 and ev%100 != 0) or ev%400 == 0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Lambda függvények\n",
"\n",
"Ha egy egyszerű kifejezést szeretnénk kiértékelni, akkor ezekhez külön függvényt írni nem feltétlenül szükséges, lokálisan használhatunk egy egyszerűbb módon definiált függvényt, ez a lambda-függvény. Ennek alakja\n",
"```Python\n",
"lambda arguments: expression\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def negyzet(x):\n",
" return x * x\n",
"\n",
"negyzet(5)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"negyzet2 = lambda x: x * x\n",
"\n",
"negyzet2(5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Akár nevet sem kell adni az objektumnak:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"(lambda x: x**2)(5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A lambda-függvénynek több argumentuma is lehet:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"kif = lambda a, b, c: a + b*c\n",
"\n",
"kif(2, 4, 5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## map()\n",
"A map()
egy iterálható objektum minden elemére alkalmazza a megadott függvényt és visszaad egy iterátort. (A Python korábbi változataiban egy listát adott vissza). Matematizált formulával valahogy így nézne ki:\n",
"$$\\mathop{\\mathrm{map}}:(A\\mapsto B)\\times A^n\\mapsto B^n\\ \\ (n\\in \\mathbb{N})$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"l = [1, 5, 8]\n",
"print(map(negyzet, l))\n",
"list(map(negyzet, l))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"d = {1: 5, 2: 6, 3: 7}\n",
"list(map(negyzet, d))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(map(negyzet, d.values()))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(map(lambda x: x.capitalize(), ['pápa', 'tata']))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Listaértelmezéssel:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[x**2 for x in range(5)]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[x.capitalize() for x in ['pápa', 'tata']]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A map
többváltozósként is használható. Ha az $f$ függvény több változós, akkor több lista megadása szükséges és \n",
"a map
mindegyiken szimultán halad és hattatja az $f$ függvényt.\n",
"\n",
"Formalizálva valahogy így:\n",
"$$\\mathop{\\mathrm{map}}: (A \\mapsto X)\\times A^n \\mapsto X^n$$\n",
"$$\\mathop{\\mathrm{map}}: (A\\times B \\mapsto X) \\times A^n\\times B^n \\mapsto X^n$$\n",
"$$\\mathop{\\mathrm{map}}: (A\\times B \\times C\\mapsto X)\\times A^n\\times B^n\\times C^n \\mapsto X^n$$\n",
"$$\\vdots$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(map(pow, [.5, 1, 1.5], [-1, 2, 3]))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(map(pow, [.5, 1], [-1, 2, 3]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Feltételes kifejezések\n",
"lambda függvényekben használhatunk feltételes kifejezéseket is. A feltételes kifejezések formája a következő:\n",
"```Python\n",
"kifejezés if feltétel else kifejezés a feltétel hamis esetre\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x = -4\n",
"x if x>0 else -x"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def abszolut(x): \n",
" return x if x >= 0 else -x\n",
"\n",
"abszolut(5), abszolut(-5)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(map(lambda x: x if x>0 else 0, range(-5,5)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Feltételes kifejezésekben az `else` használata **kötelező**.\n",
"Ennek egy következménye, hogy nem lesznek lefedetlen esetek a kódban.\n",
"\n",
"Példa lefedetlen esetekre:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def korosztaly(x):\n",
" if x < 8:\n",
" return \"gyerek\"\n",
" elif x < 15:\n",
" return \"fiatal\"\n",
" elif x >= 18:\n",
" return \"felnőtt\"\n",
"\n",
"korosztaly(16)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def korosztaly(x):\n",
" return \"gyerek\" if x < 8 else (\"fiatal\" \n",
" if x < 15 else (\"felnőtt\" \n",
" if x >= 18 else \"egyik sem\"))\n",
"\n",
"korosztaly(16)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## filter()\n",
"\n",
"A filter
függvény leszűr egy bejárható objektumot egy adott bool-függvény szerint.\n",
"\n",
"A feltétel függvény egy $A\\mapsto \\{True, False\\}$ függvény kell legyen.\n",
"\n",
"$$\\mathrm{filter} : (A\\mapsto \\{True, False\\})\\times A^n\\mapsto A^m \\text{ ahol } m\\leq n$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(filter(lambda x: x % 2 == 0, range(10)))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"[x for x in range(10) if x % 2 == 0]"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(filter(str.isupper, \"aAbBcCöŐ\"))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `zip()`"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"list(zip(['a', 'b', 'c'], (1, 2, 3)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### `any()` és `all()`\n",
"A kvantoroknak megfelelő függvények eldöntik, hogy egy bejárható objektum elemei közt van-e True, illetve hogy mindegyik True értékű-e."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"any([1, 2, 0, 1])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"all([1, 2, 0, 1])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import math\n",
"print([math.cos(i*math.pi) for i in range(3)])\n",
"any([math.cos(i*math.pi) == 1.0 for i in range(3)])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"all([math.cos(i*math.pi) == 1.0 for i in range(3)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## reduce\n",
"\n",
"A reduce
(a `functools` csomag függvénye) egy 2-változós függvényt alkalmaz egy iterálható objektum (pl. lista) elemeire balról jobbra haladva, míg végül egyetlen értéket nem kap. Alakja:\n",
"\n",
"reduce(*függvény*, *iterálható*[, *kezdőérték*])
\n",
"\n",
"A kétváltozós függvény $A\\times B\\mapsto A$ alakú kell legyen, az iterálható elemek $B$ beliek, a kezdőérték $A$-beli. A kezdőértéket a többi elem elé teszi. Ez a visszaadott érték üres lista esetén. Ha nincs kezdőérték, és a lista egyelemű, akkor azt az elemet adja vissza.\n",
"\n",
"Egy $(a, b, c)$ tuple-re és egy $x$ kezdőértékre a reduce
a következőt adja:\n",
"$$\\mathop{\\mathrm{reduce}} (f, (a,b,c)) = f(f(a, b), c)$$\n",
"$$\\mathop{\\mathrm{reduce}} (f, (a,b,c), x) = f(f(f(x, a), b), c)$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from functools import reduce\n",
"osszeg = lambda a, b: a+b\n",
"reduce(osszeg, [1, 2, 3, 4])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"reduce(osszeg, [4])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"reduce(osszeg, [], 0)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"osztas = lambda a, b: a/b\n",
"print(reduce(osztas, [2, 3, 4], 1))\n",
"1/24"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Ezzel az összegzés tétele elvileg bármikor elvégezhető és a szélsőérték keresés ennek egy alesete."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"nagyobb = lambda x, y: x if x>y else y\n",
"reduce(nagyobb, [0, 1, 10, -10, 2], float(\"-inf\"))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"kisebb = lambda x, y: x if x