4. diel - Haskell - Stráže, zoznam uteká do nekonečna!

V minulej lekcii, Haskell - Teba by som typoval na funkciu ... , sme sa naučili robiť funkcie. Dnes to rozbehneme vo veľkom.

Funkcie, zas funkcie a možno niečo k tomu

Ježiško darčeky nenosí. Ak ste to nevedeli, ospravedlňujem sa, ale to je život. Rovnako tak v Haskell máme viac ako len funkcie, premenné a konštanty, čiže nepovedal som vám o existencii ďalších štruktúr. Ale aspoň som vám to povedal predtým, než by to urobil niekto iný. Postupom času to skúsime napraviť.

Najskôr si obohatíme vedomosti o pár dátových štruktúr.

N-tica

Prvý z tých štruktúr je usporiadaná n-tica. Zapisuje sa do okrúhlych zátvoriek a môže obsahovať ľubovoľnú kombináciu typov. Môžeme pomocou nich zobraziť treba Jána Vachounka, ktorý má 22 rokov a má z programovania na VŠ A:

("Jan Vachounek",22,"programování",'A',)

Alebo dvojica "umiestnenie, meno" na olympiáde atd ...

Pary

Pokiaľ sú v n-ticu len dve hodnoty, hovorí sa im pary a sú tak bežné, že máme pre nich v Haskell zadefinované funkcie.

Prvý z nich je fst (first), druhá je snd (second). Ako asi tušíte, vráti tú prvú alebo druhú hodnotu z páru:

fst(34,"ahoj") = 34
snd(34,"ahoj") = "ahoj"

Môžeme si skúsiť tieto funkcie napísať sami:

fst' (a,b) = a    -- fst' (a,_) = a
snd' (a,b) = b    -- snd' (_,b) = b

Na tomto príklade si ukážeme 2 veci:

• Najprv ste si určite všimli znaku _. V podstate nám tento znak hovorí, že nás nezaujíma, čo je na danom mieste, pretože to nepotrebujeme. Aj keby bola na druhom mieste Šalamúnovho babička, tak nás ako programátora zaujíma len prvé miesto.
• Druhá vec je apostrof na konci funkcie. Táto funkcia je totiž v Haskell už prítomná (build-in) a ak by sme pri jej predefinovanie urobili chybu, tak by funkcia, ktorá bola predtým dobre, bola zle. Je lepšie svoje vlastné definície písať s apostrofom. A ak je možnosť definovať funkciu viacerými spôsobmi, tak vždy pridáme apostrof navyše. Napr. inc''' a = ... atď.

Skúste si teraz sami napísať funkcie pre trojice, ktoré vráti prvý, druhý a tretí prvok, poprípade z trojice urobia dvojicu, ktorá vynechá prostredný prvok.

Zoznamy

Keď sa pozorne pozrieme na n-tica, sú dosť obmedzené. My nechceme ručne zapisovať každú n-ticu, chceli by sme treba niečo vygenerovať. K tomu slúži zoznamy. V zozname však nôh byť uložené prvky iba jedného typu. Napr. zoznam čísel, zoznam stringov, zoznam zoznamov ... Zoznamy sa oproti n-ciám píšu do hranatých zátvoriek:

[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

Generovanie postupností

Haskell umožňuje generovanie postupnosti s nejakým krokom. Postupnosť však musí byť aritmetická, tzn. rozdiel medzi každými dvoma susednými členmi musí byť rovnaký. Ukážme si niekoľko príkladov:

[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 zoznamoch už sa dajú robiť veľmi zaujímavé veci. Veľmi užitočné funkcie pre prácu so zoznamom sú head a tail. Head je hlava zoznamu a tail (anglicky chvost) je jeho zvyšok:

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

Majme zoznam [1,2,3,3,4,4,5]. Tento zápis je však syntaktická skratka pre 1:2:3:3:4:4:5:[]. (:) znamená pripojenie jedného prvku (hlavy) na začiatok zoznamu.

Skúsme si napísať tieto funkcie sami:

head' (x:_) = x
tail' (_:xs) = xs

Na zozname sa dajú robiť rôzne magické triky. Najskôr však musíme rozšíriť našu znalosť funkcií.

If či guards ...

Často sa vo funkciách chceme rozhodovať podľa nejakého kritéria. Skúsme si napísať funkciu, ktorá zoberie maximum z páru:

maximum (a,b) = if a > b then a else b

Toto je jedna možnosť a uvítajú ju hlavne priaznivci "ifování". Dá sa to samozrejme napísať elegantne, ale my si ukážeme ešte jeden spôsob ifování, tzv. Stráže či guards:

maximum (a,b)
    | a > b = a
    | otherwise = b

Kód funguje ako zachytávač. Keď je a väčšie, vráti a, inak je výsledok b. V takto krátkom príklade je možná víťaz prvý variant, čo keby sme mali ale viac nákupný, než len 2?

Známky

Povedzme, že chceme napísať program, ktorý študentovi povie, ako úspešný bol v škole podľa známky, ktorú dostal. Prvou možnosťou budú 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 ak študent dostal 7, asi to s ním nebolo v poriadku. Funguje to tak, že kompilátor jede odhora dolu a prvý riadok, ktorý zodpovedá, tak ten sa splní. Keby sme dali riadok s x úplne hore, tak by odchytl úplne všetko. Ale to my nechceme.

Problém je v tom, že je to také roztiahli. Skúsme použiť 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...!"

Teraz sa na túto konštrukciu if pozrite a už nikdy ju nepoužívajte. Je to rozvleklé a stále opakujeme to isté. Naozaj, nie je to haskellovské a nepoužíva sa to. Najlepšie, jedinou, správnu a elegantný možnosťou sú stráže. Posúď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...!"

Akonáhle vám niekto začne hovoriť, že je niečo jediné a správne, klame. Sú situácie, kedy je matchování oveľa efektívnejšie ako pomocou stráží, niekedy zas stráže kód zhustí. Je to ako vždy na vás, čo sa rozhodnete použiť. Je ale zvykom nepoužívať if, pretože komunita rozhodla

Teraz, keď máme arzenál, môžeme sa vrátiť k zoznamom.

Funkcie pre prácu so zoznamami

Skúsime si sami zadefinovať niekoľko šikovných funkcií pre prácu so zoznamami.

Súčet všetkých prvkov v zozname

Kód funkcie vracajúce súčet všetkých prvkov v zozname bude nasledujúci:

sum' (x:xs)
   | xs == [] = x
   | otherwise = x + sum' xs

Tu môžeme vidieť nádherný príklad rekurzia, čiže zmenšovanie problému. Ak je zoznam jednoprvková (tail je []), tak jeho súčet je ten jeden prvok. Inak vezmeme hlavu a pripočítame k nej súčet zoznamu menšieho. Rekurzia sa zastaví, až sa zoznam zmenší na jednoprvková. Nie je to jediná možná definícia, v ďalšej lekcii sa dozvieme o ďalšie. Ak ste na ňu prišli sami, decentne sa dvakrát poťapkajte po pravom ramene.

Skúsme si teraz na zozname [1,2,3,4,5] čo presne kód robí:

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

Skúste si generovať zoznamy treba pomocou sum'[1,35..400030], naozaj to funguje

Skúste si sami napísať súčin všetkých prvkov v zozname.

Init a last

Okrem head a tail sú na zozname funkcie init a last. Funkcia init vezme celý zoznam okrem posledného prvku a last presne naopak. Skúsme si napísať init:

init' (x:xs)
  | xs == [] = []
  | otherwise = x : init xs

Ak je telo (tail) prázdny zoznam, potom funkcia skončí a vráti prázdnu množinu. Inak sa "zarekurzí". Aby sme vedeli presne, čo sa deje, skúsme si opäť malý prí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 skúste napísať last, čiže vrátiť posledný prvok v zozname.

Dĺžka zoznamu

Ako posledný sa pozrieme na aritmetiku a skúsime si napísať funkciu zisťujúci dĺžku zoznamu:

length' [] = 0
length' (x:xs) = 1 + length' xs

Tu vyžívajú najskôr matchování s prázdnym zoznamom, lebo ten nemôžeme rozdeliť na hlavu a telo. Keď vieme, že zoznam nie je prázdny, môžeme počítať dĺžku ako 1 + zbytek. Ak je zoznam jednoprvková, pri druhej iterácii sa pripočíta k jednotke 0. A áno, sum by sa dala zjednodušiť, vysvetlenie okolo sa dozvieme v ďalšej lekcii.

Skúste si tiež napísať:

null' xs    -- řekne, zda je xs prázdný seznam
reverse' xs -- obrátí seznam
take' n xs  -- vezme z xs n prvků