pp-cb

This is an old revision of the document!

---

===== Type-classes ===== Responsabili laborator: * [[mihai.dumitru@cti.pub.ro|Dumitru Mihai-Valentin]] * [[calin.cruceru@cti.pub.ro|Călin Cruceru]] Scopul laboratorului: * Recapitularea conceptului de TDA ===== 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> Aceasta * (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 ==== * (Re)definiți tipul de date polimorfic ''Tree a'' * (Re)implementați ''tmap'' (echivalentul lui ''map'' pe arbori) * (Re)implementați ''tzipWith'' (echivalentul lui ''zipWith'' pe arbori) * (Re)implementați ''foldT'' (fold pe arbori) * (Re)implementați ''tmap'' pe baza lui ''foldT'' * 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. ==== Type-classes (multimi de tipuri) ==== * Înrolați tipurile de date ''List a'' și ''Tree a'' în clasa ''Show'' * Î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''