Zimní výprodej C/C++ week
Pouze tento týden sleva až 80 % na e-learning týkající se C/C++
40 % bodů zdarma díky naší Zimní akci!

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

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

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ů

 

 

Článek pro vás napsal Tricerator
Avatar
Jak se ti líbí článek?
3 hlasů
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Předchozí článek
Haskell - Tebe bych typoval na funkci...
Všechny články v sekci
Haskell
Aktivity (3)

 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!