Haskell - typy a základní funkce

Po cvičeních s Prologem se dnes přesuneme k dalšímu neprocedurálnímu jazyku. Tentokrát nepůjde o logické programování, ale o programování funkcionální, které si ukážeme na jazyce Haskell. Základní vlastností funkcionálního programování je, že celý program se skládá z funkcí, jejichž výstupy závisí pouze na jejich vstupech (a ne třeba na stavu programu). Neexistují žádné globální proměnné. Celý program je nakonec jedna (mnohokrát složená a případně i hodně složitá) funkce.

Další vlastnosti funkcionálního programování je, že se v něm často pracuje s funkcemi, které jako parametry mají další funkce.

Podívejme se napřed, jak v Haskellu pracovat se základními datovými typy. Haskell defaultně počítá s dlouhými čísly (Integer), takže když na vstupu interpretu napíšete 5^87, on vám bez problémů odpoví 6462348535570528709932880406796584793482907116413116455078125.

Haskell samozřejmě zná i další obvyklé datové typy: Int (pro běžná, “krátká” čísla), Bool, Float, Double, Char, … (všechny s obvyklým významem). Haskell podporuje i uspořádané n-tice, psané v kulatých závorkách. (Int, Double) je dvojice, kde první prvek je Int a druhý Double. Konečně, Haskell také zná seznamy, které jste si jistě moc oblíbili v Prologu :). Seznam prvků typu Integer se zapíše jako [Integer], syntaxe pro rozdělení seznamu na hlavu a tělo je x:xs. Řetězce jsou v Haskellu seznamy znaků [Char].

Zkusme si teď v Haskellu napsat první jednoduchou funkci, například výpočet faktoriálu, ukážeme si na ní základní syntaxi a také to, jak se k funkcím píšou typy.

fact :: Integer -> Integer  -- typ
fact n  | n < 1     = error "To teda ne"    -- pro zaporna cisla neni definovan
        | n == 1    = 1                     -- faktorial 0 je 1
        | otherwise = n * fact (n-1)        -- faktorial n je n*faktorial n-1

První řádka explicitně říká, jakého typu naše funkce fact je. Že zobrazuje Integer na Integer. V interpretu si můžeme její typ nechat vypsat pomoci :t fact a dostaneme odpověď, která přesně odpovídá první řádce. Typy není nutné uvádět, Haskell si je umí odvodit sám, ale je to vhodné, pomáhá to při ladění a zároveň to pomůže komukoliv, kdo čte váš kód. Zároveň, zrovna v případě faktoriálu, si Haskell odvodí typ moc obecně a nechal by vás ho počítat i pro necelá čísla (ale stejně byste minuli ten konec rekurze a pak by vypsal tu chybovou hlášku).

Syntaxi s | a = se říká stráž. Mezi | a = můžete napsat libovolnou podmínku, je to podobné tomu, když v matematice definujete funkci po částech.

Zkusme si teď napsat několik základních funkci pro práci se seznamy (všechny z nich jsou v Haskellu definované, ale nám se pro procvičení hodí). Pro přehlednost (a zabránění kolizím s existujícími jmény) budeme před jejich standardní názvy psát my_.

První užitečnou funkcí je funkce map, která jako argument vezme funkci a seznam a aplikuje ji na každý prvek seznamu, vrátí seznam s výsledky.

my_map :: (a -> b) -> [a] -> [b]
my_map f []     = []
my_map f (x:xs) = (f x):(my_map f xs)

Můžeme ji hned vyzkoušet v interpretu.

>my_map (*2) [1,2,3,4]
[2,4,6,8]

Všimněte si, že funkce může být definována i na více řádkách. Haskell používá expression matching a použije definici, která je jako první a odpovídá zvolenému tvaru vstupu. V tomto případě se pro prázdný seznam zavolá první řádek a kdykoliv jindy řádek druhý.

Hodí se i pár vysvětlení k typu. Operátor (*) je v Haskellu typu (zjednodušeně) Int -> Int -> Int, tzn. že na vstupu očekává dvě čísla a vrací číslo. Tím, že napíšeme (*2) jsme jedno číslo dodali, a tím dostáváme funkci typu Int -> Int (tento zápis funguje pro všechny operátory a binární funkce pokud je zapíšeme v inline zápisu - ukážeme si později). Samotný zápis typu funkce my_map říká, že jako první argument dostává funkci typu (a -> b), potom seznam prvků typu a a vrací seznam prvků typu b. Všimněte si, že obecně napsané typy se píšou malým písmenem.

A ještě jedna poznámka, pokud píšete 2*3, stačí psát *, pokud ale chcete použít operátor * jako parametr funkce, musíte psát (*). Interpretu můžete tedy například napsat i (*) 2 3 a on vám odpoví 6 (* 2 3 ale nefunguje). Stejně pravidlo samozřejmě platí i pro ostatní operátory.

Užitečná funkce je i take n xs, ta vezme ze seznamu xs prvních n prvků a vrátí je.

my_take :: Int -> [a] -> [a]
my_take 0 _                     = []
my_take _ []                    = []
my_take n (x:xs) | n < 0        = error "n must be > 0"
                 | otherwise    = x:(my_take (n-1) xs) 

Všimněte si, že opět můžeme použít _ jako název proměnné, která nás nezajímá.

Vyzkoušejme si naši funkci:

> my_take 3 [1,2,3,4,5]
[1,2,3]

Haskell dovoluje definovat seznamy i o něco obecněji. Můžete definovat rozsah například jako [3..10] je seznam všech čísel od 3 do 10 (včetně). Dokonce horní mez seznamu může chybět, potom se jedna o nekonečný seznam. [1..] tedy definuje seznam [1,2,3,4,5,6,7,...]. Zajímavé je, že i s takovými seznamy jde v Haskellu bez problémů pracovat.

> my_take 5 [1..]
[1,2,3,4,5]

V tomhle případě se projevuje jedna z vlastnosti Haskellu. A tou je líné vyhodnocování, tzn. že Haskell nevyhodnocuje výrazy, dokud nemusí. A přesně to se stalo s naším nekonečným seznamem, nikdy jsme nepotřebovali prvky od 6 dál, takže Haskell na ně nikdy ani nesáhl. Dokonce můžeme zkombinovat naše dvě funkce a napsat funkci, která nám vrátí seznam prvních n mocnin 2. Opět, další mocniny se nepočítají, když nejsou potřeba.

mocninyDvojky :: Int -> [Integer]
mocninyDvojky n = my_take n (my_map (2^) [1..])

Dokonce konec této funkce definuje seznam mocnin dvojek, kdyby se nám třeba někdy hodil.

seznamMocnin = my_map (2^) [1..]

Užitečná je také varianta funkce take, a sice takeWhile, která místo počtu má funkci, která vrací Bool. takeWhile potom bere prvky ze seznamu dokud tato funkce vrací True.

my_takeWhile :: (a -> Bool)->[a]->[a]
my_takeWhile _ []                 = []
my_takeWhile f (x:xs) | f x       = x:(takeWhile f xs)
                      | otherwise = []

Další užitečnou standardní funkci je zip. Ta vytváří ze dvou seznamů jeden seznam dvojic. Délka výsledného seznamu odpovídá délce kratšího z obou seznamů.

my_zip :: [a] -> [b] -> [(a,b)] 
my_zip [] _          = []
my_zip _ []          = []
my_zip (x:xs) (y:ys) = (x,y):my_zip xs ys

> my_zip [1..5] seznamMocnin
[(1,2),(2,4),(3,8),(4,16),(5,32),(6,64),(7,128),(8,256),(9,512),(10,1024)]

zipWith je také užitečná, vezme dva seznamy, aplikuje na ně binární funkci a výsledky uloží do výsledného seznamu.

my_zipWith :: (a->b->c) -> [a] -> [b] -> [c]
my_zipWith _ _ []          = []
my_zipWith _ [] _          = []
my_zipWith f (x:xs) (y:ys) = (f x y):my_zipWith f xs ys

Pomoci ní se dá třeba napsat sčítání dvou seznamů po složkách

sectiSeznamy x y = my_zipWith (+) x y

Ukažme ještě jednu standardní funkci, foldl aplikuje operaci na seznam tak, že ji vloží mezi všechny prvky seznamu, ještě je možné specifikovat počáteční hodnotu. Např. foldl (+) 7 [1,2,3,4] spočítá (((7 + 1) + 2) + 3) + 4. Její varianta foldr dělá totéž, ale prvky seznamu bere odzadu (tj. počítá 1 + (2 + (3 + (4 + 7)))).

my_foldl :: (a->b->a)->a->[b]->a
my_foldl _ init []      = init
my_foldl f init (x:xs)  = my_foldl f (f init x) xs

Ještě existuje varianta foldl1, která jako počáteční hodnotu vezme první prvek seznamu.

my_foldl1 :: (a->a->a)->[a]->a
my_foldl1 f (x:xs) = my_foldl f x xs

Teď můžeme třeba naprogramovat skalární součin dvou seznamu.

skalarniSoucin :: Num a => [a] -> [a] -> a
skalarniSoucin x y = my_foldl1 (+) (my_zipWith (*) x y)

Specifikace Num a v typu funkce říká, že a musí být nějaký numerický typ. Jedna se o tzv. typovou třídu, jen si dejte pozor na to, že typová třída není sama o sobě typ.

Zkusme ještě něco trochu složitějšího (alespoň ve smyslu typu výsledné funkce). Funkce filter má jako jeden z parametrů funkci, která vrací Bool, a jako druhý parametr seznam. Vybere ze seznamu prvky, pro které je dána funkce True.

my_filter :: (a->Bool)->[a]->[a]
my_filter _ []              = []
my_filter f (x:xs)  | f x       = x:(filter f xs)
                    | otherwise = filter f xs

Opět máme k dispozici pár jednoduchých funkcí, které Bool vracejí, např. porovnání (<,>,<=,>=, ==, /=). Když jim opět jeden parametr “obsadíme”, dostáváme funkci, která má jeden parametr a vrací Bool. Můžeme tedy např. ze seznamu čísel vyfiltrovat ta, která jsou menší než 5.

> my_filter (<5) [1,2,3,4,5,43,2,3,4]
[1,2,3,4,2,3,4]

Pomoci této funkce ale můžeme udělat mnohem zajímavější věci, např. napsat quicksort.

qsort :: Ord a => [a] -> [a]
qsort []        = []
qsort (x:xs)    = (qsort mensi)++[x]++(qsort vetsi)
                where 
                    mensi = my_filter (<x) xs
                    vetsi = my_filter (>=x) xs

Konstrukce where dovoluje definovat lokálně funkce přímo uvnitř jiné funkce, může občas trochu zpřehlednit kód (kdybychom ale místo mensi/vetsi napsali přímo tu jejich definici, dostali bychom stejný výsledek). Operator (++) spojuje dva seznamy (v čase lineárním v délce prvního z nich).

Haskell používá (relativně volnou) 2D syntaxi, tj. záleží na odsazení. Podstatné ale je jen za klíčovými slovy where, let, do a of. Pravidlo přitom je takové, že hlubší odsazení za těmito slovy vytváří nový blok, stejné odsazení pokračuje v existujícím bloku a menší odsazení blok ukončuje. Pokud by někoho zajímaly detaily, dají se najít v dokumentaci. Místo odsazení lze používat i složené závorky a středníky, v Haskellu to ale není moc obvyklé.