Po letní přestávce pokračujeme v seriálu o funkcionálním programování. Abychom mohli používat i méně triviální data než jen čísla nebo znaky, zavedeme si uspořádané n-tice a seznamy.

Datové struktury jsou hodnoty datových typů. Příklady datových struktur mohou být záznam, pole, konečná posloupnost… Nejpoužívanější a nejjednodušší datové struktury v Haskellu jsou uspořádané n-tice a seznamy.

Uspořádané n-tice

Jsou-li M a N výrazy, pak výraz (M,N) označuje uspořádanou dvojici výrazů M, N. Podobně (M,N,P) je uspořádaná trojice výrazů M, N, P atd. V Haskellu existuje dokonce speciální hodnota (), takzvaná nultice.

Složky uspořádaných dvojic se zpřístupní pomocí funkcí fst, snd.

fst       ::  (a,b) -> a
fst (x,y)  =  x

snd       ::  (a,b) -> b
snd (x,y)  =  y

V těchto definicích jsou použity uspořádané dvojice (x,y) jako vzor. To znamená, že funkce fst, snd jsou definovány na uspořádaných dvojicích, jejichž složky mohou být libovolné (vzor x resp. y je proměnná, tj. vyhovuje všem výrazům).

Složky uspořádané n-tice mohou být různého typu. Například v uspořádané trojici (2.7,True,'+') má první složka typ Float, druhá složka má typ Bool a třetí složka má typ Char. Také celá uspořádaná trojice má typ – zapisujeme ho (Float,Bool,Char) a je vlastně kartézským součinem typů Float, Bool, Char. Složkami uspořádaných n-tic mohou být libovolné hodnoty, například jiné datové struktury nebo funkce:

('e',True)               ::  (Char,Bool)
(False,('%',0),3.14159)  ::  (Bool,(Char,Int),Float)
(isDigit,not)            ::  (Char->Bool, Bool->Bool)

Binární operátor, který vytváří uspořádanou dvojici, se jmenuje konstruktor uspořádané dvojice a značí se (,). Aplikován na výrazy M, N tvoří dvojici (M,N), tj. (,) M N = (M,N). Druhý způsob zápisu (M,N) je však obvyklejší než prefixový. Podobně máme ternární konstruktor (,,) uspořádaných trojic atd.

(,)  :: a -> b -> (a,b)
(,,) :: a -> b -> c -> (a,b,c)

Pomocí uspořádaných dvojic si můžeme třeba reprezentovat zlomky – první složka bude čitatel a druhá jmenovatel zlomku. Dále si můžeme zavést operace pro počítání se zlomky třeba operaci pro sčítání takto reprezentovaných zlomků pojmenujeme (+/):

(+/)  ::  (Int,Int) -> (Int,Int) -> (Int,Int)
(a,b) +/ (c,d)  =  (e/g,f/g) where e = a*d+b*c
                                   f = b*d
                                   g = gcd e f

(Funkce gcd počítá největšího společného dělitele svých dvou argumentů. Krácením zlomku největším společným dělitelem se zlomek převede do základního tvaru.)

Seznamy

Uspořádané n-tice mají pevný počet složek, které mohou být různého typu. Naproti tomu seznam je posloupnost, v níž mají všechny prvky stejný typ. Seznamy zapisujeme výčtem prvků oddělených čárkami a uzavřených do hranatých závorek:

[True, False, False]  :: [Bool]              -- tříprvkový seznam pravdivostních hodnot
[1,2,3,4]             :: Num a => [a]        -- čtyřprvkový seznam čísel
[(&&), (||)]          :: [Bool->Bool->Bool]  -- dvouprvkový seznam logických operací
[('*',True)]          :: [(Char,Bool)]       -- jednoprvkový seznam dvojic
[]                    :: [a]                 -- prázdný seznam

Takový zápis (výčtem prvků v hranatých závorkách) je vlastně jen syntaktická zkratka pro to, co se dá zapsat pomocí dvou základních operací – takzvaných seznamových konstruktorů. První z nich je konstanta (tedy nulární konstruktor) [], která označuje prázdný seznam. Druhou operací je binární konstruktor (:), který přidává prvek na začátek seznamu: je-li s seznam prvků a x je hodnota téhož typu jako mají prvky seznamu s, pak x:s je seznam, který vznikne ze seznamu s přidáním prvku x na jeho začátek.

Výše napsané seznamy lze proto ekvivalentně zapsat takto:

True : (False : (False : []))
1 : (2 : (3 : (4 : [])))
(&&) : ((||) : [])
('*',True) : []
[]

Dohodneme se, že operátor (:) sdružuje operandy zprava. To znamená, že závorky můžeme vynechat a zápis trochu zpřehlednit:

True : False : False : []
1 : 2 : 3 : 4 : []
(&&) : (||) : []
('*',True) : []
[]

Navíc, speciálně pro seznamy znaků, tj. seznamy typu [Char], můžeme použít notace, v níž znaky zapíšeme bez oddělovačů za sebe a seznam uzavřeme do uvozovek ("). Všechny tři následující zápisy označují stejný (tříznakový) řetězec.

'a':'b':'c':[]
['a','b','c']
"abc"

Znakové řetězce v Haskellu jsou tedy seznamy znaků. Pro zpracování řetězců se tak nemusí zavádět žádné zvláštní řetězcové operace, použijí se operace nad seznamy.

Všechny prvky seznamu musí mít stejný typ. Typ seznamu se zapisuje opět pomocí hranatých závorek. Například seznam funkcí, z nichž každá má typ Char–>Bool, má sám typ [Char–>Bool].

Když zavádíme nové funkce, které pracují se seznamy, můžeme zase použít definice podle vzoru. Například standardní funkce null, která testuje, zda je její argument (seznam), prázdný, je definována takto:

null       ::  [a] -> Bool
null []     =  True
null (x:s)  =  False

Prázdnému seznamu odpovídá jen první vzor [], neprázdnému seznamu zase odpovídá jen druhý vzor, (x:s).

Poznámka:
Protože proměnné z druhého vzoru jsme na pravé straně definice nepoužili, nemuseli jsme je vůbec pojmenovávat. „Bezejmennou“ proměnnou značíme symbolem _ (podtržítko). Její význam je „cokoliv“. Vyskytne-li se ve vzoru vícekrát, může každý její výskyt odpovídat jinému výrazu. Druhý vzor jsme tedy mohli zapsat (_:_).

Další užitečná funkce, length, počítá délku (počet prvků) seznamu:

length       ::  [a] -> Int
length []     =  0
length (_:s)  =  1 + length s

Nepokrývají-li vzory v definici všechny možné tvary argumentu, zůstává funkce nedefinovaná pro ty argumenty, které neodpovídají žádnému vzoru v její definici. Například funkce head vrací první prvek neprázdného seznamu, funkce tail zase vrací tzv. zbytek seznamu, tj. seznam bez prvního prvku.

head       ::  [a] -> a
head (x:_)  =  x

tail       ::  [a] -> [a]
tail (_:s)  =  s

Hodnoty výrazů head [] a tail [] nejsou definovány a způsobí chybu při výpočtu.

Další funkce pro práci se seznamy

Binární operátor (!!) vybírá ze seznamu prvek daného indexu, přičemž prvky jsou indexovány od nuly. Například [3,1,7]!!2 →^* 7. Funkce (!!) je definována jen pro nezáporný druhý argument.

(!!)       ::  [a] -> Int -> a
(x:_) !! 0  =  x
(_:s) !! k  =  s !! (k-1)

Velmi důležitou funkcí je funkce map. Jejím prvním parametrem je funkce, druhým je seznam. Funkce map umožňuje aplikovat funkci f na všechny prvky seznamu. Například hodnotou výrazu map square [1,5,11] bude [1,25,121] (funkce square umocňuje číslo na druhou). Výsledkem aplikace map toUpper "abc" je řetězec (tj. seznam znaků) "ABC", protože toUpper „zvětšuje“ jedno písmeno. A výraz map even [2,3,5] se vyhodnotí na [True,False,False], protože even testuje sudost čísla.

Definice funkce map vypadá takto:

map         ::  (a->b) -> [a] -> [b]
map _ []     =  []
map f (x:s)  =  f x : map f s

Funkce map je příkladem funkce, jejímž parametrem je opět funkce. Takové funkce se ve funkcionálním programování vyskytují často a někdy se jim říká funkce vyššího řádu. Další podobnou funkcí je filter. Funkce filter má zase dva parametry. Prvním z nich je funkce vracející pravdivostní hodnotu (taková funkce se nazývá predikát). Druhým parametrem funkce filter je seznam. Výsledkem aplikace filter p s je seznam vzniklý ze seznamu s vybráním jen těch prvků x, které splňují podmínku p x. Ostatní prvky filter „odfiltruje“. Například filter odd [1,1,2,5,12,35] má hodnotu [1,1,5,35] a výsledkem aplikace filter isDigit "-2.99e8" bude řetězec "2998". Definice funkce filter je opět rekursivní:

filter         ::  (a->Bool) -> [a] -> [a]
filter _ []     =  []
filter p (x:s)  =  if  p x  then  x:t  else t
                   where t = filter p s

Další dvě často používané funkce jsou take a drop.

Funkce take vrátí prvních n (první parametr) prvků seznamu (druhý parametr). Má-li seznam méně než n prvků, vrátí ho funkce celý.

Podobně funkce drop vrátí zbytek seznamu po odstranění prvých n prvků. Je-li seznam „příliš krátký“, bude výsledkem prázdný seznam.

take         ::  Int -> [a] -> [a]
take 0 _      =  []
take _ []     =  []
take n (x:s)  =  x : take (n-1) s

drop         ::  Int -> [a] -> [a]
drop 0 s      =  s
drop _ []     =  []
drop n (_:s)  =  drop (n-1) s

Podobnou roli jako funkce map pro unární funkce (operace) hraje funkce zipWith pro binární operace.

zipWith                :: (a->b->c) -> [a] -> [b] -> [c]
zipWith op (x:s) (y:t)  =  op x y : zipWith op s t
zipWith _  _     _      =  []

Funkce aplikuje operaci op na odpovídající si prvky obou seznamů a z výsledků těchto aplikací vytvoří seznam. Například výraz zipWith (*) [1,2,3] [1,4,9] bude mít hodnotu rovnou seznamu [1,8,27].

Poslední řádek definice funkce zipWith „odchytí“ případy, kdy je první nebo druhý seznam prázdný. Nemusejí být prázdné oba současně, to znamená, že funkci zipWith lze aplikovat i na dva nestejně dlouhé seznamy. Délka výsledného seznamu bude rovna délce kratšího z nich. Například zipWith (+) [1,2,3,4,5] [0,10,20]  →*  [1,12,23].

Funkce zip vytváří ze dvou seznamů seznam dvojic, například zip "abc" [1,2,3]  →*  [('a',1),('b',2),('c',3)]. Lze ji definovat takto:

zip             ::  [a] -> [b] -> [(a,b)]
zip (x:s) (y:t)  =  (x,y) : zip s t
zip _     _      =  []

Ale když už máme definovanou funkci zipWith, můžeme pomocí ní definovat funkci zip jednodušeji a kratčeji takto

zip s t  =  zipWith (,) s t

zip  =  zipWith (,)

To proto, že aplikujeme-li funkci zipWith jen na jeden argument, je hodnota takové aplikace rovna binární funkci, která očekává zbývající dva argumenty. O takzvaných částečných aplikacích si řekneme více v kapitole o funkcích vyššího řádu.

Seznamy jsou ve funkcionálním programování rozšířenou datovou strukturou. Pomocí nich se často definují složitější datové struktury. Proto na seznamech existuje řada funkcí. Některé jsme si ukázali, s některými se ještě setkáme. Definice všech standardních seznamových funkcí lze najít v knihovních modulech List.hs a Prelude.hs kompilátoru nebo interpretu Haskellu.

Shrnutí

• Mezi základní datové struktury patří uspořádané n-tice a seznamy.
• Složky n-tice mohou mít různý typ, všechny prvky seznamu musí být stejného typu.
• n-tice mají jeden konstruktor, seznamy se tvoří pomocí dvou konstruktorů.
• Funkce, pracující s n-ticemi a se seznamy s výhodou, definujeme podle vzorů.
• V Haskellu je řada užitečných předdefinovaných fukcí pracujících s uspořádanými n-ticemi a se seznamy.