Clase de tipuri (Type-classes)

Clase de tipuri (Type-classes)

Responsabili laborator:

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

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.

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

Constrângeri de clasă

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

Toate constrângerile de clasă sunt trecute într-un tuplu, înaintea definiției funcției, separate de =>.

*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

Clase de tipuri și tipuri de date polimorfice

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

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.

Exerciții

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.

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:

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.

Table of Contents