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

Jak jsem už předeslal v minulém dílu, dneska by měl být na řadě úvod do programování v Haskellu. Upozorňuji, že to bude opravdu jen rychlokurz, a ne všeobsahující a vyčerpávající učebnice jazyka. Pro čtenáře, kteří by měli o Haskell hlubší zájem, bych doporučil, samozřejmě až po absolvování tohoto článku :-), dokumenty A Gentle Introduction to Haskell a Haskell 98 report, které lze spolu s dalšími odkazy na literaturu najít na domovské stránce www.haskell.org

Struktura programu

Na nejvyšší úrovni se program skládá z modulů. Moduly poskytují možnost opakovaného použití existujícího a odladěného kódu v nových projektech (tzv. code re-use). Také umožňují kontrolu nad prostorem jmen – každý modul má vlastní prostor jmen a ven se exportují jen zadaná jména (funkcí, datových typů, tříd …) Jeden z modulů se musí jmenovat Main a musí obsahovat funkci jménem main. Tím je jednoznačně určeno, kde má výpočet začít (běh programu je vlastně ekvivalentní vyhodnocení funkce main). Hlavička modulu může vypadat např. takto:

module Sorting (quickSort, bubbleSort, mergeSort) where

import Maybe
import SortUtils hiding (merge)

Jméno modulu (v našem případě Sorting) je uvozeno klíčovým slovem module. Dále následuje nepovinný seznam exportovaných jmen uzavřený v závorkách. Začátek vlastního modulu uvozuje klíčové slovo where, poté následuje opět nepovinná sekce importů. Klíčové slovo import je následováno jménem modulu, který chceme použít, a případně v závorkách uzavřeným seznamem identifikátorů, jež se mají importovat. Druhá varianta importu má nepovinnou část se seznamem jmen uvozenou klíčovým slovem hiding. Identifikátory zde uvedené nebudou z daného modulu importovány.

Jednou ze zajímavostí struktury programu v Haskellu je i vlastní formát zápisu zdrojového kódu. Existují dvě metody, jak psát. První způsob, stejný jako v jiných (imperativních) jazycích je, že každý řádek programu je chápán jako zdrojový kód a komentáře jsou vyznačeny explicitně. V Haskellu existují dva druhy komentářů – jednořádkový je uvozen znaky – (dva mínusy) a víceřádkový začíná znaky {- (složená závorka mínus)a končí -} (mínus složená závorka). Pokud má zdrojový soubor příponu .hs, očekává se právě tento formát. Haskell ale nabízí i jiný přístup – tzv. literate programming (myšlenku literárního programování propagoval Donald Knuth, známý mimo jiné i jako autor TeXu). Na problém zápisu zdrojového kódu se nahlíží z opačné strany. Pokud není prvním znakem na řádku > (větší než), je text považován za komentář. Dalším pravidlem je, že mezi blokem komentáře a blokem kódu musí být alespoň jeden prázdný řádek. Jenom pro zajímavost, existuje ještě jeden způsob literárního zápisu programu. Komentáře jsou opět implicitní a kód je uzavírán do sekce \begin{code} \end{code}. Soubory napsané stylem literate programming se pyšní příponou .lhs

Haskell rozlišuje mezi velkými a malými písmeny, takže zipWith a ZipWith jsou dva rozdílné identifikátory. K pravidlům zápisu kódu v Haskellu patří také to, že jména funkcí a proměnných povinně začínají malým písmenem a identifikátory datových typů a konstruktorů či tříd a jména modulů se musí psát s velkým počátečním písmenem.

Zvláštností Haskellu je, že ve zdrojovém kódu není nutné (a ani obvyklé) uvádět středníky ukončující výraz nebo složené závorky vymezující blok kódu. Jejich funkci přebírá formátování vlastního zdrojového kódu (layout). Princip je následující – kód, který patří do jednoho bloku, má stejné odsazení od začátku řádky. Vnořený blok má větší odsazení než blok nadřazený. Jako ukázka by mohla posloužit funkce qsort z minula, ale proč nepřijít s něčím novým … Takže tady je příklad funkce, která otočí pořadí prvků v seznamu

otoc xs = obrat xs []
      where
        obrat [] ys     = ys
        obrat (x:xs) ys = obrat xs (x:ys)

Začátečníkům může formátování textu (respektive jeho ignorování) působit problémy v podobě chybových hlášek se zněním : Syntax error in input (unexpected symbol „xyz“). Následující kód, který je na první pohled totožný s předchozím, způsobí při překladu chybu (rovnice definující funkci obrat nemají stejné odsazení)

otoc xs = obrat xs []
      where
         obrat [] ys     = ys
        obrat (x:xs) ys  = obrat xs (x:ys)

Pro zatvrzelé odpůrce formátování nabízí Haskell použití složených závorek a středníků. Chybu z poslední ukázky lze odstranit třeba takto

otoc xs = obrat xs []
    where {
             obrat [] ys     = ys ;
        obrat (x:xs) ys = obrat xs (x:ys) }

Datové typy

Mezi základní datové typy v Haskellu patří Int, Integer, Char, Bool a Float. Pokud někoho zarazila existence dvou typů celých čísel, vězte, že velikost Int je omezena (co nabídne procesor), kdežto Integer má neomezený rozsah (výpočty ale trvají déle). Z existujících typů může uživatel samozřejmě odvodit typy vlastní. Například String je (celkem logicky) definován jako seznam znaků

type String = [Char]

Obě pojmenování ale přitom zůstávají rovnocenná, takže deklarace pomocí type se dá chápat asi jako alias. Ze všech typů lze samozřejmě vytvářet i seznamy. Zajímavou a užitečnou vlastností je možnost definice uspořádaných n-tic. Ty se tvoří jako posloupnosti prvků oddělených čárkou uzavřené v kulatých závorkách. Mějme například následující definici adresy

type Adresa = (Ulice, Obec, PSC)
type Ulice  = (String, Integer)
type Obec   = String
type PSC    = Integer

N-tice odpovídající typu Adresa může vypadat takto

(("tř. 17 listopadu", 15), "Ostrava - Poruba", 70833)

Kromě aliasů a n-tic lze v Haskellu vytvářet nové uživatelské typy pomocí deklarace data. Nejlepší bude ukázat si takovou definici na příkladu.

data Barvy = Fialova | Modra | Zelena | Zluta | Cervena

Touto deklarací zavedeme nový typový konstruktor se jménem Barvy. Identifikátory Fialova, Modra, Zelena, Zluta a Cervena představují tzv. datové konstruktory. Náš nově definovaný typ je příkladem výčtového typu – je tvořen konečným počtem nulárních (tj. takových, které nemají žádný parametr) datových konstruktorů. Mezi výčtové typy patří i Bool, Char a Int. Samozřejmě lze kombinovat datové konstruktory s různou aritou (počtem parametrů)

data Maybe a = Just a | Nothing

Datové konstruktory mohou také obsahovat rekurzi, jako například následující deklarace binárního stromu.

data Strom a = List a | Uzel (Strom a) (Strom a)

Práci s novým typem může demonstrovat funkce převádějící strom na seznam

udelejSeznam (List a)   = [a]
udelejSeznam (Uzel l p) = udelejSeznam l ++ udelejSeznam p

Jen pro pořádek připomenu, že ++ je infixový operátor spojující dva seznamy. Konstantu typu Strom můžeme definovat takto

pozdrav = Uzel (List "Dobry") (Uzel (List "den") (List "!"))

A tady je výsledek převodu konstanty pozdrav ze stromu na seznam

["Dobry","den","!"]

Deklarace funkcí

Funkce, jak už je asi zřejmé z předchozích příkladů, se v Haskellu deklarují jako rovnice. Využívá se přitom tzv. pattern matching (unifikace vzorů). Zjednodušeně to znamená asi tolik, že při vyhodnocování funkce se použije ta rovnice, jejíž vzor (část deklarace před rovnítkem) odpovídá zadaným parametrům (vyhovuje počet, typ, hodnota). Existuje několik možných typů vzorů. Nejjednoduššími z nich jsou proměnná a konstanta. Jejich použití demonstruje následující příklad

faktorial  0 = 1
faktorial  n = n * faktorial (n - 1)

Jako vzor může sloužit samozřejmě i seznam. Příklad ukazuje, jak lze určit délku seznamu

delka [] = 0
delka (x:xs) = 1 + delka xs

V druhé rovnici je jako parametr užit vzor x:xs, který představuje seznam s prvním prvkem x a zbytkem xs. Vzory tohoto typu musí být uzavřeny v kulatých závorkách. V jednom vzoru lze také míchat dohromady proměnné a konstanty (např. vzoru (7:3:xs) vyhovuje seznam začínající číslem 7, za kterým následuje číslo 3 a poté nějaký, možná i prázdný zbytek xs). Drobnou úpravou předchozího kódu na

delka [] = 0
delka (_:xs) = 1 + delka xs

můžeme demonstrovat další vzor nazvaný anonymní proměnná. Tu představuje znak _ (podtržítko). Anonymní proměnná se používá v případech, kdy nás daný parametr obsahově nezajímá, ale je důležité, aby existoval. Někdy je užitečné použít tvz. pojmenování části vzoru. Příkladem může být následující funkce, která duplikuje první prvek seznamu.

dup y@(x:xs) = x:y

Vzorem může být také uspořádaná n-tice

soucet (a,b) = a + b

Vzory typu n+k jsou často zatracované a doporučuje se dále je už nepoužívat. Přesto jsou, alespoň prozatím, součástí jazyka, a tak zde má místo i tento příklad

faktorial  0 = 1
faktorial (n+1) = (n+1) * faktorial n

Při výpočtu je občas zapotřebí pro různá data provádět odlišné výpočty. Toho lze v Haskellu dosáhnout několika způsoby.

strážené rovnice

jsou rovnice deklarující funkci, rozšířené o tzv. strážnou podmínku – logický výraz omezující použití dané rovnice na případy, kdy nabývá hodnoty True. Jako ukázku jsem dvakrát uvedl funkci na výpočet faktoriálu. Ta ale měla jeden nedostatek – pokud by někdo zadal jako parametr záporné číslo, rekurze by sama nikdy neskončila (dokud by nedošlo k přetečení zásobníku). Tato chyba je opravena v následující deklaraci

faktorial n | n < 0 = error "Nelze urcit faktorial zaporneho cisla"
        | n == 0 = 1
        | otherwise = n * faktorial (n - 1)

Funkce error vracená jako výsledek při chybném parametru způsobí ukončení výpočtu a vypsání hlášky zadané jako její parametr. Zvláštností funkce error je to, že je typově kompatibilní s jakýmkoliv typem (jinak by překladač hlásil syntaktickou chybu). Identifikátor otherwise použitý jako třetí podmínka je jenom synonymem pro True, ale jeho použití je v tomto kontextu obvyklejší, než je tomu u True, hlavně kvůli vlastnímu významu slova (otherwise = jinak).

if

je prostředek známý i z imperativních jazyků. Domnívám se, že následující příklad nepotřebuje další komentář.

faktorial 0 = 1
faktorial n = if n < 0 then error "Nelze urcit faktorial zaporneho cisla"
          else n * faktorial (n - 1)

case

Oproti svým imperativním protějškům má case v Haskellu větší možnosti. Výraz mezi klíčovými slovy case a of může mít libovolný typ. Jako návěští pro jednotlivé případy lze použít dříve zmiňované vzory (konstanty, proměnné, seznamy, …)

faktorial 0 = 1
faktorial n = case n < 0 of
         True  -> error "Nelze urcit faktorial zaporneho cisla"
         False -> n * faktorial (n-1)

Na uvedeném příkladu je vidět, že if lze vlastně úplně nahradit pomocí case.

Pozorný čtenář jistě zaregistroval, že se v příkladech několikrát objevilo klíčové slovo where (neberme teď v úvahu where v hlavičce modulu). To se používá, chceme-li ve funkci deklarovat další (pomocné) funkce. Identifikátor takové funkce je platný pouze v nadřazené deklaraci a pro zbytek rovnic je neznámý. Deklarace pomocí where se často využívá u strážených rovnic. Jako příklad tentokrát poslouží funkce pro výpočet kořenů 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

V druhé rovnici jsem použil něco, čemu se říká let expression (nevím, zda existuje nějaký český ekvivalent a překlad „výraz let“ mi připadá divný …) Je obdobou where s tím rozdílem, že let je platný výraz, kdežto where je syntaktická konstrukce jazyka (tj. nemůže být použit jen sám o sobě). Druhým rozdílem je, že symboly deklarované pomocí let mají platnost od rezervovaného slova in do konce rovnice. Naproti tomu platnost symbolů deklarovaných za where zůstává pro všechny větve strážené rovnice.

Pokud toho ještě nemáte dost, vězte, že v příštím dílu se zaměříme na práci se seznamy, na vstupně/výstupní operace, třídy a možná dojde i na to, jak můžete formálním důkazem verifikovat program v Haskellu.