Haskell a funkcionální programování (4)

Minule byla řeč o datových typech a funkcích. Souvislost s oběma tématy má tzv. signatura typu. Touto jazykovou konstrukcí lze explicitně určit, kolik má mít funkce parametrů, jakého jsou typu a co má funkce vracet. Ve většině případů není nutné signaturu typu uvádět, protože Haskell je schopen odvodit si ji sám z příslušných deklarací. Toho jsme doteď využívali i v našich příkladech. Jenom připomenu, že v prostředí hugs lze signaturu typu jednoduše určit pomocí příkazu :t jméno. Jako příklad si můžeme vzít funkci kvadrat počítající kořeny kvadratické rovnice

kvadrat 0 0 _  = error "Chybne zadani"
kvadrat 0 b c  = let r = - c / b in (r,r)
kvadrat a b c | d < 0     = error "V oboru realnych cisel neni reseni"
              | otherwise = (((b + diskr) / jmen), ((b - diskr) / jmen))
            where
                d     = b*b - 4*a*c
                diskr = sqrt d
                jmen  = 2*a

Signatura typu, kterou naší funkci Haskell přiřadí, vypadá následovně

kvadrat :: Float -> Float -> Float -> (Float,Float)

První je samozřejmě identifikátor, jehož typ signatura určuje. Za čtyřtečkou následuje seznam typů parametrů oddělených ‚šipkou‘. Jako poslední je uveden typ výsledku. Z vypsané signatury můžeme vidět, že funkce kvadrat má tři parametry typu Float a jejím výsledkem je uspořádaná dvojice s prvky typu Float. Jelikož ale Haskell podporuje polymorfismus, lze v signatuře uvádět kromě konkrétních typů (resp. typových konstruktorů) i typy polymorfní. Funkce length určující délku (libovolného) seznamu definovaná v modulu Prelude nám ukazuje, jakým způsobem to provést.

length :: [a] -> Int

Její signatura nám říká, že jako parametr předpokládá funkce seznam prvků libovolného typu (označeno [a]) a jako výsledek vrací celé číslo (Int). Aniž bychom věděli cokoliv bližšího o funkci nazvané zipWith, mužeme podle její signatury typu

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

prohlásit, že jako první parametr očekává libovolnou funkci, která má jeden parametr typu a, druhý parametr typu b a vrací hodnotu typu c. Dalším parametrem zipWith je seznam prvků typu a, seznam prvků typu b a jako výsledek vrací seznam prvků typu c. Typy a, b a c jsou opět polymorfní a mohou být navzájem různé. Někdy může být žádoucí omezit míru polymorfnosti nějakou dodatečnou vlastností. Má-li funkce provádět například řazení seznamu, je vhodné omezit platnost deklarace pouze na typy, pro které existuje alespoň relace menší nebo rovno. Jako vůbec první příklad funkce v Haskellu jsem uváděl implementaci QuickSortu. Jenom pro připomenutí, deklarace vypadá následovně

qsort []     = []
qsort (x:xs) = qsort mensi ++ [x] ++ qsort vetsi_rovno
               where
                  mensi        = [ y | y <- xs, y < x]
                  vetsi_rovno  = [ y | y <- xs, y <= x]

Z předchozího kódu bychom mohli sami určit signaturu typu

qsort :: [a] -> [a]

Použijeme-li ale v hugs příkaz :t qsort, vypíše se

qsort :: Ord a => [a] -> [a]

Nová část v signatuře je onou omezující podmínkou, o které byla řeč – polymorfní typ a musí být instancí typové třídy Ord. Aby mohl být nějaký typ instancí Ord, musí mít přetíženy operátory pro porovnávání, a právě to je pro řazení seznamu zapotřebí. Jak taková definice třídy vypadá? Pro začátek můžeme jako vzor použít třeba třídu Eq deklarovanou v modulu Prelude

class Eq a where
    (==), (/=) :: a -> a -> Bool

Tento zápis říká, že typ a, který má být instancí Eq, musí mít definovány operátory rovnosti (==) a nerovnosti (/=). Je ale celkem zbytečné definovat oba operátory, když lze jednoduše jeden vyjádřit pomocí druhého. Tuto skutečnost můžeme zapsat pomocí následujících dvou rovnic, které přidáme k deklaraci třídy Eq

    x == y  = not (x/=y)
    x /= y  = not (x==y)

Nyní stačí, když instance přetíží pouze jeden z operátorů a druhý se určí z předchozích rovnic. Jak provést přetížení, uvidíme v následujícím příkladu. Nejdříve definujme nový datový typ Dny

data Dny = Pondeli | Utery | Streda | Ctvrtek
           | Patek | Sobota | Nedele

Následujícím kódem deklarujeme datový typ Dny jako instanci typové třídy Eq

instance Eq Dny where

  Pondeli == Pondeli = True
  Utery   == Utery   = True
  Streda  == Streda  = True
  Ctvrtek == Ctvrtek = True
  Patek   == Patek   = True
  Sobota  == Sobota  = True
  Nedele  == Nedele  = True
  _       == _       = False

Typickou vlastností objektů (resp. tříd) je dědičnost. V tomto směru není ani Haskell výjimkou. Příkladem dědičnosti může být dříve zmiňovaná třída Ord, která je potomkem třídy Eq. Tento vztah se zapisuje následovně

class (Eq a) => Ord a where

-- dále následují signatury typu ...

Jelikož je Haskell funkcionálním programovacím jazykem, jsou seznamy jedním z jeho základních stavebních kamenů. Tuto skutečnost mohl pozorný čtenář zaznamenat už v prvním díle našeho povídání. Protože opakování je matkou moudrosti a od vydání prvního dílu už nějaký ten čas uplynul, ještě jednou shrnu základy práce se seznamy v Haskellu. Prázdný seznam se značí []. Zápis 1:2:3:[] reprezentuje seznam čísel 1, 2 a 3. Totéž, ale přehledněji lze zapsat jako [1,2,3]. Seznam čísel od 1 do 20 lze zkráceně generovat pomocí výrazu [1..20]. Podobným způsobem můžeme získat libovolnou aritmetickou posloupnost. Tak schválně, co asi vznikne z výrazu [10,8..(-10)]. Řetězce lze zapisovat jednak [‚a‘,‚b‘,‚c‘,‚d‘], ale také klasickým stylem „abcd“. Užitečnou konstrukcí jazyka je generátor seznamů. Čísla dělitelná pěti, která jsou menší než třicet, snadno získáme pomocí výrazu

[ x | x <- [1..30], x `mod` 5 == 0]

Tento zápis nám říká – ve výsledném seznamu chceme všechna x ze seznamu [1..30] taková, že zbytek po dělení x pěti je nulový. Generátor seznamů jsme použili už dříve při deklaraci funkce qsort (resp. pomocných funkcí mensi a vetsi_rovno). V části před svislou čarou můžeme použít x jako část výrazu a logický výraz omezující výběr prvků lze vynechat.

[ toUpper x | x <- "Funkcionalni programovani" ]

Pro spojování dvou seznamů je v modulu Prelude definován operátor ++ :: [a] → [a] → [a], který opět známe z funkce qsort. Délku seznamu určí funkce length :: [a] → Int. Prvních n prvků ze seznamu můžeme získat pomocí funkce take :: Int → [a] → [a]. Naopak posledních n prvků vrací funkce drop :: Int → [a] → [a]. Součet (resp. součin) všech prvků seznamu lze vypočíst voláním funkce sum :: Num a ⇒ [a] → a (resp. product :: Num a ⇒ [a] → a). Obrátit pořadí prvků v seznamu můžeme pomocí funkce reverse :: [a] → [a]. V modulu Prelude je kromě právě jmenovaných i množství dalších funkcí nejen pro práci se seznamy. Popsat je všechny je ale mimo rámec tohoto seriálu.

Jelikož se dneska na práci se soubory nedostalo, bude jí věnována podstatná část příštího dílu. Celé povídání o Haskellu poté uzavřu demonstrací toho, jak formálně dokázat správnost programu (resp. jeho části).