Skip to content

Instantly share code, notes, and snippets.

@jiribenes

jiribenes/1-opakovani.hs Secret

Last active May 4, 2021
Embed
What would you like to do?
Cvičení z Neprocedurálního programování - 8
-- Tato možnost zapne všechny warningy:
{-# OPTIONS_GHC -Wall #-}
-- Opakování:
-- Funkce třech argumentů
sectiTri :: Int -> Int -> Int -> Int
sectiTri x y z = x + y + z
-- Pokud ji částečně aplikujeme na dva argumenty,
-- dostaneme funkci dvou argumentů
prictiJednicku :: Int -> Int
prictiJednicku = sectiTri 0 1
-- >>> prictiJednicku 42
-- 43
-- Základní typy:
-- Int
-- Char
-- String = [Char]
-- [a] .. seznam áček
-- (a, b) .. dvojice
-- Double
-- Datové typy
{-# OPTIONS_GHC -Wall #-}
-- Součtové typy:
-- Barva je buď červená, nebo zelená, nebo modrá
data Barva = Cervena | Zelena | Modra
barvaToString :: Barva -> String
barvaToString barva =
case barva of -- rozeber možnosti `barva`
Cervena -> "Cervena" -- ... pokud je červená
Zelena -> "Zelena" -- ... pokud je zelená
Modra -> "Modra" -- ... pokud je modrá
-- >>> barvaToString Modra
-- "Modra"
jeBarvaCervena :: Barva -> Bool
jeBarvaCervena barva =
case barva of
Cervena -> True
_ -> False -- default = False
-- >>> jeBarvaCervena Zelena
-- False
-- Pattern matching v argumentu funkce
-- jde udělat i na top-level úrovni!
barvaToString' :: Barva -> String
barvaToString' Cervena = "Cervena"
barvaToString' Zelena = "Zelena"
barvaToString' Modra = "Modra"
jeBarvaCervena' :: Barva -> Bool
jeBarvaCervena' Cervena = True
jeBarvaCervena' _ = False -- default = False
-- Intuitivně si můžeme předstvovat, že:
-- data Int = ... | -2 | -1 | 0 | 1 | 2 | ...
-- data Char = 'a' | 'b' | 'c' | ... | 'z' | 'A' | 'B' | ...
-- data Bool = True | False
-- [Poznámka: Bool je takhle _fakt_ definován :D]
fibonacci :: Int -> Int
fibonacci 1 = 0
fibonacci 2 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)
-- >>> fibonacci 10
-- 34
-- Produktové typy:
data RGB = MkRGB Int Int Int -- červená, zelená, modrá
-- MkRGB je funkce typu Int -> Int -> Int -> RGB
fialova :: RGB
fialova = MkRGB 255 0 255
-- Zde můžeme pattern matchovat jednotlivé prvky
-- a přiřadit jim proměnné.
-- Pokud nějakou nechceme využít, můžeme napsat `_`.
pridejCervenou :: RGB -> RGB
pridejCervenou (MkRGB _ g b) = MkRGB 255 g b
-- Konverze z RGB na trojici není automatická
-- i přes to, že jsou tyto typy izomorfní.
-- Pokud chcete funkci z RGB do trojice intů,
-- musíte si ji napsat sami
vyrobTrojici :: RGB -> (Int, Int, Int)
vyrobTrojici (MkRGB r g b) = (r, g, b)
foo :: (Int, Int, Int)
-- nefunguje:
-- foo = fialova
-- funguje:
foo = vyrobTrojici fialova
-- ADT
{-# OPTIONS_GHC -Wall #-}
-- součtové & produktové typy dohromady
-- => "Algebraický Datový Typ"
data Barva -- Barva je
= Cervena -- ... buď červená
| Zelena -- ... nebo zelená
| Modra -- ... nebo modrá
| RGB Int Int Int -- ... nebo reprezentovaná jako RGB (tři inty)
-- Je barva červená?
jeBarvaCervena :: Barva -> Bool
jeBarvaCervena Cervena = True -- pokud je to 'Cervena', pak ano
jeBarvaCervena (RGB 255 _ _) = True -- pokud je to 'RGB 255 _ _', pak ano
jeBarvaCervena _ = False -- jinak ne
-- Pojmenuje barvu, ukázka pattern matchingu
pojmenujBarvu :: Barva -> String
pojmenujBarvu Cervena = "cervena"
pojmenujBarvu Modra = "modra"
pojmenujBarvu (RGB 255 0 255) = "fialova"
pojmenujBarvu (RGB _ 255 _) = "nazelenala? asi?"
pojmenujBarvu _ = "neznam :("
-- Příklad modelování reálného světa pomocí typů:
data SachovaBarva = Cerna | Bila
data SachovyDruh = Pesak | Jezdec | Kral | Strelec | Kralovna | Vez
data Figurka = Figurka SachovaBarva SachovyDruh
bilyKral :: Figurka
bilyKral = Figurka Bila Kral
-- Co si vyrobit seznamy? :)
data Seznam -- Seznam je
= Cons Int Seznam -- ... buď číslo a zbytek seznamu
| Nil -- ... nebo prázdný seznam
deriving (Show, Eq) -- Tohle je magické zaříkadlo, aby šel náš seznam vypsat v GHCi
-- příště vysvětlím pořádně :)
-- Seznam obsahující [1, 2, 3]
prvniTri :: Seznam
prvniTri = Cons 1 (Cons 2 (Cons 3 Nil))
-- Rekurzivně zjistí délku seznamu
delkaSeznamu :: Seznam -> Int
delkaSeznamu Nil = 0
delkaSeznamu (Cons _ xs) = 1 + delkaSeznamu xs
-- Poznámka: Typicky používáme x jako hlavu seznamu a xs jako ocásek/zbytek seznamu.
-- Často totiž máme seznam nějakého obecného typu a v tu chvíli nemá
-- konkrétnější pojmenování smysl...
{-
Proč nepoužívat `head` a `cons`:
Vezměte si následující funkce:
head' :: Seznam -> Int
head' (Cons x _) = x
tail' :: Seznam -> Seznam
tail' (Cons _ xs) = xs
Co by měly tyto funkce vracet v případě `Nil`?
Žádná z možností není moc hezká,
Haskell prostě vypíše error... :/
Proto je dobré používat raději pattern matching!
-}
-- v Haskellu se 'Cons' píše jako (:) ... a tedy 'Cons x xs' je '(x:xs)'
-- 'Nil' píše jako []
prvniTriCisla :: [Int]
prvniTriCisla = [1, 2, 3] -- také jde napsat jako (1:2:3:[]) explicitně
-- Délka seznamu
delka :: [Int] -> Int
delka [] = 0
delka (_:xs) = 1 + delka xs
-- >>> delka prvniTriCisla
-- 3
{- Pattern matching pro seznamy:
[] ... prázdný seznam
xs ... libovolný seznam (i prázdný)
[x] ... seznam o právě jednom prvku
[x, y] ... seznam o právě dvou prvcích
(x:xs) ... seznam o alespoň jednom prvku
(x:y:xs) ... seznam o alespoň dvou prvcích...
-}
-- take' n xs ... vezme prvních n prvků ze seznamu xs
take' :: Int -> [Int] -> [Int]
take' 0 _ = [] -- pokud chceme vzít 0 prvků, pak vrátíme prázdný seznam
take' _ [] = [] -- pokud chceme brát z prázdného seznamu, tak vrátíme prázdný seznam
take' n (x : xs) = -- jinak rozdělíme seznam na (x:xs)
let rest = take' (n - 1) xs -- zarekurzíme se: vezmeme (n-1) prvků ze seznamu xs a uložíme do 'rest'
in x : rest -- vrátíme 'x' připojený na začátek 'rest'
-- Parametrické typy -- typy s parametrem ("generika" v C#)
{-# OPTIONS_GHC -Wall #-}
identitaProCisla :: Int -> Int
identitaProCisla x = x
-- >>> identitaProCisla 42
-- 42
-- čteme "pro každý typ a: a -> a"
-- typové proměnné se píšou malými písmenky!
-- jsou obecně kvantifikované (s provšechnítkem)
identita :: a -> a
identita x = x
{-
V jiných jazycích:
T identita<T> (T x) {
return x;
}
template <typename T>
T identita (T x) {
return x;
}
-}
-- Tyto typy nejsou pro identitu platné!
-- (čteme pro každé a, b: a -> b)
--identita1 :: a -> b
--identita1 x = x -- nejde, a se musí rovnat b!
--identita2 :: a -> Int
--identita2 x = x -- nejde, a by se musel rovnat 'Int'!
--identita3 :: Int -> a
--identita3 x = x -- nejde, a by se musel rovnat 'Int'!
-- Tato funkce vezme funkci a aplikuje ji dvakrát
dvakrat :: (a -> a) -> a -> a
dvakrat f x = f (f x)
-- >>> dvakrat (\x -> x + 2) 1
-- 5
-- Vezme funkci z 'a' do 'b', seznam 'a'ček a vrátí seznam 'b'ček
map' :: (a -> b) -> [a] -> [b]
map' _ [] = [] -- pro prázdný seznam vrátí prázdný seznam
map' f (x : xs) = f x : map' f xs -- jinak vrátí (f x) na začátku a zarekurzí se na zbytek seznamu
-- 'map' jsme si vyrobili i v Prologu,
-- připomínám, že je to dobrý způsob jak si pořídit "for loop"
-- (jak udělat něco pro každý prvek seznamu)
-- >>> map (\x -> x + 2) [1..5]
-- [3, 4, 5, 6, 7]
-- >>> map (\x -> x * 2) [1..5]
-- [2, 4, 6, 8, 10]
-- 'filter' vezme predikát a seznam a vrátí prvky vyhovující predikátu
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x:xs) =
case p x of -- data Bool = True | False , takže můžeme pattern matchovat
True -> x : filter' p xs -- pokud predikát platí, přidáme x a zarekurzíme se
False -> filter' p xs -- jinak se jen zarekurzíme
-- >>> filter (\x -> x > 3) [1..5]
-- [4, 5]
filter'' :: (a -> Bool) -> [a] -> [a]
filter'' _ [] = []
filter'' p (x:xs) =
if p x then x : filter'' p xs -- to samé, ale pomocí 'if-then-else'
else filter'' p xs
filter''' :: (a -> Bool) -> [a] -> [a]
filter''' _ [] = []
filter''' p (x:xs)
| p x = x : filter''' p xs -- to samé, ale pomocí stráží (guards)
| otherwise = filter''' p xs
-- Příklad pro guards:
pojmenuj :: Int -> Int -> String
pojmenuj x y
| x > y = "x je vetsi"
| x == y = "stejne"
| otherwise = "y je vetsi"
-- Verze výše je rozhodně hezčí než tohle:
pojmenuj' :: Int -> Int -> String
pojmenuj' x y =
if x > y then "x je vetsi"
else if x == y then "stejne"
else "y je vetsi"
-- Často používané operátory u seznamů.
-- Zkuste odhadnout co dělají dle jejich typu
-- (++) :: [a] -> [a] -> [a] ... O(N)
-- (!!) :: Int -> [a] -> a ... O(N)
-- Klasický příklad --- quicksort! :)
quicksort :: [Int] -> [Int]
quicksort [] = []
quicksort (pivot:rest) = quicksort left ++ [pivot] ++ quicksort right
where
-- mensi nez pivot => nalevo od pivota
left :: [Int]
left = filter (\x -> x < pivot) rest
-- vetsi nebo rovno nez pivot => napravo od pivota
right :: [Int]
right = filter (\x -> x >= pivot) rest
nasSeznam = [10,9..1 :: Int]
-- >>> quicksort nasSeznam
-- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment