pp-cb

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Type-classes ======

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]]
pp-cb

User Tools

Site Tools

Page Tools
