Cvičenie 6 – Typové triedy¶
Useful Files¶
Navigation¶
- Základné pojmy
- Spoločné typy
- Krok 1 – Použitie typových tried
- Krok 2 – Definovanie inštancií
- Krok 3 – Vlastná typová trieda
- Krok 4 – Functor a Foldable
- Prehľad príkazov
1. Základné pojmy¶
| pojem | význam |
|---|---|
typová trieda (class) |
zoznam funkcií, ktoré typ musí vedieť (napr. Eq = vie ==) |
inštancia (instance) |
definícia, ako konkrétny typ tie funkcie robí |
deriving |
Haskell vytvorí inštanciu automaticky |
obmedzenie (Eq a =>) |
typ a musí patriť do triedy Eq |
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
x == y = not (x /= y) -- predvolené definície:
x /= y = not (x == y) -- stačí definovať jednu z nich
Kľúčové info z teórie¶
Dva druhy polymorfizmu
| druh | znamená | príklad |
|---|---|---|
| parametrický | funguje pre všetky typy rovnako | length :: [a] -> Int |
| ad hoc (preťaženie) | funguje len pre typy z triedy, každý inak | (==) :: Eq a => a -> a -> Bool |
Obmedzenie sa prenáša. Funkcia, ktorá vnútri používa ==, dostane obmedzenie Eq a aj do svojho typu:
Inštancia s obmedzením. Strom vieme porovnať, len ak vieme porovnať jeho prvky:
instance Eq a => Eq (BTree a) where
Leaf a == Leaf b = a == b
Branch l1 r1 == Branch l2 r2 = l1 == l2 && r1 == r2
_ == _ = False
Bez Eq a => vznikne chyba, lebo a == b porovnáva hodnoty typu a.
Predvolená metóda. Ak inštancia metódu nedefinuje, použije sa predvolená z class (preto stačí definovať len ==, a /= funguje samo).
Nadtrieda (dedenie). Ord rozširuje Eq, takže každý typ v Ord musí byť aj v Eq:
- stačí písať
Ord a =>namiesto(Eq a, Ord a) => instance Ord Shapepreto potrebuje ajinstance Eq Shape- viac nadtried naraz:
class (Eq a, Show a) => C a where ...
Druhy typov (kinds). Aj typy majú „typ“:
| typ | kind | význam |
|---|---|---|
Int, BTree Int |
* |
konkrétny typ, má hodnoty |
BTree, Maybe, [] |
* -> * |
čaká na typ (kontajner) |
Functor a Foldable vyžadujú kind * -> *, preto sa píše instance Functor BTree, nie BTree a. instance Functor Int je chyba. V GHCi to overíš cez :kind BTree.
Porovnanie s Javou
- Haskell
class≈ Javainterface(určuje, čo typ vie, nie dáta) - typ (
data) a jeho metódy (instance) sa definujú oddelene - chyby sa nájdu pri kompilácii, nie za behu
- žiadne automatické pretypovanie, žiadny spoločný predok ako
Object - žiadne
public/private, skrývanie sa robí cez moduly
2. Spoločné typy¶
data Point = Point Double Double
deriving (Eq, Show)
data Vector = Vec Double Double
deriving (Eq, Show)
data Shape -- bez Eq, to definujeme ručne (2.1)
= Circle Point Double
| Rectangle Point Point
deriving Show
data BTree a = Leaf a -- strom z cvičenia 5
| Branch (BTree a) (BTree a)
deriving Show
myLittleTree :: BTree Integer
myLittleTree = Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Leaf 4)
3. Krok 1 – Použitie typových tried¶
Úloha 1.1¶
Implementujte
allEqual, ktorá vrátiTrue, ak sú všetky hodnoty v zozname rovné, alebo ak je zoznam prázdny. Aký je typ tejto funkcie?
- prázdny zoznam →
True - inak: každý prvok zvyšku sa musí rovnať prvému
all p xs–True, akpplatí pre všetky prvky(== x)– funkcia „rovná sax?“
Typ: Eq a => [a] -> Bool – funguje pre každý typ, ktorý sa dá porovnať cez ==.
Úloha 1.2¶
Upravte
sumBTreetak, aby fungovala aj pre iné numerické typy (Int,Double).
-- pôvodne: sumBTree :: BTree Integer -> Integer
sumBTree :: Num a => BTree a -> a
sumBTree (Leaf x) = x
sumBTree (Branch l r) = sumBTree l + sumBTree r
Mení sa len typ. Num a => = a je akýkoľvek číselný typ, pre ktorý funguje +.
4. Krok 2 – Definovanie inštancií¶
Úloha 2.1¶
Definujte
EqpreShapetak, aby obdĺžniky líšiace sa iba poradím bodov boli rovné.
instance Eq Shape where
Circle c1 r1 == Circle c2 r2 = c1 == c2 && r1 == r2
Rectangle a1 b1 == Rectangle a2 b2 = normalize a1 b1 == normalize a2 b2
_ == _ = False
normalize :: Point -> Point -> (Point, Point)
normalize (Point x1 y1) (Point x2 y2) =
(Point (min x1 x2) (min y1 y2), Point (max x1 x2) (max y1 y2))
- kruhy: rovnaký stred aj polomer
- obdĺžniky:
normalizevyrobí vždy (ľavý dolný, pravý horný) roh → nezáleží na poradí bodov ani na uhlopriečke _ == _ = False– kruh sa nerovná obdĺžnikuShapenesmie mať zároveňderiving Eq(dve inštancie = chyba)
> Rectangle (Point 0 0) (Point 5 5) == Rectangle (Point 5 5) (Point 0 0)
True
> Rectangle (Point 0 0) (Point 5 5) == Rectangle (Point 0 5) (Point 5 0)
True
> Rectangle (Point 0 0) (Point 5 5) == Rectangle (Point 0 0) (Point 5 6)
False
> Circle (Point 0 0) 1 == Rectangle (Point 0 0) (Point 1 1)
False
Úloha 2.2¶
Bolo by možné definovať
OrdpreShape? Aké by bolo kritérium?
Áno, napr. podľa obsahu. Háčik: dva rôzne útvary s rovnakým obsahom by mali compare = EQ, ale == False → Ord nie je v súlade s Eq.
area :: Shape -> Double
area (Circle _ r) = pi * r^2
area (Rectangle (Point x1 y1) (Point x2 y2)) = abs (x2 - x1) * abs (y2 - y1)
instance Ord Shape where
compare s1 s2 = compare (area s1) (area s2)
compare vráti LT, EQ alebo GT. Z neho Haskell odvodí <, >, max, maximum, sort…
> Circle (Point 0 0) 1 < Rectangle (Point 0 0) (Point 5 5)
True -- 3.14 < 25
> maximum [Circle (Point 0 0) 1, Rectangle (Point 0 0) (Point 2 2)]
Rectangle (Point 0.0 0.0) (Point 2.0 2.0)
5. Krok 3 – Vlastná typová trieda¶
Úloha 3.1¶
Definujte triedu
Movables metódamimove,reflectX,reflectY,rotate180.
class Movable a where
move :: Vector -> a -> a
reflectX :: a -> a
reflectY :: a -> a
rotate180 :: a -> a
rotate180 = reflectX . reflectY -- predvolená definícia
classlen deklaruje, čo má typ vedieť- otočenie o 180° = zrkadlenie podľa oboch osí → inštancie ho nemusia písať
f . g– skladanie funkcií:(f . g) x = f (g x)
Úloha 3.2¶
Definujte inštancie
MovableprePointaShape.
instance Movable Point where
move (Vec dx dy) (Point x y) = Point (x + dx) (y + dy)
reflectX (Point x y) = Point x (-y)
reflectY (Point x y) = Point (-x) y
instance Movable Shape where
move v (Circle c r) = Circle (move v c) r
move v (Rectangle a b) = Rectangle (move v a) (move v b)
reflectX (Circle c r) = Circle (reflectX c) r
reflectX (Rectangle a b) = Rectangle (reflectX a) (reflectX b)
reflectY (Circle c r) = Circle (reflectY c) r
reflectY (Rectangle a b) = Rectangle (reflectY a) (reflectY b)
- os X → mení sa znamienko
y; os Y → mení sa znamienkox - útvar = operácia na jeho bodoch (volá sa inštancia pre
Point), polomer sa nemení
> move (Vec 1 2) (Point 0 0)
Point 1.0 2.0
> reflectX (Point 3 4)
Point 3.0 (-4.0)
> reflectY (Point 3 4)
Point (-3.0) 4.0
> rotate180 (Point 3 4)
Point (-3.0) (-4.0)
> move (Vec 1 1) (Rectangle (Point 0 0) (Point 2 2))
Rectangle (Point 1.0 1.0) (Point 3.0 3.0)
> rotate180 (Circle (Point 1 2) 5)
Circle (Point (-1.0) (-2.0)) 5.0
6. Krok 4 – Functor a Foldable¶
Úloha 4.1¶
Definujte inštanciu
Functorpre strom.
instance Functor BTree where
fmap f (Leaf x) = Leaf (f x)
fmap f (Branch l r) = Branch (fmap f l) (fmap f r)
fmap = map pre ľubovoľnú štruktúru. Zmení hodnoty, tvar stromu zostane. (Je to mapTree z cvičenia 5.) Pozor: BTree bez a – inštancia je pre „kontajner“, nie pre konkrétny typ.
> fmap (*10) (Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3))
Branch (Branch (Leaf 10) (Leaf 20)) (Leaf 30)
> fmap show (Branch (Leaf 1) (Leaf 2))
Branch (Leaf "1") (Leaf "2")
Úloha 4.2¶
Definujte inštanciu
FoldablepreBTreea implementujtefoldr.
instance Foldable BTree where
foldr f z (Leaf x) = f x z
foldr f z (Branch l r) = foldr f (foldr f z r) l
- list:
fsa aplikuje na hodnotu a počiatočnú hodnotuz - vetva: najprv sa poskladá pravý podstrom, jeho výsledok je počiatočná hodnota pre ľavý
Pre (+) je výsledok rovnaký ako v zadaní (((1+0)+(2+0))+(3+0)). Presne ten tvar sa všeobecne napísať nedá: foldr má typ (a -> b -> b), takže nevie spojiť dva výsledky typu b.
Bonus: s Foldable fungujú na strome automaticky sum, product, length, maximum, elem…
> foldr (+) 0 (Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3))
6
> foldr (:) [] myLittleTree
[1,2,3,4]
> sum myLittleTree
10
> length myLittleTree
4
> maximum myLittleTree
4
> elem 3 myLittleTree
True
7. Prehľad príkazov¶
| príkaz | čo robí | príklad | výstup |
|---|---|---|---|
class |
deklaruje typovú triedu | class Movable a where ... |
– |
instance |
priradí typ do triedy | instance Eq Shape where ... |
– |
deriving |
automatická inštancia | deriving (Eq, Show) |
– |
Eq a => |
obmedzenie typu | allEqual :: Eq a => [a] -> Bool |
– |
all |
platí pre všetky prvky? | all even [2,4] |
True |
(== x) |
sekcia operátora | (== 1) 1 |
True |
min / max |
menšia / väčšia hodnota | min 5 0 |
0 |
compare |
porovnanie (Ord) | compare 1 2 |
LT |
abs |
absolútna hodnota | abs (-3) |
3 |
pi |
číslo π | pi |
3.141592653589793 |
. |
skladanie funkcií | (show . (+1)) 1 |
"2" |
negate / -x |
opačné znamienko | negate 4 |
-4 |
fmap |
map pre Functor | fmap (+1) (Just 1) |
Just 2 |
foldr |
skladanie sprava | foldr (+) 0 [1,2,3] |
6 |
sum / length / maximum / elem |
funkcie z Foldable | sum (Just 5) |
5 |