pp-cb

This is an old revision of the document!

---

====== Tipuri de date abstracte ====== Responsabili laborator: * [[mihai.dumitru@cti.pub.ro|Dumitru Mihai-Valentin]] * [[calin.cruceru@cti.pub.ro|Călin Cruceru]] Scopul laboratorului: * Recapitularea conceptului de TDA * Definirea de TDA-uri în Haskell * Familiarizarea cu conceptul de TDA-uri polimorfice * Introducerea tipului de date ''Maybe'' ===== Tipuri de date abstracte (TDA) ===== **Tipurile de date abstracte** sunt modele pentru a defini tipuri de date în funcție de comportamentul acestora (valori posibile, axiome, operații), contrastând cu //structurile de date//, definite din punct de vedere al implementării. Un TDA familiar este **list**. În primul laborator am lucrat cu liste de întregi, definind o listă ca fiind fie lista vidă, fie un întreg introdus în altă listă. Deasemena am definit o mulțime de operații posibile pe listă: ''isEmpty'', ''head'', ''tail'', ''add'', ''get'', ''ins'', ''show''.\\ Pentru a lucra cu liste într-un limbaj ca C, am scris două //implementări// distincte, și anume ''LinkedList'' și ''ArrayList''. Ambele implementări respectă specificațiile din primul paragraf. <note important> Unii autori includ în descrierea TDA-urilor și complexități. Din acest punct de vedere, implementările ''LinkedList'' și ''ArrayList'' diferă. </note> ==== Constructori ==== Valorile posibile ale unui TDA sunt date de constructorii acestuia.\\ Să considerăm un tip simplu de date: ''Bool'', care poate avea două valori: ''False'' și ''True''.\\ Sintaxa Haskell pentru a defini acest tip de date este următoarea: <code haskell> data Bool = False | True </code> <note important> Atât numele tipului de date cât și numele constructorilor trebuie scris cu literă mare. </note> ''False'' și ''True'' nu sunt parametrizate și pot fi privite ca valori. Se mai numesc și //constructori nulari//.\\ Să considerăm un alt TDA care descrie un arbore binar cu valori întregi. Arborele poate fi gol sau un nod cu doi copii. <code haskell> data Tree = Nil | Node Int Tree Tree </code> ''Node'' este un constructor care primește un argument de tipul ''Int'' și două argumente de tip ''Tree'', pentru a creea o valoare de tip ''Tree''. Putem să ne gândim la el ca la o funcție: <code> Prelude> :t Node Node :: Int -> Tree -> Tree -> Tree </code> Constructorii sunt foarte importanți în //pattern matching//. Ca exemplu, vom scrie o funcție care însumează toate valorile dintr-un arbore: <code haskell> treeSum :: Tree -> Int treeSum Nil = 0 treeSum (Node v l r) = v + (treeSum l) + (treeSum r) </code> Observăm prezența a două pattern-uri: unul pentru arborele vid, celălalt pentru un nod, într-un fel foarte asemănător cu modul în care lucram cu liste, făcând pattern matching pe ''[]'' și ''(x:xs)''. <note tip> Observați că ghci nu știe cum să afișeze arborele nostru: <code> Prelude> Node 1 Nil Nil <interactive>:38:1: No instance for (Show Tree) arising from a use of `print' In a stmt of an interactive GHCi command: print it </code> Pentru a vă fi mai ușor să vă verificați, puteți obține o reprezentare a tipurilor definite de voi astfel: <code haskell> data Tree = Nil | Node Int Tree Tree deriving (Show) </code> Pe scurt, acest lucru înrolează TDA-ul vostru în clasa ''Show'', oferind o implementare implicită a funcției ''show'' (apelată de ghci). Mai multe detalii în laboratorul următor. <code> Prelude> Node 1 Nil Nil Node 1 Nil Nil </code> </note> ==== Exerciții TDA ==== 1. Implementați TDA-ul pentru propria voastră listă care poate conține doar numere întregi. 2. Scrieți o funcție care convertește valori ale TDA-ului vostru în liste din Haskell. <note tip> Dacă tipul vostru de listă se numește ''List'', atunci tipul funcției va fi: <code haskell> convertList :: List -> [Int] </code> </note> 3. Implementați TDA-ul "optiune", care codifică valori opționale de tip Integer (e.g. fie ''None'', fie o valoare întreagă). <note> Pentru a ilustra importanța acestui TDA, considerăm următoare situație: vrem să implementăm o funcție care returnează valoarea păstrată în rădăcina unui arbore dat. <code haskell> -- presupunem ca Optiune are constructorii "None" si "Value Int" rootValue :: Tree -> Optiune rootValue Nil = None rootValue (Node v _ _) = Value v </code> Un arbore vid nu are nicio valoare în rădăcină, iar pentru orice alt arbore, valoarea este cea din nodul primit. Fără TDA-ul ''Optiune'' nu am putea avea pattern-uri exhaustive, fără să folosim convenții de valori speciale (e.g. 0, MAX_INT) pentru valoarea din rădăcină. Putem scrie o funcție care ia o ''Optiune'' și returnează un șir pentru printare. Combinăm apoi cele două funcții: <code haskell> pretty :: Optiune -> String pretty None = "No value" pretty (Value v) = "Value is " ++ show v printRootValue :: Tree -> String printRootValue = pretty . rootValue </code> Încărcăm modulele în ghci și voilà: <code> *Main> printRootValue (Node 1 (Node 1 Nil (Node 2 Nil Nil)) (Node 3 (Node 4 (Node 5 Nil Nil) Nil) (Node 6 Nil Nil))) "Value is 1" *Main> printRootValue Nil "No value" </code> </note> <note tip> Evident, Haskell pune la dispoziție un tip de date similar, numit ''Maybe''. Spre deosebire de tipul nostru, ''Maybe'' funcționează cu orice tip de date, nu doar întregi, fiind un tip //polimorfic// (mai multe detalii [[laboratoare:04-tipuri-de-date-abstracte#tda-uri_polimorfice|aici]]). <code haskell> data Maybe a = Nothing | Just a </code> </note> ==== Înregistrări ==== Vrem să definim un TDA pentru a descrie un student, folosind următoarele câmpuri: nume, prenume, an de studiu, medie. <code haskell> -- tipul de date si constructorul au acelasi nume, ceea ce este ok -- pentru ca reprezinta concepte diferite. data Student = Student String String Int Float </code> Observăm că semnficația câmpurilor nu este evidentă din definiție. Vrem să extragem valori dintr-un Student; definim funcțiile: <code haskell> nume :: Student -> String nume (Student n _ _ _) = n prenume :: Student -> String prenume (Student _ p _ _) = p an :: Student -> Int an (Student _ _ a _) = a medie :: Student -> Float medie (Student _ _ _ m) = m </code> Pentru a face descrierea tipului de date mai clară și a evita să scriem manual acele funcții, putem folosi sintaxa: <code haskell> data Student = Student { nume :: String , prenume :: String , an :: Int , medie :: Float } </code> 4. a) Scrieți un TDA care codifică un tuplu (înregistrare) format din următoarele câmpuri: * Nume (codificat ca String) * Vârstă (codificat ca Integer) * Prieteni (codificat ca o lista de String-uri) * Notă PP (codificat ca Integer). Acest câmp este opțional! b) Scrieți o funcție care primește o listă de înregistrări și le întoarce pe acelea pentru care vârsta este mai mare ca 20. c) Scrieți o funcție care primește o listă de înregistrări și le întoarce pe acelea care conțin cel puțin un prieten cu numele "Matei". d) Scrieți o funcție care primește o listă de înregistrări și le întoarce pe acelea care conțin câmpul "Notă PP". e) Scrieți o funcție care primește o listă de nume, o listă de vârste, o listă ce conține liste de prieteni, și întoarce o listă de înregistrări corespunzătoare. ===== TDA-uri polimorfice ===== Până acum, am definit TDA-uri care lucrează doar cu întregi. Dorim să scăpăm de această limitare și să definim TDA-uri care pot lucra cu orice alt tip de date. De exemplu, are sens să considerăm capul unei liste care conține elemente de tip ''a'', ca fiind un element de tip ''a'', indiferent de cum arată acest tip.\\ Într-adevăr, aceasta este definiția funcției ''head'' existentă în Haskell: <code> Prelude> :t head head :: [a] -> a </code> ''a'' se numește **variabilă de tip** și poate să reprezinte orice tip de date (evident, cu condiția ca toate ''a''-urile care apar să se refere la același tip). <note> Să ne uităm la tipul altei funcții cunoscute: <code> Prelude> :t map map :: (a -> b) -> [a] -> [b] </code> ''map'' primește ca argument o funcție - care primește un element de tip ''a'' și întoarce un element de tip ''b'' - și o listă de elemente de tip ''a'' și întoarce o listă de elemente de tip ''b''. De precizat că ''a'' și ''b'' pot fi distincte dar nu este necesar. </note> Listele din Haskell sunt **polimorfice**. Ele pot conține date de orice tip. O instanță a listelor are însă un tip concret: <code> Prelude> :t ['a', 'b', 'c'] ['a', 'b', 'c'] :: [Char] </code> ==== Constante polimorfice ==== Care este tipul listei vide? <code> Prelude> :t [] [] :: [a] </code> Observăm că tipul listei vide este general. Asta înseamnă că lista vidă poate fi tratată ca o listă de orice tip. <code> Prelude> [1,2,3] ++ "123" -- eroare, tipuri diferite Prelude> [1,2,3] ++ [] [1,2,3] Prelude> "123" ++ [] "123" </code> Spunem că ''[]'' este o **constantă polimorfică**. <note> O altă constantă polimorfică este, de exemplu ''1''. De aceea putem scrie: <code> Prelude> 1 + 2 3 Prelude> 1 + 2.71 3.71 </code> Dacă forțăm 1 să fie întreg, vom primi o eroare la a doua adunare: <code> Prelude> (1 :: Int) + 2.71 <interactive>:60:14: No instance for (Fractional Int) arising from the literal `2.71' In the second argument of `(+)', namely `2.71' In the expression: (1 :: Int) + 2.71 In an equation for `it': it = (1 :: Int) + 2.71 </code> ''1'' are însă o constrângere despre care vom discuta în laboratorul următor. </note> Pentru a implementa în Haskell un TDA polimorfic, folosim sintaxa: <code haskell> List a = Empty | Cons a (List a) </code> <note> Ce este ''List''?\\ ''List'' este un **constructor de tip**, nu un tip de date. Constructorii de tip primesc ca parametrii //tipuri// și întorc un tip (sau un alt constructor de tip dacă nu primesc suficienți parametrii).\\ Asta înseamnă că, ''List'' nu este un //tip//, dar ''List Int'', ''List Char'' etc. sunt tipuri. </note> ==== Exerciții TDA-uri polimorfice ==== <note important> Încercați să vă obișnuiți să scrieți explicit tipurile tuturor funcțiilor definite de voi în continuare. </note> 5. Pornind de la TDA-ul polimorfic ''List a'' definit mai sus: a) Reimplementați o funcție ce convertește ''Lista a'' în liste (polimorfice) din Haskell.\\ b) Implementați ''foldl'', ''foldr'' și ''map'' pentru TDA-ul creat. \\ 6. a) Implementați TDA-ul pentru arbori polimorfici.\\ b) Implementați o funcție ''tmap'' care este echivalentul lui ''map'' pe arbori.\\ c) Implementați o funcție ''tzipWith'' care este echivalentul lui ''zipWith'' pe arbori.\\ d) Implementați o funcție ce determină suma tuturor elementelor dintr-un arbore.\\ e) Generalizați funcția anterioară, pentru a codifica o operație asociativă pe elementele din arbore.\\ f) Implementați ''foldT''. Câte implementări posibile există?\\ g) Implementați ''tmap'' pe baza ''foldT''.\\ \\ 7. a) Implementați TDA-ul ''Pereche'', care poate conține două valori de orice tip.\\ b) Implementați o funcție care primește două liste (reprezentate folosind TDA-ul anterior) și construiește o listă de perechi. ===== Referințe ===== * [[https://wiki.haskell.org/Abstract_data_type|ADT - Haskell wiki]] * [[https://wiki.haskell.org/Maybe|Maybe - Haskell wiki]] ===== Soluții laborator ===== * [[https://github.com/Programming-Paradigms/Labs/archive/master.zip|Rezolvări]]