Fold

Question 1

Co je to Celozrnné (wholemeal) programovanie?

Answer 1

znamená myslieť vo veľkom (Ralf Hinze), t.j. namiesto:
* cesty vidieť celý graf
* konkrétneho riešenia vyvinúť rámec pre riešenie problémov
* s elementami pracovať s celým zoznamom

Question 2

opis foldr

Answer 2

foldr :: (a->b->b) -> b -> [a] -> b
slide 3

Question 3

aky prvok berie ako prvy foldr?

Answer 3

posledny, teda ide akoby od konca (nejde pouzit na nekonecne)

Question 4

opis foldl

Answer 4

foldl :: (b->a->b) -> b -> [a] -> b
slide 7

Question 5

Aky prvok berie ako prvy foldl?

Answer 5

prvy

Question 6

Kedy je trojica M = (S, ⊗, e) monoid?

Answer 6

S={x1,x2,…} je neprázdna množina,
⊗ : S × S → S je asociatívna operácia na množine S,
e ∈ S je neutrálny prvok (zľava aj sprava) vzhľadom na ⊗.

Question 7

Vyslov prvu vetu o dualite foldr a foldl

Answer 7

slide 10

Question 8

Vyslov 2 vetu o dualite foldr a foldl

Answer 8

slide 11

Question 9

Vyslov 3 vetu o dualite foldr a foldl

Answer 9

slide 12

Question 10

definuj foldr podla foldl

Answer 10

foldr f e xs= foldl (flip f) e (reverse xs)

Question 11

Daj priklady dalsich identit pre foldr a foldl

Answer 11

slide 13

Question 12

Naco su foldr1, foldl1?

Answer 12

Ked nevieme zvolit e, napr pri hladani maxima. Ale nepracuje na prazdnom zozname

Question 13

Co robia funkcie scan?

Answer 13

Funkcie scan sú ako zodpovedajúce funkcie fold, ale vracajú aj zoznam všetkých medzivýsleldkov (akumulátorov).

Question 14

co robi unfold?

Answer 14

unfoldr :: (b->Maybe (a, b))->b->[a]

Question 15

aky je rozdiel medzi foldr, foldl a foldl’?

Answer 15

foldr nepoužíva chvostovú rekurziu
foldl má obrovské množstvo nedokončených výpočtov na halde
foldl’ - chvostová rekurzia s priebežným vyhod. akumulátora

Question 16

Kedy použiť foldr?

Answer 16

pokiaľ f je nie je striktná (napr. (&&), (:)) - je lenivá na svojom druhom argumente

transformácia nekonečných zoznamov

Question 17

Kedy pouzit foldl’?

Answer 17

pokiaľ je funkcia f striktná (napr. (+))