{- 5.1 -- je dobre pohrat sa s nasledovnym typom vyrazov -- f n = [ (x, y) | x <- [1..n], y <- [1..x] ] map f s === [ f x | x <- s ] filter p s === [ x | x <- s, p x ] map f (filter p s) === [ f x | x <- s, p x ] repeat x === [ x | _ <- [1..] ] -- replicate n x vrati zoznam s n-krat opakovanym prvkom x replicate n x === [ x | _ <- [1..n] ] -} {- 5.2 [ x | x <- [] ] [ () | False ] -- nizsie funguje pre cokolvek okrem nekonecneho zoznamu [ x | x <- [...], False ] -} -- let x = vyraz -- [ t ^ n | n <- s, p (s * 3), let t = blabla n ] -- [ x | n <- s, ..., x <- [head n]] {- 5.3 iterate f x === [x, f x, f (f x), f (f (f x)), ...] a) iterate (*2) 1 -- iterate f x = x : iterate f (f x) iterate (*2) 1 ~> 1 : iterate (*2) ((*2) 1) ~> ~> 1 : (*2) 1 : iterate (*2) ((*2) ((*2) 1)) b) iterate (*9) 1 c) iterate (*9) 3 d) iterate ("*"++) "" iterate ('*':) "" iterate (++"*") "" jednotlive riesenia su rozne efektivne (lin, lin, kvadr. voci n) zlozitost (++) je linearna v prvom argumente -} {- 5.4 -} fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) {- ak by sme vyssie uvedenu definiciu upravili tak, ze namiesto (tail fibs) by sme mali (tail (tail fibs)), nedostali by sme viac ako prve dva prvky 0, 1. Preco? -} fibs_naive :: Integer -> Integer fibs_naive 0 = 0 fibs_naive 1 = 1 fibs_naive n = fibs_naive (n - 1) + fibs_naive (n - 2) fibs_better :: Integer -> Integer fibs_better n = fibs_aux n 0 1 fibs_aux :: Integer -> Integer -> Integer -> Integer fibs_aux 0 x y = x fibs_aux n x y = fibs_aux (n - 1) y (x + y) trib :: [Integer] trib = 0 : 1 : 1 : zipWith (+) trib (zipWith (+) (tail trib) (tail (tail trib))) ---- --------- ---------------- {- 5.6 -} pt = iterate (\r -> zipWith (+) ([0]++r) (r++[0])) [1] {- 5.7 -} -- http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html {- readFile "cv/cv1.hs" >>= \x -> putStrLn (show (lines x)) -} {- zlozitost (++) x y m = length x n = length y (++) je O(m) -- f n = head [1..n] -- head [1..n] ~> head (1:[2..n]) ~> 1 -} {- BONUSOVA ULOHA ZADANIE: 1. Definujte funkciu rect2 :: Int -> Int -> [[a]] -> [[a]], ktora podla hodnot danych dvoch cisel vrati "obdlznikovy vysek" zo zadaneho zoznamu - pre (rect2 m n lst) bude mat vysledny zoznam max m prvkov a kazdy podzoznam max n prvkov. T.j. pre zoznam s = [ [1^1, 2^1, 3^1, ...], [1^2, 2^2, 3^2, ...], ... [1^k, 2^k, 3^k, ...], ... ] vrati (rect2 3 2 s) ako vysledok nasledovny zoznam [ [1^1, 2^1], [1^2, 2^2], [1^3, 2^3] ]. 2. Definujte analogicku funkciu rect3 :: Int -> Int -> Int -> [[[a]]] -> [[[a]]]. RIESENIE: 1. Staci vhodne pouzit funkciu take, ktora robi presne to, co potrebujeme: rect2 m n s = take m (map (take n) s) alebo rect2 m n = take m . map (take n) Da sa pouzit aj taketo riesenie, ktore nie je az tak elegantne, ale funguje: rect2 m n s = [ [ (s !! (n-1)) !! (m-1) | y <- [1..n] ] | x <- [1..m] ] 2. Obdobne: rect3 m n o = take m . map (take n) . map (map (take o)) -}