Skip to content

← Späť na FP Labs

Cvičenie 6 – Typové triedy

Useful Files

  1. Základné pojmy
  2. Spoločné typy
  3. Krok 1 – Použitie typových tried
  4. Krok 2 – Definovanie inštancií
  5. Krok 3 – Vlastná typová trieda
  6. Krok 4 – Functor a Foldable
  7. 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:

elem :: Eq a => a -> [a] -> Bool    -- lebo vo vnútri porovnáva cez ==

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:

class Eq a => Ord a where ...
  • stačí písať Ord a => namiesto (Eq a, Ord a) =>
  • instance Ord Shape preto potrebuje aj instance 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 ≈ Java interface (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áti True, ak sú všetky hodnoty v zozname rovné, alebo ak je zoznam prázdny. Aký je typ tejto funkcie?

allEqual :: Eq a => [a] -> Bool
allEqual []     = True
allEqual (x:xs) = all (== x) xs
  • prázdny zoznam → True
  • inak: každý prvok zvyšku sa musí rovnať prvému
  • all p xs – True, ak p platí pre všetky prvky
  • (== x) – funkcia „rovná sa x?“

Typ: Eq a => [a] -> Bool – funguje pre každý typ, ktorý sa dá porovnať cez ==.

> allEqual [1, 1, 1]
True
> allEqual "aab"
False
> allEqual ([] :: [Int])
True

Úloha 1.2

Upravte sumBTree tak, 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 +.

> sumBTree myLittleTree
10
> sumBTree (Branch (Leaf 1.5) (Leaf 2.25) :: BTree Double)
3.75

4. Krok 2 – Definovanie inštancií

Úloha 2.1

Definujte Eq pre Shape tak, 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: normalize vyrobí vždy (ľavý dolný, pravý horný) roh → nezáleží na poradí bodov ani na uhlopriečke
  • _ == _ = False – kruh sa nerovná obdĺžniku
  • Shape nesmie 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ť Ord pre Shape? 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 Movable s metódami move, 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
  • class len 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 Movable pre Point a Shape.

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 znamienko x
  • ú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 Functor pre 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 Foldable pre BTree a implementujte foldr.

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: f sa aplikuje na hodnotu a počiatočnú hodnotu z
  • 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

Top