Funkcionální programování

Funkcionální programování

Funkcionální programování

• funkce jsou základním stavebním kamenem
• neexistují proměnné, třídy, objekty, ...
• funkce nemají vedlejší efekty — nemění stav mimofunkčních věcí
• funkce se mohou předávat jako parametry
• funkce mohou vracet funkce

Důvod existence

• jednoduchost
• přehlednost
• snadná paralelizace

LISP

• LISt Processing
• 1958
• John McCarthy
• první funkcionální jazyk
• první jazyk s automatickou správou paměti (garbage collector)
• revoluční

Racket

• navazuje na LISP
• mnoho dialektů
• Scheme, Clojure, ...

Použití

• Emacs
• AutoCAD
• GIMP
• ...

IDE a použití

• DrRacket
• nutné použít #lang racket
• příkaz racket spustí překlad a interpretaci

Funkce

Definice

• klíčové slovo define
• jméno funkce
• seznam parametrů
• tělo funkce

Ukázka

Vyhodnocení

• při volání funkce se vyhodnotí všechny parametry
• výsledky se přiřadí do proměnných
• vyhodnotí se tělo funkce
• výsledek se vrátí

Výpočet

Práce

Vyhodnoďte následující výrazy:

• (/ 1 2)
• (floor (/ 1 2))
• (+ 1 (* 2 3))
• (+ 1 (* 2 (- 3 4)))
• (+ (ceiling (/ 1 2)) (* 2 (3 (- 4 5))))

Boolean hodnoty

• #t
• #f

Boolean funkce

• (not x)
• (and x y)
• (or x y)

Funkce pro porovnání

• (= x y)
• (< x y)
• (> x y)
• (<= x y)
• (>= x y)

Matematické funkce

• (+ x y)
• (- x y)
• (* x y)
• (/ x y)
• (floor x)
• (ceiling x)

Další funkce

• (print x)
• (newline)
• a další, později

Další vyhodnocení

Práce

Vyhodnoďte následující výrazy:

• (not #t)
• (and #t #f)
• (or (not #t) #f)
• (= 1 (+ 1 (* 2 3)))
• (< 1 (+ 1 (* 2 3)))
• (> 1 (+ 1 (* 2 3)))

Používání funkcí

Zavolání funkce

Podmínky

• (if test then else)
• test se musí vyhodnotit na boolean hodnotu
• pokud je test #t, vyhodnotí se then
• pokud je test #f, vyhodnotí se else

Ukázka podmínky

Rekurze

Příklady

Základní operace

Práce

Napište následující funkce:

• (inc x) — zvýší číslo o 1
• (dec x) — sníží číslo o 1
• (zero? x) — zjistí, zda je číslo 0
• (add x y) — sečte dvě čísla pomocí funkcí výše
• (mul x y) — vynásobí dvě čísla pomocí funkce add

Mocnina

Práce

Napište program, který vypočítá mocninu čísla x s exponentem n.

Fibonacciho posloupnost

Práce

Napište program, který vypočítá n-tý prvek Fibonacciho posloupnosti.

Listy

Listy

• vše je list
• list je vždy uzavřený v kulatých závorkách
• list může obsahovat libovolný počet prvků
• prvky jsou odděleny mezerou
• reprezentováno buňkami

Buňky

• buňka je reprezentována jako (a . b)
• první prvek je hlava
• druhý prvek je zbytek
• zbytek je buňka nebo empty
• list (1 2 3) je reprezentován jako (1 . (2 . (3 . empty)))

Práce s listy

• (cons a b) — vytvoří buňku (a . b)
• (car x) — vrátí hlavu buňky
• (cdr x) — vrátí zbytek buňky
• (list a b c) — vytvoří list (a b c)
• (null? x) — zjistí, zda je list prázdný

Porovnání

• (equal? x y)
• vrací #t, pokud jsou x a y stejné (včetně struktury)
• jinak vrací #f

Práce s listy

Zamezení evaluace

• ' či (quote x) — zamezí evaluaci
• kdybychom nepoužili, daný výraz by se vyhodnotil

Vlastní délka

Práce

Napište vlastní funkci length, která spočítá délku listu.

Příklady

n-tý prvek

Práce

Napište funkci (nth n list), která vrátí n-tý prvek listu.

min a max listu

Práce

Napište funkce (min list) a (max list), které vrátí nejmenší a největší prvek listu.

obsahuje?

Práce

Napište funkci (contains? list x), která zjistí, zda list obsahuje prvek x.

Vytvoření listu

Práce

Napište funkci (range a b), která vytvoří list čísel od a do b.

Prohození prvků

Práce

Napište funkci (reverse list), která prohodí prvky listu (první s posledním, druhý s předposledním, atd.).

Odstranění prvků

Práce

Napište funkci (remove list x), která odstraní všechny výskyty prvku x z listu.

Prvočísla

Práce

Napište program, který zjistí, zda zadané číslo je prvočíslo.

Prvočíslo je číslo, které je dělitelné pouze jedničkou a sebou samým.

Let

• definice lokálních hodnot
• použití uvnitř funkce
• (let (variables) body)
• variables jsou list dvojic (name value)

Let

Cond

• podmíněné vyhodnocení
• zlepšení vnořování if
• (cond (test1 body1) (test2 body2) ...)
• testy jsou vyhodnoceny postupně, dokud není nalezeno první pravdivé
• pokud není nalezeno žádné pravdivé, je vyhodnocen test s hodnotou else

Cond

Rekurze

Koncová rekurze

• snižuje paměťovou náročnost
• při volání funkce se neukládá na zásobník
• při volání funkce se přepíše aktuální rámec
• často tzv. akumulátory

Koncová rekurze

Funkce vyššího řádu

Funkce vyššího řádu

• funkce, která přijímá funkci jako parametr
• funkce, která vrací funkci jako výsledek
• jeden z nejdůležitějších konceptů funkcionálního programování
• např. map, filter, fold

Anonymní funkce

• funkce bez jména
• používají se jako parametry
• používají se jako výsledek
• (lambda (params) body)

Anonymní funkce

map

Aplikuje funkci na každý prvek seznamu a vrátí seznam výsledků.

filter

Vrátí seznam prvků, které splňují podmínku.

foldr a foldl

Prochází seznam a vrací jednu hodnotu. Foldr prochází seznam zprava doleva, foldl zleva doprava.

Příklady

Vlastní implementace

Práce

Vytvořte vlastní implementace funkcí map, filter a foldr. Nepoužívejte vestavěné funkce.

Eratosthenovo síto

Práce

Vytvořte funkci, která vytvoří seznam prvočísel menších než zadané číslo pomocí Eratosthenova síta. Použijte funkcí filter.

Další

• řazení pole
• binární stromy
• hledání cesty v grafu

Moderní funkcionální jazyky

Moderní funkcionální jazyky

• nejznámější nejspíše Haskell
• cíle — mnohem více API, lepší paralelizace, ...
• různé syntax sugar

Použití moderních funkcionálních jazyků

Práce

Najděte si informace o Haskellu nebo jiném moderním funkcionálním jazyku. Jazyk si zkuste vyzkoušet a napište nějaký jednoduchý program.