Skip to content

Instantly share code, notes, and snippets.

@jiribenes
Created Apr 28, 2022
Embed
What would you like to do?
Cvičení z Neprocedurálního programování - 11
import Data.List
-- Nejprve jsme si napsali funkci typu (b -> c) -> (a -> b) -> a -> c
compose :: (b -> c) -> (a -> b) -> (a -> c)
compose f g = \x -> f (g x)
-- alternativně: compose f g x = f (g x)
-- Ve standardní knihovně je to jako operátor tečka `(.)`, například:
addOneAndSum = compose sum (map (+ 1))
addOneAndSum' = sum . map (+ 1)
-- Operátor "tečka" spojuje dvě funkce dohromady zprava.
-- (f `kolečko` g)(x) = f(g(x))
-- Reálně je to pajpa z UNIXu, jen zprava doleva!
-- Tedy v Haskellu se zapisuje
-- f (g (h x)) jako (f . g . h)(x)
-- či spíše jako f . g . h $ x
-- Pak jsme si ukazovali operátor `($)`, který aplikuje funkci na argument,
-- ale je silně asociativní zprava. V tu chvíli nám umožňuje vynechávat závorky:
-- f $ g $ h x = f (g (h x))
-- Ukažme si to na funkci wordList, která:
-- `words` rozdělí string na slova
-- `map words` rozdělí každý string na slova ~> [[String]]
-- `concat` potom sesbírá všechna slova ~> [String]
-- `nub` vynechá duplicity
-- `sort` setřídí
wordList :: [String] -> String
wordList docs = sort (nub (concat (map words docs)))
-- pomocí dolarů:
wordList' docs = sort $ nub $ concat $ map words docs
-- nebo:
wordList'' docs = sort $ nub $ concat $ map words $ docs
-- pomocí tečky a dolaru:
wordList''' docs = sort . nub . concat . map words $ docs
-- jen pomocí tečky -- "zkrátíme" argument úplně:
wordList'''' = sort . nub . concat . map words
-- Tahle verze už opravdu vypadá jako bashový příkaz, jen zprava doleva!
-- Nepotřebujeme pojmenovávat proměnné, když je nemáme :D
-- Pozorování: V Haskellu má každý výraz právě jeden nejobecnější typ
-- třeba 'identita' má nejobecnější typ 'a -> a'
-- Problém: Chceme otypovat funkci (+).
-- Možnost A: (+) :: a -> a -> a
-- --> problém: ne všechny typy jdou sečíst
-- Možnost B: (+) má dvě varianty:
-- (+) :: Double -> Double -> Double
-- (+) :: Int -> Int -> Int
-- ---> to je ošklivé a přijdeme o to, že každý výraz má právě jeden nejobecnější typ
-- => Řešení: Některé typy prohlásíme za _Num_erické
-- a řekneme, že typ (+) je Num a => a -> a -> a
-- kde 'Num a =>' znamená "typ 'a' musí být _numerický_".
-- Tohle je obecný mechanismus jak zařídit overloadování funkcí!
-- Typová třída 'MyEq'
-- POZOR: Nesouvisí s OOP třídami!
class MyEq a where
-- Pokud nějaký typ 'a' splňuje 'MyEq', pak má funkci 'myeq'
myeq :: a -> a -> Bool
-- >>> :t myeq
-- MyEq a => a -> a -> Bool
-- Zadefinujeme si vlastní barvičky
data MojeBarvy = Zelena | Cervena | Modra | ZaseCervena
deriving (Show, Eq)
-- Vytvoříme instanci typové třídy 'MyEq' pro datový typ 'MojeBarvy'
instance MyEq MojeBarvy where
myeq Zelena Zelena = True
myeq Cervena Cervena = True
myeq Modra Modra = True
myeq ZaseCervena ZaseCervena = True
-- červená == zase_červená
myeq Cervena ZaseCervena = True
myeq ZaseCervena Cervena = True
myeq _ _ = False
-- Můžeme přidávat instance i pro již existující typy! :)
instance MyEq Int where
myeq = (==)
-- Je pravdivá, pokud daný prvek je v daném seznamu.
-- Využívá 'myeq' pro testování rovnosti.
-- Tedy typ 'a' vkládaný do této funkce
myElem :: MyEq a => a -> [a] -> Bool
myElem _ [] = False
myElem y (x:xs)
| myeq y x = True
| otherwise = myElem y xs
-- Zajímavý příkaz v GHCi:
-- :i MyEq ... vypíše popis třídy a její instance!
{-
Zajímavé jednoduché typové třídy,
které jsou ve std. knihovně.
Pro většinu typových tříd platí nějaká pravidla ("zákony"):
- Show a ... 'a' je hezky vypsatelné
... `show :: Show a => a -> String`
... žádné pravidlo
- Eq a ... 'a' je typ, který podporuje rovnost
...`(==) :: Eq a => a -> a -> Bool`
...`(/=) :: Eq a => a -> a -> Bool`
... pravidlo: tato relace je ekvivalence
- Ord a ... 'a' je porovnatelný
... `(<=) :: Ord a => a -> a -> Bool`
... pravidlo: částečné uspořádání
- Num a ... 'a' je numerický
... `(+) :: Num a => a -> a -> a`
... `(*) :: Num a => a -> a -> a`
... pravidlo: polookruh
--}
-- Naprogramujme si polookruh pro Z5 (sčítání/násobení modulo 5)
data Z5 = Z5 Integer
deriving (Show, Eq, Ord)
instance Num Z5 where
(Z5 a) + (Z5 b) = Z5 (a + b `mod` 5)
(Z5 a) * (Z5 b) = Z5 (a * b `mod` 5)
(Z5 a) - (Z5 b) = Z5 (a - b `mod` 5)
abs (Z5 a) = Z5 a
signum (Z5 0) = 0
signum (Z5 _) = 1
fromInteger x = Z5 (x `mod` 5)
-- Pomocná definice
produkt :: Num a => [a] -> a
produkt = foldr (*) 1
cislaVZ5 :: [Z5]
cislaVZ5 = [Z5 1, Z5 4, Z5 3]
-- >>> produkt cislaVZ5
-- Z5 2
-- Když Haskell vidí `1`, tak tam dosadí `(fromInteger 1)`
-- kde `fromInteger :: Num a => Integer -> a`
-- Mohli bychom tedy napsat:
cislaVZ5' :: [Z5]
cislaVZ5' = [1, 4, 3]
-- "Náš" seznam, který obsahuje hodnoty typu 'a'
data Seznam a = Nil | Cons a (Seznam a)
-- Seznamy a-ček podporují rovnost, _pokud_ a podporuje rovnost
instance Eq a => Eq (Seznam a) where
(==) = eq
eq :: Eq a => Seznam a -> Seznam a -> Bool
Nil `eq` Nil = True
(Cons x xs) `eq` (Cons y ys) = (x == y) && (xs `eq` ys)
_ `eq` _ = False
-- Seznamy a-ček jdou vypsat, _pokud_ a jde vypsat.
instance Show a => Show (Seznam a) where
show Nil = ""
show (Cons x Nil) = show x
show (Cons x xs) = show x ++ ", " ++ show xs
testSeznam :: Seznam Int
testSeznam = Cons 1 (Cons 2 (Cons 3 Nil))
-- >>> show testSeznam
-- "1, 2, 3"
-- Cvičení: Dodefinujte Ord instanci pro tento typ:
-- (dělali jsme, zkuste si sami!)
data Infinite a = MinusInf | Finite a | PlusInf
deriving (Eq, Show) -- automaticky vygeneruje Show a Eq instance
-- Kostra:
instance Ord a => Ord (Infinite a) where
compare _ _ = error "fixme"
-- compare :: Ord a => a -> a -> Ordering
-- kde
-- data Ordering = LT | EQ | GT
{- POLOGRUPA (Semigroup)
definováno jako
class Semigroup a where
(<>) :: a -> a -> a
...
je asociativní operace, tedy mělo by platit, že:
pro každé a, b, c: (a <> b) <> c == a <> (b <> c)
Typické příklady:
instance Semigroup [a] where
(<>) = (++)
instance Semigroup a => Semigroup (Maybe a) where
Nothing <> Nothing = Nothing
Nothing <> Just y = Just y
Just x <> Nothing = Just x
Just x <> Just y = Just $ x <> y
MONOID je pologrupa, která má neutrální prvek.
Je definována jako
class Semigroup a => Monoid a where
mempty :: a
...
Mělo by tedy platit navíc, že:
pro každé a: a <> mempty = mempty <> a = a
Typické příklady:
instance Monoid [a] where
mempty = []
instance Semigroup a => Monoid (Maybe a) where
mempty = Nothing
-}
-- Příklady:
-- wrapper pro součet
data Sum a = Sum a
-- wrapper pro součin
data Product a = Product a
-- Součet s nulou tvoří monoid
instance Num a => Semigroup (Sum a) where
Sum a <> Sum b = Sum $ a + b
instance Num a => Monoid (Sum a) where
mempty = Sum 0
-- Součin s jedničkou tvoří monoid
instance Num a => Semigroup (Product a) where
Product a <> Product b = Product $ a * b
instance Num a => Monoid (Product a) where
mempty = Product 1
{-
Pro SW se hodí následující interpretace:
Když máte seznam věcí, které jsou pologrupy, tak je nemusíte počítat najednou,
ale můžete je dělat paralelně -- rozsekáte je na kusy a pak je můžete slepovat jak chcete,
jediné co musíte splnit je, aby `(x <> y) <> z == x <> (y <> z)`.
Znamená to, že je jedno v jakém uzávorkování je naházíte dohromady!
Například když budete chtít sečíst dlouhý seznam čísel, tak je v pořádku,
když napřed sečtete jednu půlku v jednom vlákně
a druhou půlku v druhém vlákně!
-}

Doporučuji přečíst blogpost https://iagoleal.com/posts/calculus-symbolic/ který ukazuje hezké použití Num pro vlastní typ reprezentující racionální polynom. Na konci to umí automaticky z funkce vyrobit Taylorův polynom!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment