FUP Flashcards
(84 cards)
1
Q
Funkcionalni programovani
A
programovaci styl zalozenny na strukturaci programu jako kompozici cistych funkci
2
Q
Cista funkce (pure)
A
takova funkce, ktera pri stejnem inputu VZDY vrati stejny output
Nema vedlejsi ucinky - nemodifikuje zadna data, nema vliv na okolni svet a struktury
- je nezavisla na vnejsim svetu, pouze sama se sebou pracuje
cisty program - sestaven pouze z cistych funkci
3
Q
Vyhody cistych funkc
A
nezavisle na okoli - udrzitelne
- jednoduche testovani
- znovupouzitelne nezavisle na kontextu
- rozsiritelne
- paralelni
4
Q
Dusledky cistych funkci/funckionalniho programovani - hlavni vlastnosti
A
Rekurze oproti smycka
- smycka meni stav, rekurze ma stav jako stack
- immutable datove struktury
- zmena stavu datove struktury se provadi jeji kopii a zmenou
- perzistentni datove struktury pro mensi pocet kopii datovych struktur
- takova struktura, ktera vytvori pouze cast kopie, ktera je ovlvienan zmenou, zbytek nedotcene struktury se pouze odkazuje na puvodni strukturu
- tedy vytvori se cast nove struktury a nedotcena cast ukazuje na puvodni jeste
5
Q
Jde mit plne pure program?
A
Ne, potrebujeme alespon nejakou zmenu stavu (treba vypis do konzole)
proto zadny program neni 100% pure, ale mutable cast kodu, ktera zavisi na nejakem stavu se snazime minimalizovat co nejvic
6
Q
Lisp, Scheme, Racket, DrRacket
A
Lisp - list processor (jazyk, ve kterem vsechno je list), prefixova notace
Scheme - dialect of Lisp
Racket - another dialect
DrRacket - IDE pro Racket
7
Q
Racket semantika/co je psany program
A
Program v raketu - vyraz, ktery je postupne vypocitavan/evaluovan od nejvnitrnejsiho po vnejsi dokud nedojdeme k posledni hodnote
8
Q
Stretegie vyhodnocovani vyrazu
A
Strategie, kdy se hodnoty vyrazu spocitaji, zda hned, nebo na konci, nebo postupne atd…
Hlavne dulezite v parametrech funkci a podminkach:
treba jak se vyhodnoti volani funkce s parametry:
(define (square x) (* x x)) // definuju funkci square
(square (+3 4)) => (square 7) => (* 7 7) => 49
- Striktni strategie Racketu - VSECHNY parametry se nejdriv vyhodnoti zleva doprava, az pote se vola funkce
(square (+3 4)) => (* (+ 3 4) (+ 3 4)) => (* 7 7) => 49
- lazy evaluace - nejdriv se aplikuje funkce, a az pote se dopocitaji vnitrni parametry - pripad podminek
Racket funkce - eager
Racket podminky - lazy
9
Q
Syntax podminek racketu
A
(if test-exp then-exp else-exp)
(if (> 0 1) 1 2) => 2
(if (< 0 1) 1 (+ 3 “a”)) => 1
(cond [test-exp1 exp]
[test-exp2 exp]
…
[else exp])
(cond [(odd? 12) 1]
[(even? 12) 2]
[else 3]) => 2
10
Q
Zakladni datove typy Racketu
A
Numbers - +, -, /, abs, sqrt, number?, <, >, =…
Bool - #t, #f, and, or, not, boolean?
String - “abc”, string?, substring, string-append
Characters - #\A, #\@, char?m char->integer, integer->char, list->string
11
Q
Typy rekurzi
A
Linearni - jedno rekurzivni volani v tele
Stromova - vice rekurzivnich volani v tele
- podtyp stromove - TAIL - vysledek rekurze je vysledek i funkce
12
Q
Priklad TAIL rekurze
A
Klasicke vyuziti kdyz v rekurzi agregujeme nejakou hodnotu
Typicky priklad
podminka?
- pokud ne -> vrat basic pripad
- pokud ano -> aktualni_hodnota * rekurze(mensi hodnota)
(define (fact n)
(if (<= n 1)
1
(* n (fact (- n 1)))))
Bez tail rekurze ma to extremne moc volani v pameti protoze se zavola:
(fact 4) => (* 4 (fact 3))
=> (* 4 (* 3 (fact 2)))
=> (* 4 (* 3 (* 2 (fact 1))))
=> (* 4 (* 3 (* 2 (* 1 1)))) => 24
Tedy narocnost pameti je O(n) -> tolik volani, jake je cislo ale v kazde hladine se zvetsuje do sirky
Kdybych vysledek postupne agregoval v argumetnu predavanem:
(define (fact n [acc 1])
(if (<= n 1)
acc
(fact (- n 1) (* n acc))))
Tak postupne mi narusta hodnota mezivysledku faktorialu:
(fact 4) = (fact 4 1)
=> (fact 3 4)
=> (fact 2 12)
=> (fact 1 24)
=> 24
a mam pouze jednu sirku v patre, tedy O(1) pametova narocnost
13
Q
Jak vytvorit par, list v Racketu, car, cdr, …
A
Par - umoznuje konstrukci hierarchickch datovych struktur
- treba i ruzne typy
(cons 1 2) => ‘(1 . 2)
(car (cons 1 2)) => 1
(cdr (cons 1 2)) => 2
(cons (cons 1 (cons 2 3)) 4) // si nemusim predstavovat jako linearni pole paru, ale hierarchickou strukturu jako (cons X 4), kde X v sobe obsahuje dalsi jemenjsi deleni do stromu paru
List - sekvence paru s prazdnym listem na konci:
- je to jako linked list, kde je to lienarni struktura a kazdy prvkek odkazuje na dalsi, na konci je prazdny ‘()
(cons 1 (cons 2 (cons 3 (cons 4 ‘()))))
(list 1 2 3 4)
(car (list 1 2 3)) => 1 ; also: first
(cdr (list 1 2 3)) => (2 3) ; also: rest
(caddr (list 1 2 3)) => 3
(list? (list 1 2 3)) => #t
(empty? (list 1 2 3)) => #f
(list 1 2 (+ 1 2)) => ‘(1 2 3)
(append ‘(1) ‘(2) ‘(3 4)) => ‘(1 2 3 4)
14
Q
Druhy porovnani v Racket
A
= pro numerickou rovnosti
eq? pro ukazatelovou rovnost
equal? pro strukturalni rekurzivni rovnost, pro slozitejsi pole a struktury
15
Q
lambda
A
anonymni funkce, kterou nemusime pojmenovavat, jen uvedeme funckionalitu
pouziva se jako “inline” definice funkce v ramci treba mapu, nebo filtru:
(filter (lambda (x) (< x 5))
‘(1 7 3 8)) => ‘(7 8)
Another useful function iterating through a list is map.
(map f lst) applies f to each element of lst:
(map (lambda (x) (* x x)) ‘(1 2 3)) => ‘(1 4 9)
map f lst -> namapuje/provede funkci po elementech na kazdy posle
16
Q
Operator let* v Racket
A
Umoznuje zadefinovat lokalni promenna/data pro prehlednejsi kod
drzi mezivypocty treba abych nehromadil milion zavorek
17
Q
Stromy v Racket
A
Reprezentovany jako vnorene listy ‘(data left right)
‘(1 (2 (4 (7 #f #f) #f)
(5 #f #f))
(3 (6 (8 #f #f)
(9 #f #f))
#f))
Tedy 1-2,3
2-4,5
7 - f, f
3-6,f
8-f,f
9-f,f
18
Q
Rekurze stromem v Racketu
A
(define get-data car) //prvni prvek listu - koren
(define get-left cadr) // druhy prvek listu - levy potomek
(define get-right caddr) // druhy prvek listu - pravy
(define (find pred tree)
(if tree
(let* ([data (get-data tree)]
[left (find pred (get-left tree))] // rekurze stromem vlevlo
[right (find pred (get-right tree))] // rekurze stromem vpravo
[both (append left right)]) // vysledek obou rekurzi
(if (pred data)
(cons data both) //sluc vysledek treba…
both))
‘()))
19
Q
Evaluace vyrazu treba kod
A
Rekurzivne rozbijim vyraz na mensi celky, kdyz jsem narazil na zakladni prvek -> vrat ho
Dokud mam co evaluovat -> rekurzivne evaluuj po komponentach:
Nejdriv evaluuju vsechny arguemtny, pak podle operace na ne ji aplikuju:
(define (eval-expr e)
(if (number? e)
e
(let ([op (car e)]
[children (map eval-expr (cdr e))])
(cond
[(eq? op ‘+) (apply + children)]
[(eq? op ‘-) (apply - children)]
[(eq? op ‘*) (apply * children)]
[(eq? op ‘opp) (- (car children))]))))
apply takes a function and a list of arguments, “unwraps” the
arguments - (apply + ‘(1 2 3)) => (+ 1 2 3)
20
Q
High-order funkce, vyssi funcke
A
Takove funkce, ktere:
1. Jako argument prijimaji jine funkce
2. Vraci funkci jako navratovou hodnotu
3. Oboje naraz
Slouzi k vyssi urovne abstrakce, znovupouzitelnost navrhu programu (nemusim pokazde prepisovat funkci, staci do ni pouze vlozit jinou funkci, treba
apply f args -> nezavisle na f, tedy to je znovupouzitelny kus kodu
21
Q
Priklady funkci vyssiho radu
A
- Filter - filter elements of a list by some predicate
(filter pred lst) -> (lst) // without elements that does not satisfy pred - Map - applies func to each element of a list
(map f lst) -> ‘(f(l1) f(l2) … f(ln)) - Apply - “inserts” function between each element of a list (reduction)
(apply f lst) -> (l1 f l2 f l3 f … ln) - fold (l/r) - aggregates elements in a list by binary operation from left/right
(foldr + 0 (1 2 3)) -> (((0+1) + 2) + 3) = 6, postupna redukce, agregace dat podle funkce f od pocatecni hodnoty neutralni treba
22
Q
Castecna evaluace, curry
A
Princip curry v programovacím jazyce jako je Racket se týká transformace funkce s více argumenty na posloupnost funkcí s jedním argumentem. V podstatě to znamená, že namísto toho, aby byla funkce aplikována na všechny argumenty najednou, je možné postupně aplikovat na každý argument zvlášť.
Klasicka funcke bez curry:
(define (add a b)
(+ a b))
S curry
(define (curry-add a)
(lambda (x)
(+ a x)))
- tedy nesectu parametry hned, ale pouze vratim jinou funkci (ktera uz ma prednastaveny jeden arguemnt) a pouze ceka na dalsi vstup.
Je to vyhodne prednastaveni parametru, ktere se nebudou menit a na ne mohu nabalovat dalsi parametry ktere uz jsou prommenne.
Vyhodou je postupne nabalovani argumentu do funkce jako pipelining, aniz bych musel porad voalt tu samou funkci dokola, ale menim jen jeden argument.
Je to optimalni zrychleni, kdy funkci predpripavi predem.
Pouziti dobre treba v map, kdy na kazdy element pole poslu curry funkci:
(define (add a b) (+ a b))
(define add5 (curry add 5)) ; add5 je funkce (lambda (x) (+ 5 x)), tedy vytvoril jsem jakousi “makro-rutinu”, ktera pricte 5 k jakemukoliv arguemtnu, ale uz ji nemusim volat pokazde se dvema argumentami
(map add5 ‘(1 2 3)) ; Výstup: ‘(6 7 8)
Dalsi vyhodou je vytvoreni jakehosi pomocneho makra pro lepsi vizualizaci a citelnost kodu:
(define add5 (curry add 5)) ; vytvoříš si pomocníka/makro
tedy toto makro muzu poslat na jina cisla
(add5 3) ; můžeš používat dál -> 8
23
Q
Curry vs lambda funkce
A
Curry mi muze jednoduse a PREHLEDNE nahradit zbytecne hromadeni kodu pri psani lambda funkci ve funkcich vyssiho radu:
treba chci kazdy prvek v poli vynasobit dvema:
(1 2 3) -> (2 4 6)
Pristup pomoci lambda funcke:
(map (lambda (x) (* 2 x)) (1 2 3)) -> tedy jsem zbytecne zabral misto a zneprehlednil kod…
Pristup pomoci curry:
(map (curry * 2) (1 2 3)) -> prehlednejsi postupne aplikovani *2 na kazdy prvek
klicove slovo curry transofrmuje funkci v jeji curry verzi:
treba (+ 2 3) -> ((curry + 2) 3)
24
Q
Skladani funkci f,g
A
Klasicky jako v linearni algebre:
g pote co f:
gof = g(f(x)) a muzu nabalovat dalsi a dalsi funkce…
Vzdy vyhodnotim vnitek, ten se stane argumentem pro vnejsi atd…
Bud hromadim zavorky nebo pouziju klicove slovo compose
25
Volne promenne lammbda funkci
Pri definici lambda funkce v ni mohu pouzit tzv volne promenne, ktere nejsou parametrem funkce, ale odkazuji na globalni, pred tim zadefinovane hodnoty. Treba:
define u 1)
(define fn (lambda (x) (+ x u))) // u je volna promenna
- ALE volna promenna si PAMATUJE tu hodnotu u, KDY BYLA FUNKCE DEFINOVANA
- tedy tato lambda funcke NAVZDY SI PAMATUJE u=1
- nepomuze ani prepsani lokalne:
let ([u -1])
(fn 5)) => 6
Protoze funkce fn si furt mysli, ze u je definovano = 1.
Nepomohlo by ani volat fn v ramci let bloku:
let ([u -1])
(fn 5))) => 6
Protoze fn pracuje s u hodnotou takovou, kdy byla fn definovana, takze i lokalni zavedeni to neovlivni
Pokud bych zadefinoval samotnou fn v ramci let bloku, pak by si fn navzdy myslela, ze u=-1
26
Vazany rozsah promennych (lexicky, dynamicky)
Vetsina programovacich jazyu cetne Racketu pouzivat lexicky rozsah pro volne promenne zadefinovanych funkci
1. Lexicky - pokud zadefinovana funcke obsahuje volne promenne, pak si jejich hodnoty NAVZDY PAMATUJE jako takovou, kterou mela v moment definice
- tedy porad si bude myslet ze volna promenna je staticka navzdy
2. Dynamicky - funkce "dosadi" dynamicky hodnotu volne promenne podle hodnotu, kterou tato promenna ma v moment volani funkce
- tedy ji dynamicky sleduje a updatuje
Pseudokod:
a = 1
foo(x) -> x+a
a=2
foo(0)
1. Lexicky scope - foo(x) si navzdy bude myslet, ze a=1, i kdzy jsme jeji hodnotu zmenili potom:
foo(0) = 1
2. Dynamicky scope - foo(x) bylo vazane na a=1, ale v moment volani funkce foo(0) je jiz a=2, tedy pocita s 2
foo(0) = 2
27
Funkcni closure/uzaver
Když vytvoříš funkci (pomocí lambda), v Racketu se neuloží jen kód funkce, ale také prostředí, ve kterém byla definována.
Closure = "balíček" obsahující:
- Kód funkce (tělo funkce)
- Prostředí: hodnoty všech volně vázaných proměnných, které funkce potřebuje
(define (make-adder x)
(lambda (y) (+ x y)))
- zadefinoval jsem curry-makro scitani dvou cisle, kde budu zadavat pouze y
- o hodnote x jeste nevim nic, tu musim dospecifikovat pozdeji
- dospecifikvoat x mohu pomoci definice make-adder s konkretnim x:
(define adder10 (make-adder 10)) ; uzávěr s x = 10, navzdy jsem uzavrel kontext
(define adder3 (make-adder 3)) ; uzávěr s x = 3
(define adder7 (make-adder -7)) ; uzávěr s x = -7
(adder10 5) ; => 15
(adder3 5) ; => 8
(adder7 5) ; => -2
Tyto funkce si budou navzdy pamatovat svoje promenne x, protoze jsem jim je ulozil do jejich closure - tedy pamatuji si nejen svuj kod, ale i hodnoty prostredi, ve kterem byly vytvoreny, nebo dospecifikovany
28
Dva pristupy, jak zavest/simulovat objekty/struktury ve funkcionalnim programovani
1. Pomoci ulozeni dat do closure funkci:
- toto simuluje "ulozeni" dat primo ve funkcich, bez struktrur
- funkce si pamatuji svoje hodnoty, protoze maji svoje closure prostredi
(define (point x y)
(lambda (m) (m x y)))
- toto je "konstruktor" bodu (x,y)
- point x y - je funkce, ktera ULOZI HODNOTY x a y do closure, pamatuje si je
- vraci funkci, ktera ceka na nejaky parametr, a zavola tento parametr spolu s x a y
(define p (point 3 10)) - tady p je tedy FUNKCE (closure s kodem a hodnotami x,y)
- toto p tedy CEKA NA ARGUMENT a ma PRISTUP k x a y
- mohu tam tedy poslat jako argument funkci, ktera mi vrati x nebo y
(define (get-x p)
(p (lambda (x y) x)))
- tedy ja ZAVOLAM CLOSURE p, predam mu funkci, ktera bere dva parametry a vrati prvni z nich
(get-x p) => 3
- chronologie:
get-x p => zavola funkci get-x s parametrem p => p je funkce, takze uvnitr tela get-x mohu => zavolam p => p samo o sobe ceka jako argument funkci, kterou aplikuje na SVOJE SCHOVANE x a y => tedy jako argument poslu takovou lambdu, ktera bere x a y a vraci x => vrati mi to x
2. Pomoci struktur:
(struct person (first-name surname age) #:transparent) ; defines type
(define pers (person "John"
"Down"
33)) ; defines instance, constructor
Accessor functions to all fields are automatically defined.
(person-first-name pers) => "John"
(person-surname pers) => "Down"
(person-age pers) => 33
(person? pers) => #t
(person? "John") => #f
29
Pattern matching
Technika umoznujici vetveni programu v zavislosti na tvaru vyrazu, ktere chceme porovnat/matchnout s nejakou sablonou preddefinovanou
(match exp
[pattern1 exp1]
[pattern2 exp2]
...)
Podobne jako cond, ale prehlednejsi, neni tolik ifu
(struct point (x y))
(match exp
[0 'zero]
[1 'one]
[2 'two]
["abc" 'abc]
[(point 0 0) 'point]
[(? string?) 'string]
[(and (? number? x) (? positive?))
(format "positive num ~a" x)]
[_ 'other])
Muze obsahovat jakekoliv typy - lepsi pokryti
- _ je "final" varianta
(match lst
[(list) 'empty]
[(list x) (format "singleton (~a)" x)]
[(list 'fn ys ...)
(format "fn and rest ~a" ys)]
[(list (list 'fn args ...) ys ...)
(format "fn with ~a and rest ~a" args ys)]
[(list 1 ys ... z)
(format "1, rest ~a and last ~a" ys z)]
[(list x ys ...)
(format "~a and rest ~a" x ys)]
[_ 'other])
Muzeme matchovat TVAR listu
30
Postpone evaluace/lazy/odlozena
Racket vetsinou pouziva striktni/eager evaluaci arguemtnu
- hlavne ve funkcich - nez se zavola funkce, tak se evaluuji vsechny predane argumenty zleva doprava
- toto neplati v pripade if/cond/or/and struktur logickych:
- tedy v tomto pripade:
(if (< 0 1) 0 (/ 1 0)) => 0, nam nevadi, ze jako druhy argument mame deleni nulou,
protoze k tomu nikdy nedojde
- if se hodnoti jako lazy
- tedy z pohledu Racketu je to jako:
- "je 0 < 1? ANO -> HNED vrat prvni arguemtn" - tedy nkdy ani nedojde k evaluaci druheho arguemtnu
- je to vymysleno z pohledu rychlosti a optimality - v logickych porovnanich neni treba vyhodnocovat vsechny elementy, pokud vysledna podminka bude jasne PLATIT/NEPLATIT
Ve funkcich se to ale vyhodnocuje vsechno, takze pokud bych si napsal nejaky svuj my-if ktery by volal if s predanymi arguemtny a ja bych pak zavolal tuto my-if funkci
- tak se napred vyhodnoti vsechny parametry
- OBJEVI SE CHYBA DELENI 0
31
Jak zabranit tomu, aby se vyraz vyhodnotil hned, ale az na vyzadani?
Vyraz zabalime do lambda funkce - thunk.
Tento vyraz se tedy nevyhodnoti hned, ale az pote, co si o to nekdo rekne
Pouziva se uz vbudovane v logickych konstruketch, nebo kdyz je to narocny vypocet, ktery bude dlouho trvat, nebo ktery nemusi ani nikdy byt potreba
(thunk expr) -> nevyhodnocuj expression hned, ale az to nekdo bude potrebovat
32
Stream
Usporadavne posloupnost elementu, ktere jsou vyhodnocovany lazy, postupne po jednom na vyzadani, muze byt i nekonecny
(delay expr) -> lazy evaluace
(force expr) -> vyhodnot expr
Funkce se streamem jsou podobne jako s listem
1. Explicitne
We can specify a stream by defining a generating function
computing a next element from previous ones.
(define (nats n) (stream-cons n (nats (+ n 1))))
-> vrati to (n . promise(n+1)), tedy nevyhodnoti to hned nekonecny stream,
ale lazy evaluuje steam prirozenych cisel jako n a lazy zbytek (promise), ktery se pak dopocte
2. Implicitne:
The stream of ones: 1 = 1, 1, 1, ...
(define ones (stream-cons 1 ones))
- tedy nejdriv pridam nic+1, pak +1, pak +1 na kazde vyzadani...
Scitani streamu: funguje pro prvni prvek a rekurzivne pro zbytek streamu:
stream-map works only for a single stream.
(define (add-streams s1 s2)
(stream-cons (+ (stream-first s1)
(stream-first s2))
(add-streams (stream-rest s1)
(stream-rest s2))))
Misto + muzu dosadit obecnou funkci...
33
Parsovani kodu
Nezbytna cast pro interpretaci programu
1. cast - parsovani
2. cast evaluace - vykonavani kodu - interpretace
Parsovani - proces, pri kterem je nacitan kod sekvence
- pro kazdy nacteny symbol/slovo se musi stanovit, jakemu gramatickemu pravidlu odpovida tento symbol
- treba takto
-> *
-> |
-> []
-> + | - | < | > | . | ,
Tedy program se rozlozi na posloupnost termu
- kazdy term se rozlozi bud na comand, nebo smycku
- smycka v sobe obsahuje dalsi podprogram
- comand je oprace nad daty (abecedou)/parametry
Tedy parsovani porad nacita a pattern amtchuje co nacetlo -
- je to program -> rekurzivne parsuj dal
- je to term -> parsuj dal
- je to smycka -> parsuj dal
- je to prikaz -> proved
Tedy priletelo mi neco jako:
expr1 operace expr2
- nejdriv rekurzivne zjisti evaluuj expr1,
pote rekurzivne evaluuj expr2,
- pote aplikuj operaci mezi nimi
34
Haskell zakladni prehled
Staticky typova (pri kompilaci)
- pouze lazy evaluace
- purely functional jazyk (az na IO)
- spousten pomoci GHC kompilace
Program (modul) .hs se sklada z definic typu a funkci
Funkce je deklarovana jako vyraz co vstupuje atyp co vystupuje:
e :: t
GHC interpreter dela nasledujici kroky pri interpretaci funkce:
1. zkontroluje syntaktickou korektnost e
2. Zkontroluje kompatibilitu typu e
3. Evaluuje rekurzivne e na nejprimitivnejsi tvar
4. Spocitana hodnota je vypsana do konzole
35
Primitivni datove Haskell typy
Bool logical values True, False
Char single characters 'a'
String strings of characters "abc"
Int fixed-precision integers
Integer arbitrary-precision integers
Float single-precision floating-point numbers
Double double-precision floating-point numbers
36
Zakladni syntax volani funkce Haskellu
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n-1)
power :: Integer -> (Integer -> Integer)
power _ 0 = 1
power n k = n * power n (k-1)
37
Pattenr matching haskell
Podobne jak v Racketu -> prvni nalezena schoda je vyhodnocena
True && True = True
_ && _ = False
38
Let/Where construct haskell
Umoznuje zavadet pomocne mezivypocty do funkce:
discr :: Float -> Float -> Float -> Float
discr a b c =
let x = b*b
y = 4*a*c
in x - y
Alternatively
discr a b c = x - y
where x = b*b
y = 4*a*c
39
Podminky haskell
abs n = if n >= 0 then n else -n
Conditional expressions can be nested:
signum n = if n < 0 then -1 else
if n == 0 then 0 else 1
40
Guarded podminky (match) haskell
As an alternative to conditionals, functions can also be defined
using guarded equations.
abs n | n >= 0 = n
| otherwise = -n
Definitions with multiple conditions are then easier to read:
signum n | n < 0 = -1
| n == 0 = 0
| otherwise = 1
41
List v Haskellu
Lists are sequences of elements of the same type, e.g. [Int]
[1,2,3,4,5]
[1..10]
['a'..'z']
[1,3..]
[10,9..1]
* Built by “cons” operator :, ended by the empty list []
* Includes all basic functions
take, length, reverse, ++, head, tail
* In addition, you can index by !!
* Data type String is just [Char]
42
List matching v haskellu
Podobne jak racket -> matchuje tvar listu
Functions on lists can be defined using x:xs patterns
head (x:_) = x // funkce head bere list jako (car:cdr) -> vraci car...
tail (_:xs) = xs
43
Tuple pattern amtching v haskellu
Podobne jako list:
Tuples are fixed-size sequences of elements of arbitrary types,
e.g. (Int, Char)
(1,2)
('a','b')
(1,2,'c',False)
Their element can be accessed by pattern matching
first (x,_,_) = x
second (_,x,_) = y
third (_,_,x) = x
44
List comprehension v haskellu
In Haskell, there is a list comprehension notation to construct
new lists from existing lists.
[x^2 | x <- [1..5]]
x <- [1..5] is called a generator
Later generators can depend on the variables that are
introduced by earlier generators.
> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
Using a dependent generator, we can define a function that
concatenates a list of lists:
flatten :: [[Int]] -> [Int]
flatten xss = [x | xs <- xss, x <- xs]
> flatten [[1,2],[3,4],[5]]
[1,2,3,4,5]
List comprehensions can use guards to restrict the values
produced by earlier generators.
[x | x <- [1..10], even x]
45
Typ, typy v haskellu, statis-vs dynamic, strongly, weekly...
Typ - mnozina elementu ktere nejak mezi sebou logicky souvsi, definuje se set of elements a operace nad nimi
Static - pri compile
Dynamic - pri runtime
Strongly - operace pouze mezi stejnymi typy
Weekly - operace povolene i pro smisene typy
Treba 5*"a" = aaaaa
46
Typy funkci v haskellu
Apriori vsechny defauktne v curry verzi:
foo :: Int -> Int -> Int -> Int
znamena:
(((foo Int) Int) Int) -> return Int
f :: Int -> Int -> Int -> Int
f x y z = x + y * z
Muzu i predem stanovit, ktery parametr bude nemenny:
f 5 :: Int -> Int -> Int
f 5 = 5 * Int * Int -> return Int
47
Polymorfismus v Haskellu
Funkce je polymorfni kdyz pokud je pouzitelna pro ruzne typy - pracuje s ruznymi typy hodnot (treba je funkcni pro string, pro int atd...)
1. Parametricky
- funkce je naprosto nezavisla na typu parametru
- tedy funkce porad dela to samy nezavisle na vstupnch parametrech
- treba length lst - nezavisle jestli je to list boole, nebo list integeru, nebo string...
- nebo treba car -> vzdy vrati prvni prvek nezavisle na typu
- nebo treba foo(cokoliv) -> return 5 -> vzdy vrati 5 nezavisle na parametrech...
- tedy funkce je parametricky polymorfni p .t.k. dela to samy nezavisle na typu vstupnich argumentu
(define (identity x) x)
A parametric polymorphism is a function using a type variable
in its type declaration, e.g.
len :: [a] -> Int // TADY UVADIM ABSTRAKTNI TYP
len [] = 0
len (_:xs) = 1 + len xs
2. Dynamicka (ad hoc), pretizeni
- nekolik definic ty same funkce podle typu parametru
- definuju print treba pro int, pro string, pro bool atd..
- vetsinou implementuju nejakou podobnou logiku, ale v zavislosti na typu se ma funkce chovat jinak
- tedy ji pretizim nekolikrat
class Show a where
show :: a -> String
instance Show Int where
show x = intToString x
instance Show Bool where
show True = "True"
show False = "False"
48
Ad hoc polymorfismus a typove tridy
Ad hoc polymorfismus (funkce) jsou implementovany pmoci tzv Type Class:
- type class definuje mnozinu funkci ktere muzou mit ruznou pretizenou implementaci v zavislosti na typech dat v argumetnech
Pokud chceme pouzuvat jednu funkci pro ale ruzne typy, musime predem definovat Type Class, ktery toto podporuje (neco jako interface) a v nem musime parametrizovat tuto funkci.
Treba chci srovnavat promenne pomoci ==:
Predem musim zadefinovat tuto operaci pro ruzne typy, jak by se to melo chovat nezavisle na parametru, a to zabalim do Type Class Eq -> objekty, ktere pak dedi od tohoto Eq, muzou byt porovnavany
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
Zakladni type class:
- Eq, Ord, Num, Show, Fractional...
- tedy porovnatelne objekty, usporadatelne, ciselne operace, print...
Tedy pokud ve funkci budu pouzivat treba porovnani a print, musim to deklarovat v hlavicce funkce, ze tam musim pouzit vstupni arguemtny Ord a a Show a:
foo :: Ord, Show a => a -> a -> Boo
49
Zavedeni vlastniho prejmenovaneho typu v Haskellu, tzv parametrickeho typu
type MyName = cokoliv
- umoznuje to prehledne zavedeni novych pseudotypu
treba:
type Pos = (Int,Int)
left :: Pos -> Pos
left (x,y) = (x-1,y)
Je to jakasi odlehcena struktura
Like function definitions, type declarations can also have
parameters. With type Pair a = (a,a) we can define:
mult :: Pair Int -> Int
mult (m,n) = m*n
copy :: a -> Pair a
copy x = (x,x)
Tedy zavedeni typu nemusi byt typove
- treba Pair muze byt par jakyhkoliv typu
Muze byt nested, ale ne rekurzivni
50
Zavedeni kompletne noveho datoveho algebraickeho typu
data Answer = YES | NO | UNKNOWN
- Answer - type constructor
- yes, no, unknows - data constructor
Toto je zadefinovany zcela novy nezavisly typ
- muzu ho pouzivat jako typ ve funkcich:
flip :: Answer -> Answer
flip Yes = No
flip No = Yes
flip Unknown = Unknown
kde pouzivatm pattern matchiing na hodnoty noveho typu
Novy typ muze mit parametry:
data Shape = Circle Float | Square Float Float
- tedy rika mi to "zavadim novy datovy typ Shape, ktery je BUD Circle s vlastnosti Float (diameter) NEBO je to Square se straanami
- je to neco jako dedeni podle typu
square :: Float -> Shape
square n = Rect n n
- konstruktor na square
area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect x y) = x * y
51
Maybe data
Jeden z nejpouzivanejsich typu v Haskellu, umoznuje safe operace
data Maybe a = Nothing | Just a
allows defining safe operations.
safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv m n = Just (m `div` n)
safehead :: [a] -> Maybe a
safehead [] = Nothing
safehead xs = Just (head xs)
Tedy je to jakysi vbudovany if v definici typu, ze pokud se neco pokazi, vrat Nothing, jinak tu hodnotu
52
Records v Haskellu
Neco jako struktura/objekt
Tedy je to defincie noveho datoveho typu, ale jeho polozky muzu pojmenovat pro prehlednost:
data Person = Person { firstName :: String,
lastName :: String,
age :: Int,
phone :: String,
address :: String }
Pak mam automaticky get-atribut funcke na vsechny pojmenovane polozky
53
Rekurzivni datovy typ
Takovy datovy typ, ktery v definici vyuziva sam sebe:
data List a = Nil | Cons a (List a)
- tedy list je bud prazdny, nebo nejaky prvek spolu se zbytkem...
- a je abstarktni typ, neurcity zatim, nepotrebnujeme konkretne
Pokud chceme pridat vlastnost treba printable, tak to musime specifikvoat dedicnosti od datove tridy Show:
data List a = Nil | Cons a (List a) deriving Show
Nebo pokud sami chceme implementovat jak se bude na typ zobrazovat, muzeme to naimplementovat jako kdybych pretezoval funkci interfacu Show:
instance Show a => Show (List a) where
show lst = "<" ++ disp lst ++ ">" where
disp Nil = ""
disp (Cons x Nil) = show x
disp (Cons x l) = show x ++ ", " ++ disp l
54
Definice aritmetickeho vyrazu pomoci datoveho typu
data Expr a = Val a | Add (Expr a) (Expr a) | Mult (Expr a) (Expr a)
tedy vyraz muzu treba reprezentovat jako basic hodnotu, nebo scitanim nebo nasobenim vyrazu (ktere musim rekurzivne prozkoumat a vyresit zvlast)
tedy rekurzivni funcke eval je postupne prochazi do hloubky podle pattern amtchingu a evaluuje od nejprimitivnejsi urovne:
eval :: (Num a) => Expr a -> a // musim pridat Type Class Num, protoze pouzivam+*
eval (Val x) = x // vrat basic hodnotu
eval (Add x y) = eval x + eval y // rekurzivne vyhodnot x a pricti k tomu rekurzivni y
eval (Mul x y) = eval x * eval y
Pro tisk:
nstance (Show a, Num a) => Show (Expr a) where
show (Val a) = show a
show (Add e1 e2) = "(" ++ show e1
++ " + "
++ show e2 ++ ")"
show (Mul e1 e2) = "(" ++ show e1
++ " * "
++ show e2 ++ ")
55
Vsechny typove tridy v haskellu
Show, Read
Eq -> Ord -> Real, Num, Fractional, Floating, Integral -> Enum -> RealFloat
Foldable
Semigroup -> Monoid
Functor -> Applicative -> Monad -> Traversable
56
Read type class v Haskellu
Opak Show -> tedy polymorficka funkce na nacitani vstupu stringu a parsovani hodnot podle hlavicky funkce
57
Functor
Functor nam umoznuje mapovat funkce na struktury i slozitejsi nez jen list, treba mapovani funkce na strom
map :: (a -> b) -> [a] -> [b] // map bere funkci a pole, vraci novy pole
treeMap :: (a -> b) -> Tree a -> Tree b // chceme stejnou logiku pro strom
Functor je typova trida ktera nam to umoznuje - implementuje pomoci fmap:
class Functor f where
fmap :: (a -> b) -> f a -> f b // bere funkci a aplikuje na strukturu
- f je "context" functorialni
- tedy f je "strukturalni kontext" - list, Maybe...
instance Functor [] where
fmap = map
- functor pro list (neboli fmap verze pro list) je obycejny map!!!
Definuju treba strom:
data Tree a = Tree a [Tree a] deriving Show
tree :: Tree Int
tree = Tree 1 [Tree 2 [Tree 3 []], Tree 4 []]
Pokud na nej chci aplikovat map, tak moje Tree musi "implementovat rozhrani" Functor:
instance Functor Tree where
fmap f (Tree x []) = Tree (f x) []
fmap f (Tree x ts) = Tree (f x) (map (fmap f) ts)
- tedy pokud zavolam fmap na Tree, tak pokud jsem v listu -> aplikuj na nej tu funkci
- pokud nejsem v listu -> aplikuj na aktualni uzel a rekurzivne aplikuj dal...
Obecne Functor se da zapsat sablonovite jako:
f a -> (a -> b) -> f b, (a->b) je funkce, f je kontext struktury, list Maybe
bere zabalenou hodnotu, uvnitr aplikuje funkci a vraci zpet zabalenou hodnotu
musim sam zadefinovat jak se bude fmap chovat
58
Pouziti Functor pri spojeni padajiich vypoctu
Treba mam safe-funkce getHead a getTail.
Jejich zretezeni muzu provadet pomoci andThen funkce, ktera je Functor pracujici s Maybe objekty
- tedy bere Maybe objekt, funkci, ktera nejaky objekt a prevede na Maybe a, a vrati Maybe b
Maybe a -> (a -> Maybe b) -> Maybe b
andThen je tedy safe, protoze v pripade, ze do ni nic neprislo -> vrat Nothing, jinak aplikuj funkci jako safe:
andThen :: Maybe a -> (a -> Maybe b) -> Maybe b
andThen Nothing _ = Nothing
andThen (Just x) f = f x
safeSecond :: [a] -> Maybe a
safeSecond xs = safeTail xs `andThen` safeHead
Maybe je obecne instanci Functoru -> protoze splnuje jeho logiku
- vezme objekt, funkci a vrati novy objekt v zavislosti na Maybe/Nothing
- reprezentuje to chybne vypocty potencialni
59
IO
V Haskellu je většina kódu čistě funkcionální – stejný vstup → stejný výstup, bez vedlejších efektů.
-Ale programy potřebují:
-číst a psát na konzoli,
-číst ze souboru,
-generovat náhodná čísla,
To jsou vedlejší efekty, a v Haskellu se tyto efekty přesně modelují pomocí typu IO.
main :: IO ()
main = putStrLn "Hello, world!"
- menit tedy okolni stav sveta (World) muzeme pouze v ramci jedine funkce main a to ma vracet IO()
což říká: „Tento výpočet provede nějaký efekt a vrátí jednotkovou hodnotu
>>= je klíčový operátor monád. Má typ:
(>>=) :: IO a -> (a -> IO b) -> IO b
Máme IO-akci, která vrací a.
Dáme jí funkci, která z toho a vytvoří novou IO-akci.
Výsledkem je spojená IO-akce.
- slouzi to k predani hodnoty z predchozi funkce do nasledujici -> zretezeni
getLine >>= \name ->
putStrLn ("Hello, " ++ name)
- getline nacte vstup a ulozi do name, nasledne se zavola putStrLn
Do-notace
Syntaktický cukr pro práci s monádami. Místo:
getLine >>= \name -> putStrLn ("Hello, " ++ name)
Muzu napsat citelnejsi:
main = do
name <- getLine
putStrLn ("Hello, " ++ name
x <- action znamená: spusť action, výsledek ulož do x.
Každý řádek je postupná akce, kterou Haskell zřetězí přes >>= pod kapotou
60
Monada
class Applicative m => Monad m where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
>>=: řetězení efektů (hlavní operátor)
return: zabalí čistou hodnotu do kontextu monády (např. return 3 :: IO Int)
instance Monad Maybe where
Just x >>= f = f x
Nothing >>= _ = Nothing
return = Just
Monada je typova trida (specialni druh functoru) ktera nam umoznuje retezit monadicke operace pomoci operatoru >>= (bind)
Monadicky map:
umoznuje pouzit IO funkci na kazdy prvek seznamu a vrati IO seznam vysledku:
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
askName :: IO String
askName = do
putStrLn "What is your name?"
getLine
main = do
names <- mapM (\_ -> askName) [1..3]
print names
- trikrat se zepta na jmeno, vysledek ulozi do seznamu jmen a vytiskn
61
Applicative
Je Functor, ktery navic do kontextu (Maybe, Either, List, Io...) zabali i funkci, kterou chceme mapovat na elementy.
Applicative :: f (a->b) -> f a -> f b
Každý krok:
vezme funkci (nebo mezifunkci) v kontextu,
aplikuje ji na další argument v kontextu pomocí <*>,
a vrátí výsledek zase v kontextu.
Pokud se některý krok nepovede (např. Nothing, chyba, prázdný seznam), celý výpočet končí s výsledkem v daném kontextu.
isntance Applicative Maybe where
pure = Maybe // zakladni vraceny typ
Just f <*> (Just a) = (Just f a)
Just f <*> Nothing = Nothing
1. Tedy muzu volat jako:
Just (+1) <*> (Just 1) ==> 1 + 1 = 2
Just (+1) <*> (Just 1) <*> (Just 2) ==> 1 + 1 = 2 ==> 2 + 1 = 3
- tedy v kazdem kroku jsem aplikoval +1 a jestli mi nevylezlo Nothing -> pokracuju
2.
Just (*) <*> (Just 2) ==> ERROR, vyslo mi totiz 2*nic, ceka to tedy na dalsi vstup:
Just (*) <*> (Just 2) <*> (Just 3) ==> Just (*2) <*> (Just 3) ==> 2*3 = 6
3. Applicative umí funkci s více argumenty aplikovat postupně:
pure (\x y z -> x + y + z) <*> Just 1 <*> Just 2 <*> Just 3
- tedy vezme nejdriv prvni arguement, pak druhy, pak treti a az pak na ne posle tu funkci...
4. (*2, *3) <*> [1, 2, 3, 4]
==> [2, 4, 6, 8, 3, 6, 9, 12]
- tedy aplikovalo to dve funkce na jedno pole
Hodi se jako:
1. Mapovani funkce, ktera ma kontext
2. Postupne safe mapovani kontextove funkce na kontextove hodnoty po jednom
3. Mapovani vice vstupove (n-arni) funkce
4. Treba mavopani vice funkci na jeden vstup
62
🧠 Flashcard: Functor, Applicative, Monad, Alternative pro Parser
🔹 Functor
fmap :: (a -> b) -> Parser a -> Parser b
Umožňuje transformovat výsledek parseru funkcí.
🧪 fmap (=='c') item → načte znak a vrátí True, pokud je to 'c'.
🔸 Applicative
pure :: a -> Parser a, (<*>) :: Parser (a -> b) -> Parser a -> Parser b
Umožňuje kombinaci více parserů s funkcí více argumentů (n-ární mapování).
🧪 pure (/=) <*> item <*> item → porovná dva znaky.
🔹 Monad
(>>=) :: Parser a -> (a -> Parser b) -> Parser b
Umožňuje řetězení parserů, kde další parser závisí na výsledku předchozího.
🧪 item >>= \c -> if c == 'a' then item else return ' ' → načte druhý znak jen pokud první je 'a'.
🔸 Alternative
empty :: Parser a, (<|>) :: Parser a -> Parser a -> Parser a
Umožňuje parser s volbou (fallback při selhání).
🧪 item <|> return 'x' → buď načti znak, nebo vrať 'x'.
⚖️ Rozdíly:
Instance Co dělá Závislost na výsledku?
Functor Transformuje výsledek ❌
Applicative Kombinuje parsery bez závislosti ❌
Monad Řetězí parsery závislé na výsledku ✅
Alternative Umožňuje volbu mezi parsery ❌
63
Functor, Applicative, Monada z pohledu krabicek
1. Functor
- mam rozbalenou funkci, ale zabalenou hodnotu v krabicce
- vyndej hodnotu z krabicky
- posli na ni rozbalenou funkci
- vysledek vrat do krabicky
class Functor where
fmap :: (a->b) -> f a -> f b
instance Functor MyClass where
fmap f (Myclass a) = MyClass (f a)
-- zbytek rekurzivni logiky pripadne...
2. Applicative Functor
- mam zabalenou funkci v krabice a hodnotu v krabicce
- z krabicek vyndam funkci a hodnotu
- poslu funkci na hodnotu
- vysledek vratim do krabicky
- funguje pomoci Functor
class Functor where
<*> :: f(a->b) -> f a -> f b
instance Applicative Myclass where
pure = basic MyClass
MyClass func <*> (MyClass a) = (MyClass func a)
-- zbytek logiky pripadne
3. Monada
- mam zabalenou hodnotu v krabice a cistou rozbalenou funkci
- vynda hodnotu z krabicky a poslu na ni cistou funkci rozbalenou
- vratim hvysledek do krabicky
- rozdil oproti Functor je, ze funkce NEMUSI pocitat se zabalenou hodnotou
- mohu vysledek preposilat do dalsich funkci pomoci bind
- funguje pomoci Applicative a Funcotr, oba musi byt definvoany v kodu
class Monad where
>>= :: m a -> (a -> m b) -> m b
instance Monad MyClass where
Nothing >>= func = Nothing
MyClass a >>= func = func a
- uz nemusim vysledek zabalovat do MyClass, protoze Monad automaticky zabaluje vyslednou hodnotu do monady - tedy vraci do krabicky, ze ktere to vyndal sam, nemusim to resit ja v hlavicce
64
Stavovy vypoce
Takovy, ktery pracuje s nejakym vedlejsim stavem pro svuj vypocet
Co je stavový výpočet?
Stavový výpočet je způsob, jakým funkcionální programovací jazyky, jako je Haskell, řeší změny stavu a interakci s okolím. V klasických imperativních jazycích jako Java nebo Python je běžné používat globální proměnné pro uchovávání stavu a měnit je pomocí příkazů.
V Haskellu, kde je důraz na čistotu funkcí (tj. funkce nemění stav mimo svůj kontext), se stav řeší pomocí monád. Monády jsou struktury, které umožňují programátorovi manipulovat se stavem a provádět efektivní operace, jako je čtení ze vstupu, zápis do souboru nebo komunikace se vzdáleným serverem.
65
State monade
Monada umoznujici stavovy vypocet tak, ze oddelime stav od samotneho vypoctu, tedy bez toho bychom promennou stavu museli porad predavat do funcke jako arguemtn - zabira zbytecne prostor a pamet. Misto toho nad objekty budeme operavoat jako nad stavy, ktery uz v sobe zabaluji parametr stavu, tedy nemusiem do funkci posilat nejaky citac, pouze pracujeme s objekty jako State Monade, kde standardni knihovna nam uz poskytuje rozhrani jako get, put, update... aniz bychom resili manualne zmeny stavu
zavedeme:
newtype State s a = S { runState :: s -> (a, s)}, kde S je typ stavu a a je vysledek vypoctu
Potom stavovy vypocet zavisly na hodnote b a stavu s je:
st :: b -> State s a
Haskell poskytuje několik užitečných funkcí pro práci se stavem:
state :: (s -> (a, s)) -> State s a – vytvoří stavový výpočet z funkce.
evalState :: State s a -> s -> a – spustí výpočet a vrátí výsledek.
execState :: State s a -> s -> s – spustí výpočet a vrátí nový stav.
get :: State s s – získá aktuální stav.
put :: s -> State s () – nastaví nový stav.
modify :: (s -> s) -> State s () – upraví stav pomocí funkce.
Priklad jednoducheho operovani se State monad pomoci get a put()
import Control.Monad.State
-- Definice stavového typu
type ShoppingCart = [String]
-- Přidání položky do košíku
addItem :: String -> State ShoppingCart ()
addItem item = do
cart <- get
put (item : cart)
-- Odstranění položky z košíku
removeItem :: String -> State ShoppingCart ()
removeItem item = do
cart <- get
put (filter (/= item) cart)
-- Příklad použití
main :: IO ()
main = do
let actions = do
addItem "Mléko"
addItem "Chléb"
removeItem "Chléb"
print $ execState actions [] -- Vytiskne ["Mléko"]
Treba operace nad kosikem, ocislovani listu stormu, generovnai nahodnych cusel...
66
Generovani nahodnych cisel
Obecne to neni cista funkce, protoze by mela vracet porad ruzny vysledek nezavisle na okoli
Haskell to resi pomoci pseudorandom generatoru nahodnych cisel s pouzitim state monade
Je to determenisticky a cisty pristup
1. Bud manualne pocitame seed a novou hodnotu
Pseudorandom generators allow generating random values
based on an initial seed.
f (seed) = (x, newseed) where x is a random value
rand100 :: Int -> (Int, Int)
rand100 seed = (n, newseed) where
newseed = (1664525 * seed + 1013904223)
`mod` (2^32)
n = (newseed `mod` 100)
2. Knihovna System.Random generuje pomoci geneatoru StdGen, pomoci funkce mkStdGen vytvari generatory novych seeds. Novou hodnotu pak dostaneme funkci:
randomR, kam posleme generator a cislo, vrati to nove cislo a novy generator...
3. Nebo pomoci state monade
67
Semigroup
Mnozina prvku S s binarni operaci <*> takova, ze je asociativni:
(x*y)*z = x*(y*z)
- tedy nezalezi na poradi
class Semigroup a where
(<>) :: a -> a -> a
-- proste bere dva prvky a vraci novy
instance Semigroup [a] where
(<>) = (++)
-- treba pro list
68
Monoid
Monoid je semigrupa spolecne s neutrlnim konstantnim prvkem:
x*n = x = n*x
treba realna cisla s se scitanim a 0:
// append prazdny list
class Semigroup a => Monoid a where
mempty :: a
mappend :: a -> a -> a
mappend = (<>)
instance Monoid [a] where
mempty = []
-- treba pro list
Je to typova trida ktera abstrahuje operace agregace s neutralnim prvkem
69
Sum a Prod
Pomoci SemiGroup a Monoidu muzeme definovat novy typ jao Sum nebo Product, ktery umi vratit novy Sum jako soucet dvou Sum, neutralni produkt = 0, nebo Product jako nasobeni, kterdy bere dva Prod a vraci novy Prod jako soucin arguemtn, netrualni prvek = 1
70
Any a All
Dalsi vyuziti Semigroupy a Monoidu, kdy definujeme nove typy Any a All a dedime od Semigroup (Any x Any y) = Any (x || y)... a Monoidu (mempty = Any False)
Analogicky pro All
71
Foldable
Type class ktery generalizuje foldl/r operace
Rika mi "pokud tuto tridu definujes jako foldable, tak ji muzes projit a nejak slozit pomoci nejake operace"
- povoluje to klasicky fold i na slozitejsi struktury nez jen llist, treba kdyz chci slozit strom
Musi se implementovat 3 funkce:
class Foldable t where
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
foldl :: (b -> a -> b) -> b -> t a -> b
foldMap :: Monoid m => (a -> m) -> t a -> m
Převádí každý prvek na monoidní hodnotu a všechny je skládá (<>) dohromady.
toList :: Foldable t => t a -> [a]
null :: Foldable t => t a -> Bool
length :: Foldable t => t a -> Int
elem :: Eq a => a -> t a -> Bool
maximum :: Ord a => t a -> a
minimum :: Ord a => t a -> a
sum :: Num a => t a -> a
product :: Num a => t a -> a
To znamená, že pro jakoukoli strukturu, která je Foldable, získáváme všechny tyto funkce zdarma, pokud správně implementujeme foldMap nebo foldr.
72
Lambda calculus obecne
Formalni nejjednodussi univerzalni programovaci jazyk zavedeny Alonzo Churchem v roce 1930
- ma pouze definice lambda funkci
- redukce a prejmenovavani pravidel (alfa-konverze, beta-redukce)
Zavedl se jako nastroj
- je turing complete, tedy pokud muj programovaci jazyk jde prepsat do lambda kalkulu tak je turing complete
slouzi jako zakladni stavebni baze pro vsechny programovaci jazyky a hlavne funkcionalni
- ma pouze anonymni (nepojmenovane funkce)
73
Gramatika lambda kalkulu
Syntax je odvozen pozue tremi pravidle
expr = var | function | application
function = lambda var . expr
application = expr expr
Tedy treba:
λx.body -> znamena zavedl jsem funkci, ktera bere jeden arguemtn a vykonava prikazy z body. Je to analogicky jako:
(lambda (x) body)
Na to mohu poslat vstupni arguemtny:
(λx.body)y -> to znamena, ze to ty funkce poslu vstupni arguemtn y (aplikuju)
je to jako:
((lambda (x) (body) y), kde y je uz konkretni hodnota, nebo cokoliv jineho.
Hlavni myslenkou je dosazovani argumentu do funkci
λx.(λy.xyx)z -> toto znamena, ze zavedl jsem funkci, ktera ceka na jeden arguemtn. Dosadim to z. Funkce vezme telo "λy.xyx" a dosadi tam z a zacne vykonavat...
74
Abstraktni Syntakticty Strom lambda kalkulu
1. Aplikace (tedy obycejne expr1 exp2, treba (λy.body)x) se znaci @ a je to vetvici bod kodu
2. Uzly muzou byt bud λy
3. Nebo uz samotne hodnoty v listech
Sestavuju rekurzivne od nejvetsi priority az dolu do mensich podvyrazu
75
Volna/vazana promenna lmabda\kalkulu
Volna - neni vazana zadny λ funkci po ceste nahoru
Vazana - takova, ktera cestou anhoru ma alespon jednu λ se svym jmenem
Vazane promenne kdykoliv muzu prejmenovat, tedy
λy.xyx je totez jko λz.xzx -> nemeni to smysl
76
Uzavreny/otevreny vyraz
1. Uzavreny vyraz (COMBINATOR)
- takovy, ktery nema volne promenne promnenne
2. Oteverny - ma volne promenne
77
Alfa-conversion
Proces prejmenovavani vazanych promennych
78
Beta-reduction
Semanticky proces redukce vyrazu na zakaldni tvar, je to postupne aplikovani funkci na argumenty, dokud nemame vyslednou nejjednodussi zakaldni hodnotu, kterou uz nejde redukovat
Redex - vyraz, ktery jde jeste rozlozit, treba (λy.xyx)z, protoze je to aplikace funkce na z, tedy tam to z mohu primo dosadit a dostanu jednodussi tvar: xzx, toto uz nejde rozlosit -> vysledek hotovo
Beta-redukce se provadi dosazenim arguemtnu do vsech VOLNYCH VYSKYSTU parametru funkce za vstupni arguemtn. Tedy:
((λx.body)arg) → body[x := arg]
- tedy vezmu telo funkce a vsechny VOLNE vyskyty x nahradim vstupnim parametrem.
je to analogicky jako pri parametricke funkce:
def add1(x):
return x+1
- kde x je volna promenna definovane funcke a ja do ni posilam vstupni arguemtny
(λx.x)(λy.y) →vstupni parametr je jina funkce, to ale nevadi, proste ji dosadim za volny x: x[x := (λy.y)] ≡ (λy.y)
λx.x(λx.x))y →(x(λx.x))[x := y] ≡ y(λx.x)
79
Cemu se vyhnout pri beta-konverzi?
Pri dosazovani nesmi dojit k tomu, ze volna promenna by se stala vazanou. Treba:
(λx.(λy.xy))y -> bych do tela funkce zacal dosazovat y na misto x:
- (λy.xy)[x := y] -> (λy.yy)
- Y SE MI ALE STALO VAZANYM, PRED TIM BYLO VOLNE!
Tento krok je nutne vzdy zkontrolovat a v takovem pripade pomoci alfa-konverze prejmenovat vstupni argument na neco jineho:
treba
1. (λx.(λy.xy))y -> alfa konverze y:=z ==> (λx.(λy.xy))z
2. Beta redukce: (λy.xy)[x := z] -> (λy.zy)
OK -> NOVA PROMENNA ZUSTALA VOLNA
80
Evaluacni strategie beta-kalkulu
Podobne jako eager a lazy evaluace arguemtnu funkci ve Scheme
1. Lazy - nejdriv se zavola samotna funkce a pak az se dovyhodnoti argumenty
- tzv NORMAL-ORDER - vzdy redukuje nejnizsi nejlevejsi redex
- tedy ve stromu jdu co nejvic doleva
- neboli ve vyrazu jdu proste zleva dorpava
- ve stromu je to nejlevejsi @
2. Eager - nejdriv se vyhodnoti vsechny vstupni arguemtny, pak az se zavola samotna funcke na redukovane hodnoty
- tzv APPLICATIVE ORDER - leftmost-inner msot, tedy jdu po vstupech do funkce nejdriv, pak az funkci volam
- ve stromu je to "nejpravejsi levy @", tedy v levem podstrome nejvic vpravo @
81
Normal-form vyrazu lambda-kalkulu
Takovy vyraz, ktery uz nema redexy -> tedy je zcela redukovan na zakladni tvar
Proces hledani normalni formy pomoci beta-redukce nemusi nikdy skoncit v zavislosti na evaluacni strategii a samotnem vyrazu, treba nekonecny loop
(λx.xx)(λx.xx) →β (λx.xx)(λx.xx) // nikdy neskonc
82
Church-Rosser Theorems
1. Normalni forma je jednoznacne urcena
- tedy pokud jsem nasel normalni formu vyrazu (nezavisle na postupu) -> pak je to jedina normalni forma
2. Normalni poradi (normal order) evaluacni strategie nam VZDY najde normalni formu
- applcative order nemusi skoncit
83
Identita, T, F, negace, AND, OR, 0, 1, 2, 3, ...
Identita: I ≡ (λx.x), funkce ktera vraci vstup
True: T ≡ λxy.x, vraci prvni vstup
False: F ≡ λxy.y, vraci druhy vstup
AND: ∧ ≡ λxy.xyF, za X a Y dosadim T/F
- TTF ==> prvni T vraci 1. vstup, coz je y=T, takze to celkove vraci T
- FTF ==> prvni F vraci 2. vstup, coz je default=F, takze to celkove vraci F
- TFF ==> prvni T vraci 1. vstup, coz je y=F, takze to celkove vraci F
OR: ∨ ≡ λxy.xTy
- analogicka myslenka jako AND
- staci alespon jeden x,y=T ==> vraci T
Negace: ¬ ≡ λx.xFT
- kombinace FT za sebou neguje vstupni X
Cisla:
0 ≡ λsz.z ≡ F
1 ≡ λsz.sz
2 ≡ λsz.s(sz)
3 ≡ λsz.s(s(sz))
- tedy cislo n je n-krat aplikovani s na z (s,z jsou nezavisle pro me hodnoty, jde jen o jejich pocet, ne hodnoty)
- tedy cislo je kolikrat aplikuju s na nejaky z
Inkrement by one: S ≡ λwyx.y(wyx)
- tedy beru predchozi cislo wyx a pridavam k tomu jeste jednu aplikaci y ==> ++1
Scitani - x + y - znamena k y pricti x-krat inkrement jednicky
- tedy je to x-krat aplikace inkrement_by_one k y
Test na nulu: Z ≡ λx.xF¬F
- dosadim za x=0, nebo n>0
- 0 reprezentuje F, takze by to bylo: FF¬F -> prvni F vraci druhy vstup => negace F => true, tedy je TRUE ze x=0 (tady chcu negovat vysledek, protoze mi jde o "USPESNE" provedenou podminku
- pokud tam dam cokoliv jinyho nez 0, tak je to TF¬F => dava celkove False, x NENI 0
84
Y-combinarot, rekurze v lambda kalkulu
Rekurze je zprostredkovana tzv Y-kombinatorem:
Y ≡ λy.(λx.y(xx))(λx.y(xx))
- tedy funkce, ktera bere jeden parametr a jen se duplikuje v podstate
- Y ≡ λy.(λx.y(xx))(λx.y(xx))z ==> (λx.z(xx))(λx.z(xx))
- pokud dosadim dalsi parametr -> dostanu to stejny akorat s jinym pojemnovanim...
- vola sama sebe
