Lekce 4 - Haskell - Stráže, seznam utíká do nekonečna!
V minulé lekci, Haskell - Tebe bych typoval na funkci..., jsme se naučili dělat funkce. Dnes to rozjedeme ve velkém.
Funkce, zas funkce a možná něco k tomu
Ježíšek dárky nenosí. Pokud jste to nevěděli, omlouvám se, ale to je život. Stejně tak v Haskellu máme více než jen funkce, proměnné a konstanty, čili neřekl jsem vám o existenci dalších struktur. Ale aspoň jsem vám to řekl dříve, než by to udělal někdo jiný. Postupem času to zkusíme napravit.
Nejdříve si obohatíme znalosti o pár datových struktur.
N-tice
První z těch struktur je uspořádaná n-tice. Zapisuje se do kulatých závorek a může obsahovat libovolnou kombinaci typů. Můžeme pomocí nich zobrazit třeba Jana Vachounka, který má 22 let a má z programování na VŠ A:
("Jan Vachounek",22,"programování",'A',)
Nebo dvojice "umístění, jméno" na olympiádě atd...
Páry
Pokud jsou v n-tici pouze dvě hodnoty, říká se jim páry a jsou tak běžné, že máme pro ně v Haskellu zadefinované funkce.
První z nich je fst (first), druhá je snd
(second). Jak asi tušíte, vrátí tu první nebo druhou hodnotu z páru:
fst(34,"ahoj") = 34 snd(34,"ahoj") = "ahoj"
Můžeme si zkusit tyto funkce napsat sami:
fst' (a,b) = a -- fst' (a,_) = a snd' (a,b) = b -- snd' (_,b) = b
Na tomto příkladě si ukážeme 2 věci:
- Prvně jste si určitě všimli znaku
_. V podstatě nám tento znak říká, že nás nezajímá, co je na daném místě, protože to nepotřebujeme. I kdyby byla na druhém místě Šalamounova babička, tak nás jako programátora zajímá jen první místo. - Druhá věc je apostrof na konci funkce. Tato funkce je totiž v Haskellu
již přítomná (build-in) a pokud bychom při jejím předefinování udělali
chybu, tak by funkce, která byla předtím dobře, byla špatně. Je lepší
své vlastní definice psát s apostrofem. A pokud je možnost definovat funkci
více způsoby, tak vždy přidáme apostrof navíc. Např.
inc''' a = ...atd.
Zkuste si teď sami napsat funkce pro trojice, které vrátí první, druhý a třetí prvek, popřípadě z trojice udělají dvojici, která vynechá prostřední prvek.
Seznamy
Když se pozorně podíváme na n-tice, jsou dosti omezené. My nechceme ručně zapisovat každou n-tici, chtěli bychom třeba něco vygenerovat. K tomu slouží seznamy. V seznamu však nohou být uloženy prvky pouze jednoho typu. Např. seznam čísel, seznam stringů, seznam seznamů... Seznamy se oproti n-ticím píší do hranatých závorek:
[1,2,3,3,4,4,5] -- seznam čísel ['a','b','c'] -- seznam znaků [[],[1,2,3],[1,1,1,1,1]] -- seznam seznamů [] -- prázdný seznam
Generování posloupností
Haskell umožňuje generování posloupnosti s nějakým krokem. Posloupnost však musí být aritmetická, tzn. rozdíl mezi každými dvěma sousedními členy musí být stejný. Ukažme si několik příkladů:
[1..20] -- seznam čísel od jedné do dvaceti ['A'..'z'] -- generování seznamu znaků, můžete si všimnout, že mezi 'Z' a 'a' je ještě -- několik znaků navíc (vidíme, že se chary složily -- do stringové notace pomocí apostrofů) ['a'..'Z'] -- generování prázdného seznamu, 'Z' je před 'a'... [3,6..100] -- generování násobků 3, které jsou menší než 100, zde musíme zadat i první krok, -- aby Haskell věděl, po jak velkých úsecích má skákat [12,11..0] -- generování klesající číselné řady [1..] -- generuje nekonečný seznam, k čemu je to dobré uvidíme později
head a tail
Na seznamech už se dají dělat velmi zajímavé věci. Velmi užitečné
funkce pro práci se seznamem jsou head a tail. Head
je hlava seznamu a tail (anglicky ocas) je jeho zbytek:
head [1..10] = 1 tail [1..10] = [2..10] -- všimněme si, že tail je vždy seznam, i kdyby měl být prázdný head [1] = 1 tail [1] = [] head [] .. ERROR -- [] nelze rozložit
Mějme seznam [1,2,3,3,4,4,5]. Tento zápis je však
syntaktická zkratka pro 1:2:3:3:4:4:5:[]. (:)
znamená připojení jednoho prvku (hlavy) na začátek seznamu.
Zkusme si napsat tyto funkce sami:
head' (x:_) = x
tail' (_:xs) = xs
Na seznamu se dají dělat různé magické triky. Nejdříve však musíme rozšířit naši znalost funkcí.
If či guards...
Často se ve funkcích chceme rozhodovat podle nějakého kritéria. Zkusme si napsat funkci, která vezme maximum z páru:
maximum (a,b) = if a > b then a else b
Toto je jedna možnost a uvítají ji hlavně příznivci "ifování". Dá se to samozřejmě napsat elegantně, ale my si ukážeme ještě jeden způsob ifování, tzv. stráže či guards:
maximum (a,b) | a > b = a | otherwise = b
Kód funguje jako zachytávač. Když je a větší, vrátí
a, jinak je výsledek b. V takto krátkém příkladu
je možná vítěz první varianta, co kdybychom měli ale více porovnání,
než jen 2?
Známky
Řekněme, že chceme napsat program, který studentovi řekne, jak úspěšný byl ve škole podle známky, kterou dostal. První možností budou tzv. zástupné vzory:
dostal_jsem 1 = "Jsi šprt!" dostal_jsem 2 = "Nemáš hold na jedničku!" dostal_jsem 3 = "Jsi takový nemastný, neslaný!" dostal_jsem 4 = "Jsi klikař!" dostal_jsem 5 = "Jsi hloupý!" dostal_jsem x = "Už nepij...!"
Tento program vezme známku a pokud student dostal 7, asi to s ním nebylo v
pořádku. Funguje to tak, že kompilátor jede odshora dolů a první řádek,
který odpovídá, tak ten se splní. Kdybychom dali řádek s x
úplně nahoru, tak by odchytl úplně vše. Ale to my nechceme.
Problém je v tom, že je to takové roztáhlé. Zkusme použít
if:
dostal_jsem x = if x == 1 then "Jsi sprt!" else if x == 2 then "Nemas hold na jednicku!" else if x == 3 then "Jsi takovy nemastny, neslany!" else if x == 4 then "Jsi klikar!" else if x == 5 then "Jsi hloupy!" else "Uz nepij...!"
Nyní se na tuto konstrukci if podívejte a už nikdy ji
nepoužívejte. Je to rozvleklé a stále opakujeme to samé. Opravdu, není to
haskellovské a nepoužívá se to. Nejlepší, jedinou, správnou a elegantní
možností jsou stráže. Posuďte sami...
dostal_jsem x
| x == 1 = "Jsi sprt!"
| x == 2 = "Nemas hold na jednicku!"
| x == 3 = "Jsi takovy nemastny, neslany!"
| x == 4 = "Jsi klikar!"
| x == 5 = "Jsi hloupy!"
| otherwise = "Uz nepij...!"
Jakmile vám někdo začne říkat, že je něco jediné a správné, lže.
Jsou situace, kdy je matchování mnohem efektivnější než pomocí stráží,
někdy zas stráže kód zhustí. Je to jako vždy na vás, co se rozhodnete
použít. Je ale zvykem nepoužívat if, protože komunita rozhodla
Nyní, když máme arsenál, můžeme se vrátit k seznamům.
Funkce pro práci se seznamy
Zkusíme si sami zadefinovat několik šikovných funkcí pro práci se seznamy.
Součet všech prvků v seznamu
Kód funkce vracející součet všech prvků v seznamu bude následující:
sum' (x:xs) | xs == [] = x | otherwise = x + sum' xs
Zde můžeme vidět nádherný příklad rekurze, neboli zmenšování
problému. Pokud je seznam jednoprvkový (tail je []),
tak jeho součet je ten jeden prvek. Jinak vezmeme hlavu a přičteme k ní
součet seznamu menšího. Rekurze se zastaví, až se seznam zmenší na
jednoprvkový. Není to jediná možná definice, v další lekci se dozvíme o
další. Pokud jste na ni přišli sami, decentně se dvakrát poplácejte po
pravém rameni.
Zkusme si teď na seznamu [1,2,3,4,5] co přesně kód
dělá:
sum'[1,2,3,4,5] = 1 + sum'[2,3,4,5] = 1 + 2 + sum'[3,4,5] = 1 + 2 + 3 + sum'[4,5] = = 1 + 2 + 3 + 4 + sum'[5] = 1 + 2 + 3 + 4 + 5 = 15
Zkuste si generovat seznamy třeba pomocí sum'[1,35..400030],
opravdu to funguje
Zkuste si sami napsat součin všech prvků v seznamu.
init a last
Kromě head a tail jsou na seznamu funkce
init a last. Funkce init vezme celý
seznam kromě posledního prvku a last přesně naopak. Zkusme si
napsat init:
init' (x:xs)
| xs == [] = []
| otherwise = x : init xs
Pokud je tělo (tail) prázdný seznam, pak funkce skončí a
vrátí prázdnou množinu. Jinak se "zarekurzí". Abychom věděli přesně, co
se děje, zkusme si opět malý příklad:
init' [1,2,3,4,5] = 1: init'[2,3,4,5] = 1 : 2 : init' [3,4,5] = 1 : 2 : 3 : init'[4,5] = = 1 : 2 : 3 : 4 : init'[5] = 1 : 2 : 3 : 4 : [] = [1,2,3,4]
Sami si zkuste napsat last, neboli vrátit poslední prvek v
seznamu.
Délka seznamu
Jako poslední se podíváme na aritmetiku a zkusíme si napsat funkci zjišťující délku seznamu:
length' [] = 0 length' (x:xs) = 1 + length' xs
Zde vyžíváme nejdříve matchování s prázdným seznamem, neboť ten
nemůžeme rozdělit na hlavu a tělo. Když víme, že seznam není prázdný,
můžeme počítat délku jako 1 + zbytek. Pokud je seznam
jednoprvkový, při druhé iteraci se přičte k jedničce 0. A
ano, sum by se dala zjednodušit, vysvětlení kolem se dozvíme v
další lekci.
Zkuste si také napsat:
null' xs -- řekne, zda je xs prázdný seznam reverse' xs -- obrátí seznam take' n xs -- vezme z xs n prvků
