Differences

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

--- laboratoare:04-tipuri-de-date-abstracte [2016/03/20 22:51]
mihai.dumitru2201 Sections
+++ laboratoare:04-tipuri-de-date-abstracte [2016/03/24 14:54] (current)
mihai.dumitru2201 Correction
@@ Line 7: / Line 7: @@
 Scopul laboratorului:
   * Recapitularea conceptului de TDA
-  * Definirea unor TDA-uri în Haskell
+  * Definirea de TDA-uri în Haskell
   * Familiarizarea cu conceptul de TDA-uri polimorfice
+  * Introducerea tipului de date ''Maybe''
@@ Line 16: / Line 17: @@
 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.
+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 pentru
+Unii autori includ în descrierea TDA-urilor și complexități. Din acest punct de vedere, implementările
 ''LinkedList'' și ''ArrayList'' diferă.
 </note>
-=== Constructori ===
+==== Constructori ====
 Valorile posibile ale unui TDA sunt date de constructorii acestuia.\\
@@ Line 62: / Line 63: @@
 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)''.
-=== Exercițiu ===
-. Implementați TDA-ul pentru propria voastră listă care poate conține doar numere întregi.
 <note tip>
@@ Line 92: / Line 88: @@
 </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.
@@ Line 106: / Line 106: @@
 . 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 ===
+==== Înregistrări ====
 Vrem să definim un TDA pentru a descrie un student, folosind următoarele câmpuri: nume, prenume, an de studiu, medie.
@@ Line 157: / Line 196: @@
 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.
-!! In acest laborator, vom specifica explicit tipurile functiilor implementate !!
 ===== TDA-uri polimorfice =====
@@ Line 191: / Line 228: @@
 </code>
-=== Constante polimorfice ===
+==== Constante polimorfice ====
 Care este tipul listei vide?
@@ Line 240: / Line 277: @@
 <code haskell>
-List a = Empty | Cons a (List a)
+data List a = Empty | Cons a (List a)
 </code>
@@ Line 250: / Line 287: @@
 </note>
-=== Exerciții ===
+==== 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:
@@ Line 257: / Line 298: @@
 b) Implementați ''foldl'', ''foldr'' și ''map'' pentru TDA-ul creat.
-\\
 \\
 . a) Implementați TDA-ul pentru arbori polimorfici.\\
@@ Line 267: / Line 307: @@
 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 =====
+  * [[https://wiki.haskell.org/Abstract_data_type|ADT - Haskell wiki]]
+  * [[https://wiki.haskell.org/Maybe|Maybe - Haskell wiki]]
-=== Solutii laborator ===
+===== Soluții laborator =====
-  * [[https://github.com/Programming-Paradigms/Labs/archive/master.zip|Rezolvari]]
+  * [[https://github.com/Programming-Paradigms/Labs/archive/master.zip|Rezolvări]]

pp-cb

User Tools

Site Tools

Differences

Page Tools