Práce se seznamy


-- skytí knihovních funkcí které napíšeme
import Prelude hiding
    ( (!!), and, cycle, reverse, map, filter )

and :: [Bool] -> Bool
and [] = True
and (h:t) = h && and t


(!!) :: [a] -> Int -> a
(!!) (x:xs) n | n==0 = x
              | n>0 = xs !! (n-1)
              | otherwise = undefined
[] !! _ = error "krátký seznam"


cycle :: [a] -> [a]
cycle [] = []
cycle l = l ++ cycle l
-- (++) :: [a] -> [a] -> [a]

-- Bonus: vytvoření cyklického seznamu pomocí lenosti
cycle' l = c where
    c = l ++ c


reverse :: [a] -> [a]
reverse [] = []
reverse (h:t) = (reverse t) ++ [h] 
-- kvadratické, pokud vyhodnotíme všechno

-- lineární pomocí akumulátoru
reverse' s = reverseCat s []
-- reverseCat a b == reverse a ++ b
reverseCat [] p = p
reverseCat (h:t) p = reverseCat t (h:p)


filter :: (a -> Bool) -> [a] -> [a]
filter f [] = []
--filter f (h:t) = if f h then h : filter f t else filter f t
filter f (h:t) = (if f h then [h] else []) ++ filter f t


map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x : map f xs)

{-
>   take 5 $ map (* 23) $ filter (>10) [1..]
[253,276,299,322,345]
>   :i ($)
($) :: (a -> b) -> a -> b
infixr 0 $
-}

-- cíl mergesort (mimochodem, Data.List obsahuje sort)
mérdž l [] = l
mérdž [] l = l
mérdž (a:b) (c:d) = if a > c
    then c : (mérdž (a:b) d)
    else a : (mérdž b (c:d))

split [] = ([], [])
split (a:[]) = ([a], [])
split (x:y:xs) = ((x:a), (y:b)) where
    (a, b) = split xs

méčsort [] = []
méčsort [a] = [a]
méčsort l = mérdž a b where
    a = méčsort c
    b = méčsort d
    (c, d) = split(l)


-- Bonus k zamyšlení: efektivní a stručná verze
-- seznamu celé Fibonacciho posloupnosti
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
-- zipWith f (x:xs) (y:ys) = f x y : zipWith xs ys