pp-cb

This is an old revision of the document!

---

====== Clase de tipuri ====== Responsabili laborator: * [[mihai.dumitru@cti.pub.ro|Dumitru Mihai-Valentin]] * [[calin.cruceru@cti.pub.ro|Călin Cruceru]] Scopul laboratorului: * Familiarizarea studenților cu tipuri de clase * Familiarizarea studenților cu constrângeri de tip ===== Typeclasses ===== O clasă de tipuri (typeclass) este un fel de interfață care definește un comportament. Dacă un tip de date face parte dintr-o anume clasă de tipuri, atunci putem lucra pe tipul respectiv cu operațiile definite în clasă. <note hint> Conceptul de clasă de tipuri este diferit de conceptul de clasă din programarea orientată pe obiecte. O comparație mai pertinentă este între clasele de tip din Haskell și interfețele din Java. </note> O clasă des întâlnită este clasa ''Eq''. Orice tip care este o instanță a acestei clase poate fi comparat, utilizând funcțiile ''=='' și ''/=''. Clasa ''Eq'' este definită mai jos. Observați sintaxa Haskell: <code haskell> class Eq a where (==) :: a -> a -> Bool (/=) :: a -> a -> Bool x == y = not (x /= y) x /= y = not (x == y) </code> Observăm că definițiile pentru ''=='' și ''/='' depind una de cealaltă. Acest lucru ne ușurează munca atunci când vrem să înrolăm un tip acestei clase, pentru că trebuie să redefinim doar unul dintre cei doi operatori. Pentru a vedea cum lucrăm cu clase, vom defini un tip de date simplu și îl vom înrola în ''Eq'': <code haskell> data Color = Red | Green | Blue instance Eq Color where Red == Red = True Green == Green = True Blue == Blue = True _ == _ = False </code> Am redefinit ''=='', iar definiția lui ''/='' rămâne neschimbată (''x /= y = not (x == y)''), ceea ce e suficient ca să folosim ambii operatori. <code> *Main> Red == Red True *Main> Red /= Red False </code> <note> În acest caz, puteam obține același comportament folosind implementarea default oferită de cuvântul cheie ''deriving'', i.e.\\ ''data Color = Red | Green | Blue deriving (Eq)''. </note> ===== Constrângeri de clasă ===== În laboratoarele trecute, analizând tipurile unor expresii, ați întâlnit notații asemănătoare: <code> Prelude> :t elem elem :: (Eq a) => a -> [a] -> Bool </code> Partea de după ''=%%>%%'' ne spune că funcția ''elem'' primește un element de un tip oarecare, ''a'' și o listă cu elemente de același tip și întoarce o valoare booleană. ''(Eq a)'' precizează că tipul de date ''a'' trebuie să fie o instanță a clasei ''Eq'' și nu orice tip. De aceea se numește o **constrângere de clasă** (class constraint). <note> Toate constrângerile de clasă sunt trecute într-un tuplu, înaintea definiției funcției, separate de ''=%%>%%''. <code> *Main> :t (\x -> x == 0) (\x -> x == 0) :: (Eq a, Num a) => a -> Bool </code> </note> O definiție posibilă a funcției ''elem'' este: <code haskell> elem :: (Eq a) => a -> [a] -> Bool elem _ [] = False elem e (x:xs) = e == x || elem e xs </code> Ceea ce înseamnă că, odată înrolat tipul nostru clasei ''Eq'', putem folosi, printre altele, și functia ''elem'': <code> Prelude> elem Red [Blue, Green, Green, Red, Blue] True </code> ===== Clase de tipuri și tipuri de date polimorfice ===== Să considerăm tipul de date polimorfic ''Either'': <code haskell> data Either a b = Left a | Right b </code> Ț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. 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 ===== 1. 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). 2. Înrolați aceleași tipuri în clasa ''Eq''. 3. Implementați sortarea pentru ''List a'', unde ''a'' e un tip oarecare înrolat în clasa ''Ord''. 4. Implementați căutarea binară pentru ''Tree a'', unde ''a'' e un tip oarecare înrolat în clasa ''Ord''. 5. Înrolați tipurile de date ''List'' și ''Tree'' în clasa ''Functor''. ===== Resurse ===== * [[https://www.haskell.org/tutorial/classes.html|Type Classes and Overloading - Haskell wiki]] * [[https://wiki.haskell.org/Typeclassopedia|Typeclassopedia - Haskell wiki]] * [[http://learnyouahaskell.com/types-and-typeclasses#typeclasses-101|Typeclasses 101 - Learnyouahaskell]] * [[http://learnyouahaskell.com/making-our-own-types-and-typeclasses#typeclasses-102|Typeclasses 102 - Learnyouahaskell]]