Differences

This shows you the differences between two versions of the page.

--- laboratoare:04-tipuri-de-date-abstracte [2015/03/17 15:07]
lucian.mogosanu [TDA-uri monomorfice: Liste monomorfice, inregistrari]
+++ laboratoare:04-tipuri-de-date-abstracte [2016/03/24 14:54] (current)
mihai.dumitru2201 Correction
@@ Line 1: / Line 1: @@
-===== Laborator 4 - Tipuri de date abstracte =====
+====== Tipuri de date abstracte ======
-!! In acest laborator, vom specifica explicit tipurile functiilor implementate !!
+Responsabili laborator:
+  * [[mihai.dumitru@cti.pub.ro|Dumitru Mihai-Valentin]]
+  * [[calin.cruceru@cti.pub.ro|Călin Cruceru]]
-==== TDA-uri monomorfice: Liste monomorfice, inregistrari ====
+Scopul laboratorului:
-  * Implementati TDA-ul: "lista de numere naturale"
+  * Recapitularea conceptului de TDA
-  * Scrieti o functie care converteste valori ale TDA-ului vostru in liste din Haskell
+  * Definirea de TDA-uri în Haskell
-  * Implementati TDA-ul "optiune", care codifica valori optionale de tipul Integer, e.g. fie ''None'', fie o valoare intreaga
+  * Familiarizarea cu conceptul de TDA-uri polimorfice
-  * Scrieti un TDA care codifica un tuplu (inregistrare) format din urmatoarele campuri:
+  * 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 Java, 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 ====
+. Implementați TDA-ul pentru propria voastră listă care poate conține doar numere întregi.
+. 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>
+. 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>
+. a) Scrieți un TDA care codifică un tuplu (înregistrare) format din următoarele câmpuri:
      * Nume (codificat ca String)
-     * Varsta (codificat ca Integer)
+     * Vârstă (codificat ca Integer)
      * Prieteni (codificat ca o lista de String-uri)
-     * Nota PP (codificat ca Integer). Acest camp este optional!
+     * Notă PP (codificat ca Integer). Acest câmp este opțional!
-  * Scrieti o functie care primeste o lista de inregistrari, si le intoarce pe acelea pentru care varsta este mai mare ca 20
+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.
-  * Scrieti o functie care primeste o lista de inregistrari, si le intoarce pe acelea care contin cel putin un prieten cu numele "Matei"
-  * Scrieti o functie care primeste o lista de inregistrari, si le intoarce pe acelea care contin campul "Nota PP"
+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".
-  * Scrieti o functie care primeste o lista de nume, o lista de varste, o lista ce contine liste de prieteni, si intoarce o lista de inregistrari corespunzatoare
+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
+
+Prelude> 1 + 2.71
+.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>
+data 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>
+. 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.
+\\
+. 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''.\\
+\\
+. 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 =====
-==== TDA-uri polimorfice: Liste, Arbori, Perechi ====
+  * [[https://wiki.haskell.org/Abstract_data_type|ADT - Haskell wiki]]
-=== Liste polimorfice ===
+  * [[https://wiki.haskell.org/Maybe|Maybe - Haskell wiki]]
-  * Implementati TDA-ul "Lista polimorfica"
-  * Re-implementati o functie ce converteste Liste definite anterior, in liste (polimorfice) din Haskell
-  * Implementati ''foldl'', ''foldr'' si ''map'' pentru TDA-ul creat
-=== Arbori polimorfici ===
+===== Soluții laborator =====
-  * Implementati TDA-ul "Arbore polimorfic"
-  * Implementati o functie ''tmap'' care este echivalentul lui ''map'' pe arbori
-  * Implementati o functie ''tzipWith'' care este echivalentul lui ''zipWith'' pe arbori
-  * Implementati ''tfoldl'' si ''tfoldr''
-=== Perechi ===
+  * [[https://github.com/Programming-Paradigms/Labs/archive/master.zip|Rezolvări]]
-  * Implementati TDA-ul "Pereche". Observatie: O pereche poate contine valori de orice tip
-  * Implementati o functie care primeste doua liste (reprezentate folosind TDA-ul anterior) si construieste o lista de perechi

pp-cb

User Tools

Site Tools

Differences

Page Tools