Lekce 3 - Haskell - Tebe bych typoval na funkci...
V minulé lekci, První funkce v Haskell, jsme si vytvořili první jednoduché funkce v Haskell. Dnes budeme pokračovat s datovými typy a vytvoříme si funkce složitější.
Typy
Haskell je silně staticky typovaný jazyk, tzn. všechno má svůj typ a ten
se nemění. Pro zjištění typu slouží zkratka :t následovaná
tím, čehož typ nás zajímá. Zkusme si pár jednoduchých příkladů:
Jaký je typ znaku? Napišme :t 'a':
'a' :: Char -- neboli 'a' má typ Char
A co třeba textu? Zadáme :t "Ahoj světe!":
"Ahoj světe!" :: [Char]
Zde vidíme, že string v Haskellu jako takový neexistuje, je to jen pole znaků.
Typ je něco jako nálepka, aby sám kompilátor věděl, co je ta "věc"
zač. To má řadu výhod, například pokud se pokusíme dělit
Integer typem Boolean, kompiler takový program ani
nepřeloží. Vede to tedy k velké efektivitě. Navíc, oproti nudným
mainstreamovým jazykům, v Haskellu nemusíme explicitně říkat, co je jaký
typ. Až doteď jsme se bez typů obešli. Haskell se sám rozhodne pro vhodný
typ podle toho co definujeme.
Základní typy
Int, Integer, Char,
Float, Double, Bool, n-tice. Vše je asi
jasné, za zmínku stojí rozdíl mezi Int a Integer.
Int se používá pro celá čísla od cca 2147483647
do -2147483648. Tato čísla se mohou lišit, ale pokud budete
blbnout s kalkulačkou, zaručeně skončíte v Integeru. Ten je
totiž neomezený co se týká velikosti, práce s ním ovšem může být proto
o chlup pomalejší.
Typové třídy
Nenechte se zmást objektově orientovaným programováním, typová třída neoznačuje nějaký objekt. Je to rozhraní, které definuje chování.
Num
Zkusme zjistit typ konstanty 8:
:t 8
Výsledek:
8 :: Num a => a.
Num a znamená, že a je nějaké číslo
(Int, Integer, Decimal,... kdo ví) a
tedy patří do typové třídy. Zkuste si:
8 :: Integer 8 :: Int 8 :: Double 8 :: Float.
Už je asi jasné, že pokud vložíme :t 8.0, výsledek nebude
v třídě Num, ale Fractional, podmnožině
Num. 8 tedy dědí vlastnosti z třídy
Num. Může se například k něčemu přičíst atd...
Eq
Eq je typová třída pro ekvivalenci. Pokud ve své funkci
používáte někde test na == či /=, je třeba mít
prvky v této třídě, aby měly možnost být porovnávány.
Ord
Pokud například proměnná a patří do třídy
Ord jako Ordinal, může být porovnána. To se hodí, pokud máte
funkci na větší než a menší než.
Další třídy si probereme, až je budeme potřebovat. Nejčastější
jsou: Eq, Ord, Show (převádí na
řetězec), Read (jakési "Unshow", převádí z řetězce na typ),
Enum (seřazené typy v sekvenci, u kterých lze použít třeba
funkci succ, která vrátí další prvek), dále Num,
Integral, Floating, ...
Typy funkcí
Vezměme si třeba funkce head a tail:
head :: [a] -> a tail :: [a] -> [a]
Co to znamená? Velmi jednoduše, head vezme seznam a vrátí
prvek ze seznamu, tail vezme seznam a vrátí seznam. Prvek
a může být cokoliv, Int, další pole,
String, pár. To není podstatné.
A co třeba taková funkce reverse? Jaký ta má typ?
reverse :: [a] -> [a]
Jednoduché. Co takhle naše funkce mult3?
mult3 :: Int -> Int -> Int -> Int
Tento zápis nám říká jen to, že funkce bere na vstupu tři parametry
typu Int a vrací také Int. Jak to poznáme? No,
jednoduše z definice funkce. Ta vrací pouze jednu hodnotu, takže poslední
typ je vždy návratový. Z toho plynou další věci. Například každá
funkce musí mít alespoň dva typy ve své definici - vstupní a
výstupní.
Jaký bude mít typ třeba fst?
fst :: (a,b) -> a
A tak dále... Proč to vlastně říkáme? Není jedno, jaký má funkce
typ? Vždyť si ho tam Haskell doplní sám. Odpověď zní: ano i ne. Rozhodně
typy psát nemusíte, ale je velmi doporučené je psát. Pokud totiž váš
program funguje tak, jak má, nikdo s ničím nemá problém. Jakmile ale někde
nastane chyba a vy budete luštit, co se děje, chybové hlášky jsou často
velmi nepřehledné. Napište si schválně třídu sum' s
definicí sumy. Pokud vám zdroják nepůjde přeložit, měl by vás Haskell
sám navést k tomu, co vám v ní chybí. Až ji napíšete, zkuste si zadat
sum 1 a sum' 1. A teď jedna malá habaďura. My jsme
si (tedy alespoň já) definovali sum' takto:
sum' :: (Eq a, Num a) => [a] -> a sum' (x:xs) | xs == [] = x | otherwise = x + sum' xs
Vtip je v tom, že jsme mohli svou sum definovat ještě
jinak:
sum'' :: Num a => [a] -> [a] sum'' [] = 0 sum'' (x:xs) = x + sum'' xs
V druhé definici jsme nepotřebovali vůbec třídu Eq. I v tom
je dobré psát vlastní typy funkcí, přesně víte, co váš program dělá a
co dělá navíc.
Chybová hláška u našeho sum' či dokonce sum''
je také mnohem čitelnější, než ta u toho vestavěného. To je jeden z
důvodů, proč se vyplatí definice psát ručně. Další výhoda je
čitelnost. Když napíšete funkci a dobře ji pojmenujete, tak pak už vás
nezajímá vyloženě kód, ale jak tu funkci napojit do vláčku dalších
funkcí, popřípadě jaké argumenty potřebuje. Proto si sami zkuste ke všem
funkcím napsat jejich typy. Pokud budete v koncích, vždy se můžete
inspirovat u Haskellu pomocí funkce :t, ale doporučuji si to
nejdříve zkusit každý sám...
Když bych vám zadal třeba typ funkce replicate, už o ní
víte docela dost:
replicate :: Int -> a -> [a]
Co ta funkce dělá? Vezme Int, vezme něco a pak vrátí pole s
tím něčím. Zkuste teď sami napsat funkci, která dostane n a
prvek a zkopíruje funkci n-krát.
Složitější funkce
Na dnešní lekci máme rovněž slíbené, že si zkusíme implementovat
složitější funkce. Zkusme implementovat trochu složitější funkci
zip:
zip :: [a] -> [b] -> [(a,b)]
Co tato funkce dělá? Vezme dva seznamy a spáruje první s prvním, druhý s druhým atd... dokud alespoň jeden seznam neskončí. Zbytek druhého seznamu zahodí. Na tomto příkladě si opět ukážeme výhodu logického programování. V procedurálních jazycích bychom tuto úlohu řešili nějakým slovníkem, nebo novým polem obsahujícím dvojice, teď ho šikovně alokovat atd... V Haskellu se to píše samo.
Prvně definici:
zip' :: [a] -> [b] -> [(a,b)] -- Pak se musíme podívat na krajní podmínky, aneb kdy má program skončit. zip' [] _ = [] zip' _ [] = [] -- A jsme za půlkou. Nyní už musíme vyřešit samotné párování. zip (x:xs) (y:ys) = (x,y) : zip xs ys
A... to je celé. Nic složitého. Celý program tedy vypadá takto:
zip' :: [a] -> [b] -> [(a,b)] zip' [] _ = [] zip' _ [] = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys
Funkce zip se hodí, když máme např. třídu žáků a chceme
je očíslovat. Tady se navíc ukazuje jedna velmi příjemná vlastnost
Haskellu, jeho lenost. Nepočítá, co nemusí.
zip [1..] ["Kunhuta", "Ctibor", "Vasyl", "Mateo", "Mahulena", "Kvivo", "Naomi", "Stella"]
Zkusme si teď napsat úlohu nahrazení prvku v seznamu:
nahr :: (Eq a) => a -> a -> [a] -> [a]
To je vše, co potřebujeme. Jen se nenechme zmást zápisem. Zde pouze říkáme, že budeme používat všude stejný typ. Můžeme ale mít různé proměnné:
nahr a _ [] = [] nahr a b (x:xs) | x == a = b : nahr a b xs | otherwise = x : nahr a b xs
Je dobrým zvykem ptát se na složitost algoritmu. V Haskellu je to trochu oříšek, protože on sám dělá dost složité optimalizace a jak navíc uvidíme v další lekci, je tzv. líný, takže nepočítá to, co nepotřebuje. To jsme ostatně již viděli u nekonečných seznamů. V příští lekci, Haskell - Stráže, seznam utíká do nekonečna!, si představíme generátory seznamů a temnou magii okolo nich.
