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

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

 

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

Google       Google       15. 9. 2006       13 345×

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 Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Reklama
Reklama
Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Obrázek ke článku Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

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 © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý