Funkcionální programování - Datové struktury
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama

Funkcionální programování - Datové strukturyFunkcionální programování - Datové struktury

 

Funkcionální programování - Datové struktury

Google       Google       15. 9. 2006       13 730×

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.

Reklama
Reklama

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
protože konstruktor uspořádaných dvojic (,) je také binárním operátorem. A dokonce, jak uvidíme později, lze definici funkce zip zkrátit ještě více:

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.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

Hlasování bylo ukončeno    
0 hlasů
Google
Autor je profesorem na Fakultě informatiky Masarykovy univerzity v Brně.

Nové články

Obrázek ke článku Blockchain & Bitcoin konference

Blockchain & Bitcoin konference

V pátek 19. 5. 2017 se v pražském konferenčním centru Andel’s konala Blockchain & Bitcoin konference. Řada odborníků a podnikatelů v oboru blockchainu a kryptoměn představila možnosti budoucího směřování tohoto oboru. Speakeři většinou rusky mluvící provenience prezentovali řešení svých firem založená na technologii blockchainu.

Reklama
Reklama
Obrázek ke článku Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Bezpečnostní tým Cisco Talos odhalil celkem 4 kampaně dosud neobjeveného malwaru, který dostal jméno KONNI. Ten se dokázal úspěšně maskovat od roku 2014. Zpočátku se malware zaměřoval pouze na krádeže citlivých dat. Za 3 roky se ale několikrát vyvinul, přičemž jeho současná verze umožňuje útočníkovi z infikovaného počítače nejenom krást data, ale i mapovat stisky na klávesnici, pořizovat screenshoty obrazovky či v zařízení spustit libovolný kód. Pro odvedení pozornosti oběti zasílali útočníci v příloze také obrázek, zprávu a výhružkách severokorejského režimu či kontakty na členy mezinárodních organizací.

Obrázek ke článku Pouze jedna z deseti lokálních firem ví o pokutách plynoucích z GDPR

Pouze jedna z deseti lokálních firem ví o pokutách plynoucích z GDPR

Trend Micro, celosvětový lídr v oblasti bezpečnostních řešení a VMware, přední světový dodavatel cloudové infrastruktury a řešení pro podnikovou mobilitu, oznámily výsledky výzkumu mezi českými a slovenskými manažery zodpovědnými za ochranu osobních údajů, který zjišťoval, jak jsou připraveni na nové nařízení o ochraně osobních údajů (GDPR). Většina firem v České republice a na Slovensku nad 100 zaměstnanců je již s novým nařízením GDPR obeznámena. Výzkum provedený ve spolupráci s agenturou Ipsos ukázal, že téměř 8 firem z 10 o nařízení ví, přičemž jeho znalost je o něco vyšší na Slovensku (89 %) než v České republice (69 %).

Obrázek ke článku Vyděračský software Locky se vrací, tváří se jako potvrzení platby, odhalil tým Cisco Talos

Vyděračský software Locky se vrací, tváří se jako potvrzení platby, odhalil tým Cisco Talos

Jeden z nejznámějších ransomwarů, Locky, se vrací. Po většinu roku 2016 patřil mezi nejrozšířenější vyděračské softwary. Ke svému šíření využíval emailové kampaně s infikovanými přílohami. Ransomware Locky byl rozesílán prostřednictvím botnetu (internetový robot zasílající spamy) Necurs. Jeho aktivita na konci roku 2016 téměř upadla a spolu s ní i šíření ransomwaru Locky. Před několika týdny se Necurs opět probudil a začal posílat spamy nabízející výhodný nákup akcií. Dne 21. dubna zaznamenal bezpečnostní tým Cisco Talos první velkou kampaň ransomwaru Locky prostřednictvím botnetu Necurs za posledních několik měsíců.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý