{- 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))

-}