--------------------------------------------------
predmet: IB015 Úvod do funkcionálního programování
semester: jaro 2012
prednášajúci: doc. RNDr. Jiří Barnat, Ph.D.
--------------------------------------------------
typ: zaverečná skúška, termín00 (17.05.2012)
verejná: nie
zdroj: opravujuci
--------------------------------------------------

Príklad 01 (-2/0/10)
Bezparametrová ("pointfree") definice funkce zwf x = zipWith x [1..3] [True, False, False] je
a) zwf = (flip zipWith) [1..3] [True, False, False]
b) zwf = flip ((flip zipWith) [1..3]) [True, False, False]
c) zwf = ((flip zipWith) . flip) [1..3] [True, False, False]
d) zwf = zipWith (flip . flip) [1..3] [True, False, False]
e) žádná z uvedených možností

Príklad 02 (-2/0/10)
Jaká je časová složitost výpočtu funkce prod3 s vzhledem k velikosti jejího parametru, t.j. k délce seznamu s?

drop :: Int -> [a] -> [a]
drop 0 z = z
drop _ [] = []
drop n (x:s) = drop (n-1) s

prod3 :: [Integer] -> Integer
prod3 [] = 1
prod3 (x:y) = x * prod3 (drop 2 y)

a) konstantní
b) logaritmická
c) lineární
d) kvadratická
e) žádná z uvedených možností

Príklad 03 (-2/0/10)
Vstup-výstupní akce

do f <- getLine
   s <- getLine
   appendFile f (s ++ "\n")

je ekvivalentní akci:
a) \f -> getLine >> \s -> getLine >> appendFile f (s ++ "\n")
b) getLine >>= (\f -> getLine) >>= (\s -> appendFile f (s ++ "\n"))
c) getLine >> getLine >>= (\f s -> appendFile f (s ++ "\n"))
d) getLine >>= \f -> getLine >>= (appendFile f) . (++"\n")
e) žádná z uvedených možností

Príklad 04 (14)

Príklad 05 (14)
Intensionálním zpusobem definujte seznam všech kladných lichých čísel takový, že každé liché číslo x se v seznamu vyskytuje právě tolikrát, kolik je zbytek po dělení čísla x číslem 12 (pro výpočet zbytku po dělení lze použít funkci `mod`).

Príklad 06 (2+4+12)
Stromovou rekurzivní datovou strukturu lze v programovacím jazyce Haskell definovat následovně:

data Tree a = Leaf a | Branch [Tree a] deriving (Show, Eq)

a) Identifikujte typové konstruktory ve výše uvedené definici typu a určete jejich aritu.
b) Uveďte hodnotu typu Tree Int, která obsahuje použití všech datových konstruktoru použitých pro definici typu Tree a
c) Definujte funkci sucheVetve, která pro zadanou hodnotu definovaného typu vrátí počet větví, které jsou bez listí (t.j. počet výskytu Branch []).*** priklad 01 ***

--------------------------------------------------

*** priklad 01 ***

najjednoduchsie je previest zadany vyraz do tvaru podobnemu na moznosti, t.j. na pointfree a porovnavat,
ktory je s nim ekvivalentny

\x -> (zipWith x [1..3]) [True, False, False]
\x -> flip zipWith [1..3] x [True, False, False]
\x -> flip (flip zipWith [1..3]) [True, False, False] x
flip (flip zipWith [1..3]) [True, False, False]

B

*** priklad 02 ***

s = [0,1,2,3,4,5,6]
prod3 s = 0 * prod3 [3,4,5,6] = 0 * 3 * prod3 [6] = 0 * 3 * 6 * prod3 [] = 0 * 3 * 6 * 1

drop 2 s
    - konstantne vzhladom k s
prod3
    - urobi sucin vsetkych prvkov zo zoznamu, ktore su na poziciach
    - 3n + 1
    - kazdy krok konstantny
    - hlbka rekurzie linearne zavisi na dlzke zoznamu
    - dohromady je teda prod3 linearne voci dlzke s

C

*** priklad 03 ***

prepisovanie je vcelku jednoduche a robi sa podla nasledovnych pravidiel:
    do var <- akcia             akcia >>= \var ->
    do akcia                    akcia >>

getLine >>= \f -> getLine >>= \s -> appendFile f (s ++ "\n")

\s -> appendFile f (s ++ "\n")
appendFile f . (++"\n")

*** priklad 05 ***

-- ukazka intenzionalneho zapisu:
-- [ 38 * x | x <- [1,3,5,2,5,4,4], y <- [1..x], even x ]

chceme [1,3,3,3,5,5,5,5,5, ..., 13,15,15,15, ...]

[ x | x <- [1,3..], _ <- [1..(mod x 12)]]

*** priklad 06 ***

data BinTree a = Empty | Node a (BinTree a) (BinTree a)
-- n-arny strom, podobny tomu, ktory bude neskor preberany na prednaske:
data NTree a = NEmpty | NNode a [NTree a]
-- NNode 1 [NEmpty, NNode 3 [], NNode 10 (repeat NEmpty)]
-- problem v existencii viacerych reprezentacii intuitivne rovnakeho stromu;
-- vyriesi sa odstranenim NEmpty
-- NNode 1 [] === NNode 1 [NEmpty] === ...

*** priklad X ***

--    f . g      ->     \x -> f (g x)
-- (.) f g x = f (g x)

prevod z pointfree do pointwise
(.) . (.) snd
\x -> ((.) . (.) snd) x
\x -> (.) ((.) snd x)
\x y z -> (.) ((.) snd x) y z
          (.) ----------- ~ _
\x y z -> ((.) snd x) (y z)
          ----------- (~ _)
\x y z -> (.) snd x (y z)
\x y z -> snd (x (y z))

co treba robit:
-- doplnit maximalny pocet argumentov podla arity funkcie
-- prevadzat z infixu do prefixu
-- prepisovat zname funkcie podla definicie
-- zjednodusovat vyraz, odstranovat nepotrebne ()

*** priklad Y ***

otypovat \x -> x 3

1. otypovanie funkcii, premennych, konstant
x :: a -> b
3 :: (Num c) => c

2. typove rovnosti z aplikacie funkcii
a = c

3. vyjadrenie vsetkych typov pomocou minimalnej mnoziny typ. premennych
a = a
b = b
c = a

4. hladany typ
(a -> b) -> b = (a -> b) -> b

5. zohladnit typove kontexty
(Num a) => (a -> b) -> b