Responsabili laborator:

• Dumitru Mihai-Valentin
• Călin Cruceru

Scopul laboratorului:

• Familiarizarea studenților cu tipuri de clase
• Familiarizarea studenților cu constrângeri de tip

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

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:

class Eq a where  
    (==) :: a -> a -> Bool  
    (/=) :: a -> a -> Bool  
    x == y = not (x /= y)  
    x /= y = not (x == y)  

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:

data Color = Red | Green | Blue
 
instance Eq Color where
    Red == Red = True
    Green == Green = True
    Blue == Blue = True
    _ == _ = False

Am redefinit ==, iar definiția lui /= rămâne neschimbată (x /= y = not (x == y)), ceea ce e suficient ca să folosim ambii operatori.

*Main> Red == Red
True
*Main> Red /= Red
False

În laboratoarele trecute, analizând tipurile unor expresii, ați întâlnit notații asemănătoare:

Prelude> :t elem
elem :: (Eq a) => a -> [a] -> Bool

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

*Main> :t (\x -> x == 0)
(\x -> x == 0) :: (Eq a, Num a) => a -> Bool

O definiție posibilă a funcției elem este:

elem :: (Eq a) => a -> [a] -> Bool
elem _ [] = False
elem e (x:xs) = e == x || elem e xs

Ceea ce înseamnă că, odată înrolat tipul nostru clasei Eq, putem folosi, printre altele, și functia elem:

Prelude> elem Red [Blue, Green, Green, Red, Blue]
True

Să considerăm tipul de date polimorfic Either:

data Either a b = Left a | Right b

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

show :: (Show a) => a -> String

Pentru a înrola tipul Either în clasa Show, vom folosi sintaxa:

instance (Show a, Show b) => Show (Either a b) where
    show (Left x) = "Left " ++ show x
    show (Right y) = "Right " ++ show y

1. Fie urmatorul TDA:

 data Result a = Value a | Error 

ale carui valori pot fi folosite pentru a modela conceptul de eroare (exceptie).

Definiti pentru tipul:

 data FIFO a = P [a] [a] 

operatiile:

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

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:

   <expr> ::= <value> | <variable> | <expr> + <expr> | <expr> * <expr> 

unde o valoare poate avea orice tip.

4. Consideram urmatorul constructor de tip:

type Dictionary a = [(String,a)]

care modeleaza dictionare - mapari de tip “nume-variabila”-“valoare polimorfica”

Definiti functia:

valueof :: Dictionary a -> String -> Result a

care intoarce valoarea asociata unui nume-variabila, dintr-un dictionar

5. Definiti urmatoarea clasa:

class Eval t a where
    eval :: Dictionary a -> t a -> Result a

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.

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:

Prelude> show (Cons 1 (Cons 2 (Cons 3 Nil)))
[1,2,3]

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

• Type Classes and Overloading - Haskell wiki
• Typeclassopedia - Haskell wiki
• Typeclasses 101 - Learnyouahaskell
• Typeclasses 102 - Learnyouahaskell