Vlastní jednoduché datové typy,
konstruktor Maybe, rekurzivní datové typy
IB015 Neimperativní programování
Kolektiv cvičících IB015
Fakulta informatiky, Masarykova univerzita
podzim 2018
IB015: Cvičení 05 podzim 2018 1 / 16
Opakování
Naprogramujte funkci intersection :: Real a => [(a, a,
a)] -> [((a, a, a), (a, a, a))], která vezme seznam
kružnic v rovině reprezentovaných trojicí (x, y, r), kde x, y jsou
souřadnice, r je poloměr, a vrátí seznam dvojic kružnic, které se
navzájem protínají.
Naprogramujte funkci noIntersection :: Real a => [(a,
a, a)] -> [(a, a, a)], která bere seznam kružnic v rovině a
vrací seznam kružnic, které se neprotínají s žádnou jinou.
IB015: Cvičení 05 podzim 2018 2 / 16
Vlastní datové typy
Příklad 5.1.1: Mějme datový typ Day představující dny v týdnu
definovaný níže. Definujte funkci weekend :: Day -> Bool,
která o zadaném dni určí, jestli je to víkendový den.
data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun
            deriving (Show, Eq, Ord)
IB015: Cvičení 05 podzim 2018 3 / 16
Vlastní datové typy
Příklad 5.1.1: Mějme datový typ Day představující dny v týdnu
definovaný níže. Definujte funkci weekend :: Day -> Bool,
která o zadaném dni určí, jestli je to víkendový den.
data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun
            deriving (Show, Eq, Ord)
jednotlivé možné hodnoty se oddělují svislítkem
deriving část říká, do kterých typových tříd má typ patřit
(instance se odvodí automaticky)
IB015: Cvičení 05 podzim 2018 3 / 16
Vlastní datové typy
data Shape = Circle Double
               | Rectangle Double Double
               | Point
               deriving (Eq, Show)
Uveďte příklady různých hodnot typu Shape.
Jakého typu jsou výrazy Circle, Rectangle, Point?
IB015: Cvičení 05 podzim 2018 4 / 16
Hodnotové a typové konstruktory I.
data Shape = Circle Double
               | Rectangle Double Double
               | Point
               deriving (Eq, Show)
Shape je (nulární) typový konstruktor
tři hodnotové konstruktory (funkce vytvářející hodnoty typu
Shape):
unární: Circle :: Double -> Shape
binární: Rectangle :: Double -> Double -> Shape
nulární: Point :: Shape
hodnotové i typové kostruktory začínají velkým písmenem
(nebo dvojtečkou)
IB015: Cvičení 05 podzim 2018 5 / 16
Hodnotové a typové konstruktory II.
Hodnotové konstruktory lze použít v definici podle vzoru:
null :: [a] -> Bool
null []      = True
null (_:_) = False
[] a (:) jsou hodnotové konstruktory typu [a]
Hodnotové konstruktory jsou first-class citizens (stejně jako
funkce), tedy můžeme je ve výrazech jako funkce používat.
(Circle . (*2)) 2.5 ∗ Circle 5.0
IB015: Cvičení 05 podzim 2018 6 / 16
Hodnotové a typové konstruktory: příklad
data Shape = Circle Double
               | Rectangle Double Double
               | Point
               deriving (Eq, Show)
Naprogramujte funkci area :: Shape -> Double, která spočítá
obsah zadaného tvaru.
area (Circle 1) ∗ 3.141592653589793
area (Rectangle 2 2) ∗ 4
area Point ∗ 0
IB015: Cvičení 05 podzim 2018 7 / 16
Datový typ Maybe a
Definice (z Prelude):
data Maybe a = Nothing | Just a
                  deriving (Eq, Ord, Show, Read)
parametrizovaný datový typ Maybe a → konkrétní typy:
Maybe Int, Maybe [String], Maybe (Int, [Bool]),. . .
reprezentuje hodnotu, jejíž výpočet může selhat
hodnota může být přítomna (Just 1) nebo chybět (Nothing)
hodnoty extrahujeme pomocí vzorů
za povšimnutí stojí funkce fromMaybe z modulu Data.Maybe
nebo lookup
fromMaybe :: a -> Maybe a -> a
IB015: Cvičení 05 podzim 2018 8 / 16
Datový typ Maybe a
Definice (z Prelude):
data Maybe a = Nothing | Just a
                  deriving (Eq, Ord, Show, Read)
parametrizovaný datový typ Maybe a → konkrétní typy:
Maybe Int, Maybe [String], Maybe (Int, [Bool]),. . .
reprezentuje hodnotu, jejíž výpočet může selhat
hodnota může být přítomna (Just 1) nebo chybět (Nothing)
hodnoty extrahujeme pomocí vzorů
za povšimnutí stojí funkce fromMaybe z modulu Data.Maybe
nebo lookup
fromMaybe :: a -> Maybe a -> a
fromMaybe x Nothing   = x
fromMaybe _ (Just y) = y
IB015: Cvičení 05 podzim 2018 8 / 16
Datový typ Maybe a: příklad
Příklad 5.2.2: S využitím typového konstruktoru Maybe definujte
funkci
divlist :: Integral a => [a] -> [a] -> [Maybe a], která
celočíselně podělí dva celočíselné seznamy „po složkách“, tj.
divlist [x1, ..., xn] [y1, ..., yn]
      ∗ [div x1 y1, ..., div xn yn]
divlist [12, 5, 7] [3, 0, 2] ∗ [Just 4, Nothing,
Just 3]
a ošetří případy dělení nulou.
IB015: Cvičení 05 podzim 2018 9 / 16
Rekurzivní datové typy
Zamyslete se, jak byste definovali vlastní datový typ reprezentující
seznamy v Haskellu.
IB015: Cvičení 05 podzim 2018 10 / 16
Rekurzivní datové typy
Zamyslete se, jak byste definovali vlastní datový typ reprezentující
seznamy v Haskellu.
data MyList a = Empty | ListElement a (MyList a)
Uveďte příklady různých hodnot typu MyList a
IB015: Cvičení 05 podzim 2018 10 / 16
Rekurzivní datové typy: příklad
Příklad 5.1.6: Uvažme následující definici typu Expr:
data Expr = Con Float
               | Add Expr Expr | Sub Expr Expr
               | Mul Expr Expr | Div Expr Expr
a) Uveďte výraz typu Expr, který představuje hodnotu 3.14.
b) Definujte funkci eval :: Expr -> Float, která vrátí hodnotu
daného výrazu.
IB015: Cvičení 05 podzim 2018 11 / 16
Binární stromy
Uvažme následující definici binárních stromů:
data BinTree a = Empty
                     | Node a (BinTree a) (BinTree a)
Identifikujte v definici hodnotové a typové kostruktory a
určete jejich aritu.
Zkuste pomocí tohoto datového typu zapsat stromy zobrazené
níže.
∅ 1 1
3
54
2
1
2
3
V nasledujících příkladech by se vám mohl hodit soubor s
předdefinovanými stromy na testování.
IB015: Cvičení 05 podzim 2018 12 / 16
Binární stromy: příklady
Příklad 5.3.3: Uvažte následující rekurzivní datový typ
představující binární strom s ohodnocenými uzly:
data BinTree a = Empty
                     | Node a (BinTree a) (BinTree a)
Definujte následující funkce nad binárními stromy:
a) treeSize :: BinTree a -> Integer, která spočítá počet
uzlů ve stromě.
b) listTree :: BinTree a -> [a], která převede všechny
hodnoty uzlů ve stromu do seznamu.
c) height :: BinTree a -> Int, která určí výšku stromu.
d) longestPath :: BinTree a -> [a], která najde nejdelší
cestu ve stromě začínající v kořeni a vrátí ohodnocení na ní.
IB015: Cvičení 05 podzim 2018 13 / 16
Binární stromy: příklady
Příklad 5.3.4: Pro datový typ BinTree a označíme výškou
stromu počet uzlů na cestě z kořene do nejvzdálenějšího listu.
a) Definujte funkci fullTree :: Int -> a -> BinTree a,
která pro volání fullTree n v vytvoří binární strom výšky n,
ve kterém jsou všechny větve stejně dlouhé a všechny uzly
ohodnocené hodnotou v.
b) Definujte funkci
treeZip :: BinTree a -> BinTree b -> BinTree (a,b)
jako analogii seznamové funkce zip. Výsledný strom tedy
obsahuje pouze ty uzly, které jsou v obou vstupních stromech.
IB015: Cvičení 05 podzim 2018 14 / 16
Binární stromy: příklady
Příklad 5.3.5: Uvažme datový typ BinTree a.
a) Definujte funkci treeRepeat :: a -> BinTree a jako
analogii seznamové funkce repeat. Funkce tedy vytvoří
nekonečný strom, který má zadanou hodnotu v každém uzlu.
b) Pomocí funkce treeRepeat vyjádřete nekonečný binární strom
nilTree, který má v každém uzlu prázdný seznam.
c) Definujte funkci
treeIterate :: (a->a) -> (a->a) -> a -> BinTree a
jako analogii seznamové funkce iterate. Levý potomek
každého uzlu bude mít hodnotu vzniklou aplikací první zadané
funkce a pravý aplikací druhé zadané funkce.
IB015: Cvičení 05 podzim 2018 15 / 16
Binární stromy: příklady
Příklad 5.3.8: Uvažme datový typ BinTree a.
a) Definujte funkci
isTreeBST :: (Ord a) => BinTree a -> Bool, která se
vyhodnotí na True, jestli bude její první argument validní
binární vyhledávací strom.
b) Definujte funkci
searchBST :: (Ord a) => a -> BinTree a -> Bool,
která projde BST z druhého argumentu v smyslu binárního
vyhledávání a vyhodnotí se na True v případe, že její první
argument najde v uzlech při vyhledávání.
IB015: Cvičení 05 podzim 2018 16 / 16