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