Differences

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

--- laboratoare:05-polimorfism [2016/04/04 23:13]
mihai.dumitru2201
+++ laboratoare:05-polimorfism [2016/04/05 15:58] (current)
matei.popovici
@@ Line 1: / Line 1: @@
-===== Type-classes =====
+====== Clase de tipuri (Type-classes) ======
 Responsabili laborator:
@@ Line 6: / Line 6: @@
 Scopul laboratorului:
-  * Recapitularea conceptului de TDA
+  * Familiarizarea studenților cu tipuri de clase
+  * Familiarizarea studenților cu constrângeri de tip
 ===== Typeclasses =====
@@ Line 91: / Line 92: @@
-Aceasta
+===== Clase de tipuri și tipuri de date polimorfice =====
-  * (Re)definiți tipul de date polimorfic ''List a''
-  * (Re)implementați funcțiile ''foldr'', ''foldl'', ''map'' și ''filter'' pentru TDA-ul creat
-==== TDA-ul arbore ====
+Să considerăm tipul de date polimorfic ''Either'':
-  * (Re)definiți tipul de date polimorfic ''Tree a''
+<code haskell>
-  * (Re)implementați ''tmap'' (echivalentul lui ''map'' pe arbori)
+data Either a b = Left a | Right b
-  * (Re)implementați ''tzipWith'' (echivalentul lui ''zipWith'' pe arbori)
+</code>
-  * (Re)implementați ''foldT'' (fold pe arbori)
-  * (Re)implementați ''tmap'' pe baza lui ''foldT''
+Țineți minte că ''Either'' nu este un tip, ci un //constructor de tip//. ''Either Int String'', ''Either Char Bool'' etc. sunt tipuri propriu-zise.
-  * Implementați operația de transformare a unui ''Tree a'' într-un ''List a'', folosind traversarea arborelui în preordine/inordine/postordine.
-  * Implementati operatia ''mirror'' pe arbori.
+O clasă utilă de tipuri este clasa ''Show'', care oferă funcția ''show'' care primește un parametru și întoarce reprezentarea acestuia sub formă de șir de caractere.
+<code haskell>
+show :: (Show a) => a -> String
+</code>
+Pentru a înrola tipul ''Either'' în clasa ''Show'', vom folosi sintaxa:
+<code haskell>
+instance (Show a, Show b) => Show (Either a b) where
+    show (Left x) = "Left " ++ show x
+    show (Right y) = "Right " ++ show y
+</code>
+<note important>
+Observați constrângerile de clasă ''(Show a, Show b)''! În implementarea funcției ''show'' pentru tipul ''Either a b'', folosim aplicațiile ''show x'' și ''show y'', deci aceste elemente trebuie să aibă, la rândul lor, un tip înrolat în clasa Show.
+</note>
+===== Exerciții =====
+. Fie urmatorul TDA:
+<code> data Result a = Value a | Error </code>
+ale carui valori pot fi folosite pentru a modela conceptul de eroare (exceptie).
+Definiti pentru tipul:
+<code> data FIFO a = P [a] [a] </code>
+operatiile:
+<code>
+push :: a -> FIFO a -> Result (FIFO a)
+pop :: FIFO a -> Result (FIFO a)
+mpop :: Integer -> FIFO a -> Result (FIFO a)
+top :: FIFO a -> Result a
+</code>
+care trateaza cazurile in care ''top'', ''pop'' si ''mpop'' produc eroare.
+//Hint:// Pentru ''mpop'', folositi **case** si **guards**.
+. Inrolati ''FIFO a'' in clasa ''Show''
+. Definiti un tip de date asociat urmatoarei gramatici:
+<code>
+   <expr> ::= <value> | <variable> | <expr> + <expr> | <expr> * <expr>
+</code>
+unde o valoare poate avea orice tip.
+. Consideram urmatorul constructor de tip:
+<code>
+type Dictionary a = [(String,a)]
+</code>
+care modeleaza //dictionare// - mapari de tip "nume-variabila"-"valoare polimorfica"
+Definiti functia:
+<code>valueof :: Dictionary a -> String -> Result a</code>
+care intoarce valoarea asociata unui nume-variabila, dintr-un dictionar
+. Definiti urmatoarea clasa:
+<code>
+class Eval t a where
+    eval :: Dictionary a -> t a -> Result a
+</code>
+Spre deosebire de clasele prezentate in exemplele anterioare, care desemneaza o //proprietate// a unui tip sau constructor de tip, ''Eval'' stabileste o **relatie** intre un constructor de tip ''t'' si un tip ''a''. Relatia spune ca orice container de tip ''t a'' poate fi evaluat in prezenta unui dictionar cu valori de tip ''a'', la o valoare de tip ''Result a''.
+. Inrolati ''Expr'' si ''Integer'' in clasa ''Eval''. Care este semnificatia evaluarii?
+. Inrolati ''Expr'' si ''FIFO a'' in clasa ''Eval''. Semnificatia inmultirii este //concatenarea// a doua FIFO.
+===== Alte exercitii =====
+. Ați definit, în laboratorul anterior, tipurile polimorfice ''List a'' și ''Tree a''. Pentru le putea reprezenta, ați folosit implementarea implicită a funcției ''show'', oferită de ''deriving (Show)''. Aceasta nu era însă o reprezentare citibilă.
+Ne dorim să reprezentăm tipul listă, la fel ca cel existent în Haskell:
+<code>
+Prelude> show (Cons 1 (Cons 2 (Cons 3 Nil)))
+[1,2,3]
+</code>
+(Pentru arbori există multe reprezentări posibile, puteți alege orice reprezentare preferați).
+. Înrolați aceleași tipuri în clasa ''Eq''.
+. Implementați sortarea pentru ''List a'', unde ''a'' e un tip oarecare înrolat în clasa ''Ord''.
+. Implementați căutarea binară pentru ''Tree a'', unde ''a'' e un tip oarecare înrolat în clasa ''Ord''.
+. Înrolați tipurile de date ''List'' și ''Tree'' în clasa ''Functor''.
-==== Type-classes (multimi de tipuri) ====
+===== Resurse =====
-  * Înrolați tipurile de date ''List a'' și ''Tree a'' în clasa ''Show''
+  * [[https://www.haskell.org/tutorial/classes.html|Type Classes and Overloading - Haskell wiki]]
-  * Înrolați aceleași tipuri în clasa ''Eq''
+  * [[https://wiki.haskell.org/Typeclassopedia|Typeclassopedia - Haskell wiki]]
-  * Implementați sortarea pentru ''List a'', unde ''a'' e un tip oarecare înrolat în clasa ''Ord''
+  * [[http://learnyouahaskell.com/types-and-typeclasses#typeclasses-101|Typeclasses 101 - Learnyouahaskell]]
-  * Implementați căutarea binară pentru ''Tree a'', unde ''a'' e un tip oarecare înrolat în clasa ''Ord''
+  * [[http://learnyouahaskell.com/making-our-own-types-and-typeclasses#typeclasses-102|Typeclasses 102 - Learnyouahaskell]]
-  * Înrolați tipurile de date ''List'' și ''Tree'' în clasa ''Functor''

pp-cb

User Tools

Site Tools

Differences

Page Tools