-- Jednoduche ukony se seznamem
suma :: [Int] -> Int
suma [] = 0
suma (x:xs) = x + suma xs
posledni :: [a] -> a
posledni (x:[]) = x
posledni (x:xs) = posledni xs
prostredni :: [a] -> a
prostredni (x:[]) = x
prostredni (x:_:[]) = x
prostredni (x:y:xs) = prostr (y:xs) xs
prostr :: [a] -> [a] -> a
prostr (x:_) (_:[]) = x
prostr (x:_) (_:_:[]) = x
prostr (_:xs) (_:_:ys) = prostr xs ys
mymax :: (Ord a) => [a] -> a
mymax (x:[]) = x
mymax (x:y:xs) | (x > y) = mymax (x:xs)
| otherwise = mymax (y:xs)
mymin :: (Ord a) => [a] -> a
mymin (x:[]) = x
mymin (x:y:xs) | (x < y) = mymin (x:xs)
| otherwise = mymin (y:xs)
-- Sort
quickSort :: (Ord a) => [a] -> [a]
quickSort []= []
quickSort (x:xs) = quickSort ([y|y<-xs, y<x]) ++ [x] ++ quickSort ([y|y<-xs, y>=x])
mergeSort :: (Ord a) => [a] -> [a]
mergeSort [] = []
mergeSort (x:[]) = [x]
mergeSort x = merge (mergeSort(fst pulky)) (mergeSort(snd pulky))
where pulky = naPulky x
naPulky :: (Ord a) => [a] -> ([a],[a])
naPulky [] = ([], [])
naPulky (x:[]) = ([x],[])
naPulky (x:y:xs) = ((x:(fst z)), (y:(snd z)))
where z = naPulky xs
merge :: (Ord a) => [a] -> [a] -> [a]
merge x [] = x
merge [] x = x
merge (x:xs) (y:ys) | (x < y) = (x:(merge xs (y:ys)))
| otherwise = (y:(merge (x:xs) ys))
-- Seznam prvociselnych delitelu
seznamDelitelu :: (Integral a, Enum a) => a -> [a]
seznamDelitelu 1 = [1]
seznamDelitelu 2 = [1,2]
seznamDelitelu x | odd x = [1] ++ (eratosthen [y|y<-[3,5..floor(sqrt (fromIntegral x))], (mod x y) == 0])
| otherwise = [1,2] ++ (eratosthen [y|y<-[3,5..floor(sqrt (fromIntegral x))], (mod x y) == 0])
eratosthen :: (Integral a) => [a] -> [a]
eratosthen [] = []
eratosthen (x:xs) = (x:(eratosthen (vyskrtejNasobky x xs)))
vyskrtejNasobky :: (Integral a) => a -> [a] -> [a]
vyskrtejNasobky _ [] = []
vyskrtejNasobky x (y:ys) | ((mod y x) == 0) = vyskrtejNasobky x ys
| otherwise = (y:(vyskrtejNasobky x ys))
-- Graf a prochazeni do sirky
data Uzel = Uz ID String [ID]
type ID = Int
type Graf = [Uzel]
vypis :: [(ID, Int)] -> String
vypis [] = ""
vypis ((x, y):[]) = ("("++(show x)++", "++(show y)++")")
vypis ((x, y):xs) = ("("++(show x)++", "++(show y)++"), ")++(vypis xs)
uz1::Uzel
uz1 = (Uz 1 "" [2, 3, 4])
uz2::Uzel
uz2 = (Uz 2 "" [1, 4])
uz3::Uzel
uz3 = (Uz 3 "" [5])
uz4::Uzel
uz4 = (Uz 4 "" [1, 2, 3])
uz5::Uzel
uz5 = (Uz 5 "" [3])
myG::Graf
myG = [uz1, uz2, uz3, uz4, uz5]
projdiDoSirky :: Graf -> ID -> [(ID, Int)]
projdiDoSirky [] _ = []
projdiDoSirky g i = prochazejDoSirky g [(i, 0)] []
prochazejDoSirky :: Graf -> [(ID, Int)] -> [ID] -> [(ID, Int)]
prochazejDoSirky _ [] _ = []
prochazejDoSirky g ((i, vz):is) y | (prvek i y) = prochazejDoSirky g is y
| otherwise = (((idUzlu x), vz)):(prochazejDoSirky g (is ++ nove) (i:y))
where
x = najdiUzel g i
nove = zip (sousediUzlu x) (repeat (vz + 1))
prvek :: (Eq a) => a -> [a] -> Bool
prvek _ [] = False
prvek y (x:xs) | (y == x) = True
| otherwise = prvek y xs
najdiUzel :: Graf -> ID -> Uzel
najdiUzel (u:us) id | (id == idUzlu u) = u
| otherwise = najdiUzel us id
idUzlu :: Uzel -> ID
idUzlu (Uz id _ _) = id
sousediUzlu :: Uzel -> [ID]
sousediUzlu (Uz _ _ s) = s
-- Nasledujici permutace
naslPerm :: Ord a => [a] -> [a]
naslPerm [] = []
naslPerm x = reverse vysledek
where
(ros, zbyt) = rostouci (reverse x)
nv = nejmensiVetsi ros (prvniVetsi ros (head zbyt)) (head zbyt)
ros2 = prohod ros nv (head zbyt)
vysledek = ros2++(nv:(tail zbyt))
rostouci :: Ord a => [a] -> ([a], [a])
rostouci [] = ([], [])
rostouci (x:[]) = ([], [x])
rostouci (x:y:xs) | (x < y) = ((x:ros), zb)
| (x > y) = ([x], (y:xs))
where (ros, zb) = rostouci (y:xs)
prohod :: Eq a => [a] -> a -> a -> [a]
prohod [] _ _ = error "Dalsi permutace neexistuje"
prohod (x:xs) a b | (x == a) = b:xs
| otherwise = x:(prohod xs a b)
nejmensiVetsi :: Ord a => [a] -> a -> a -> a
nejmensiVetsi [] m _ = m
nejmensiVetsi (x:xs) mezi hod | ((x > hod) && (x < mezi)) = nejmensiVetsi xs x hod
| otherwise = nejmensiVetsi xs mezi hod
prvniVetsi :: Ord a => [a] -> a -> a
prvniVetsi [] a = a
prvniVetsi (x:xs) a | (x > a) = x
| otherwise = prvniVetsi xs a
-- Generator pascalova trojuhelniku
pascal :: Num a => [[a]]
pascal = generujPasc [[1]]
generujPasc :: Num a => [[a]] -> [[a]]
generujPasc (x:[]) = x:(generujPasc [generujDalsi (0:x)])
generujPasc (x:xs) = x:(generujPasc xs)
generujDalsi :: Num a => [a] -> [a]
generujDalsi (x:[]) = [x]
generujDalsi (x:y:xs) = (x + y):(generujDalsi (y:xs))
-- BVS a ruzne vylomeniny
data (Ord a, Eq a) => BVS a = Null | Bvs (BVS a) a (BVS a) deriving Show
postavBVSpreOrder :: (Ord a, Eq a) => [a] -> BVS a
postavBVSpreOrder [] = Null
postavBVSpreOrder (x:xs) = (Bvs levy x pravy)
where
levy = postavBVSpreOrder [y | y <- xs, y <= x]
pravy = postavBVSpreOrder [y | y <- xs, y > x]
postavBVSinOrder :: (Ord a, Eq a) => [a] -> BVS a
postavBVSinOrder [] = Null
postavBVSinOrder x = (Bvs levy h pravy)
where
(l, (h:p)) = naPoloviny x x
levy = postavBVSinOrder l
pravy = postavBVSinOrder p
naPoloviny :: [a] -> [a] -> ([a], [a])
naPoloviny [] [] = ([], [])
naPoloviny (x:xs) [] = ([], (x:xs))
naPoloviny (x:xs) (y1:[]) = ([], (x:xs))
naPoloviny (x:xs) (_:_:ys) = ((x:(fst z)), (snd z))
where z = naPoloviny xs ys
postavBVSpostOrder :: (Ord a, Eq a) => [a] -> BVS a
postavBVSpostOrder x = postavBVSpreOrder (reverse x)
vypustPrvekBVS :: (Ord a, Eq a) => BVS a -> a -> BVS a
vypustPrvekBVS Null _ = Null
vypustPrvekBVS (Bvs Null h Null) a | (a == h) = Null
| otherwise = (Bvs Null h Null)
vypustPrvekBVS (Bvs Null h pravy) a | (a == h) = pravy
| otherwise = (Bvs Null h (vypustPrvekBVS pravy a))
vypustPrvekBVS (Bvs levy h Null) a | (a == h) = levy
| otherwise = (Bvs (vypustPrvekBVS levy a) h Null)
vypustPrvekBVS (Bvs levy h pravy) a | (a > h) = (Bvs levy h (vypustPrvekBVS pravy a))
| (a < h) = (Bvs (vypustPrvekBVS levy a) h pravy)
| otherwise = (Bvs (vypustPrvekBVS levy x) x pravy)
where x = nejvetsiPrvekBVS levy
nejvetsiPrvekBVS :: (Ord a, Eq a) => BVS a -> a
nejvetsiPrvekBVS Null = error "Chyba - nenalezen nejvetsi prvek."
nejvetsiPrvekBVS (Bvs _ x Null) = x
nejvetsiPrvekBVS (Bvs _ _ pravy) = nejvetsiPrvekBVS pravy
vypustPrvkyBVS :: (Ord a, Eq a) => BVS a -> [a] -> BVS a
vypustPrvkyBVS Null _ = Null
vypustPrvkyBVS bvs [] = bvs
vypustPrvkyBVS bvs (x:xs) = vypustPrvkyBVS (vypustPrvekBVS bvs x) xs
vypisBVSpreOrder :: (Ord a, Eq a) => BVS a -> [a]
vypisBVSpreOrder Null = []
vypisBVSpreOrder (Bvs levy h pravy) = (h:(vypisBVSpreOrder levy))++(vypisBVSpreOrder pravy)
vypisBVSinOrder :: (Ord a, Eq a) => BVS a -> [a]
vypisBVSinOrder Null = []
vypisBVSinOrder (Bvs levy h pravy) = (vypisBVSinOrder levy)++(h:(vypisBVSinOrder pravy))
vypisBVSpostOrder :: (Ord a, Eq a) => BVS a -> [a]
vypisBVSpostOrder Null = []
vypisBVSpostOrder (Bvs levy h pravy) = (vypisBVSpostOrder levy)++(vypisBVSpostOrder pravy)++[h]
-- Polynomy
type Polynom = [(Koef, Exp)]
type Koef = Float
type Exp = Int
--soucet
soucetP :: Polynom -> Polynom -> Polynom
soucetP p [] = p
soucetP [] q = q
soucetP (p:ps) q = pricti p q1
where q1 = soucetP ps q
pricti :: (Koef, Exp) -> Polynom -> Polynom
pricti x [] = [x]
pricti x@(k1, e1) (p@(k2, e2):ps) | (e1 == e2) = if ((k1 + k2) == 0) then ps else ((k1 + k2), e1):ps
| otherwise = p:(pricti x ps)
--rozdil
rozdilP :: Polynom -> Polynom -> Polynom
rozdilP p q = soucetP p (vynasob (-1, 0) q)
--nasobeni
nasobeniP :: Polynom -> Polynom -> Polynom
nasobeniP [] q = []
nasobeniP (p:ps) q = soucetP (vynasob p q) q1
where q1 = nasobeniP ps q
vynasob :: (Koef, Exp) -> Polynom -> Polynom
vynasob _ [] = []
vynasob x@(k1, e1) (p@(k2, e2):ps) | ((k1 * k2) == 0) = vynasob x ps
| otherwise = ((k1 * k2), (e1 + e2)):(vynasob x ps)
--deleni (bohuzel je tam chyba, viz. deleniP [(1, 2), (-5, 1), (7, 0)] [(1, 1), (2, 0)])
deleniP :: Polynom -> Polynom -> (Polynom, Polynom) --delenec -> delitel -> (podil, zbytek)
deleniP p q = vydel (sortP p) (sortP q)
sortP :: Polynom -> Polynom
sortP [] = []
sortP (x:[]) = [x]
sortP (p@(_, e):ps) = (sortP [(k, e1) | (k, e1) <- ps, e <= e1])++(p:(sortP [(k, e1) | (k, e1) <- ps, e > e1]))
vydel :: Polynom -> Polynom -> (Polynom, Polynom)
vydel [] _ = ([], [])
vydel p@(x:_) q@(y:_) | (e < 0) = ([(0, 0)], p)
| otherwise = ((pricti pod podil), zbytek)
where
pod@(_, e) = najdiPodil x y
(podil, zbytek) = (vydel (sortP (rozdilP p (vynasob pod q))) q)
najdiPodil :: (Koef, Exp) -> (Koef, Exp) -> (Koef, Exp)
najdiPodil (k1, e1) (k2, e2) | (k2 == 0) = error "Deleni nulou"
| otherwise = (k1 / k2, e1 - e2)