Cvičení z Neprocedurálního programování - 11

0-dots-and-dollars.hs

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

1-classes.hs

-- 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

2-monoid.hs

{- 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ě!
-}

3-automatic-diff.md

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!