====== Clase de tipuri (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. 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**.

2. Inrolati ''FIFO a'' in clasa ''Show''

3. Definiti un tip de date asociat urmatoarei gramatici:
<code>
   <expr> ::= <value> | <variable> | <expr> + <expr> | <expr> * <expr> 
</code>
unde o valoare poate avea orice tip.

4. 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

5. 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''.

6. Inrolati ''Expr'' si ''Integer'' in clasa ''Eval''. Care este semnificatia evaluarii?

7. Inrolati ''Expr'' si ''FIFO a'' in clasa ''Eval''. Semnificatia inmultirii este //concatenarea// a doua FIFO. 

===== Alte exercitii =====
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]]