Tipuri de date abstracte

Responsabili laborator:

• Dumitru Mihai-Valentin
• Călin Cruceru

Scopul laboratorului:

• Recapitularea conceptului de TDA
• Definirea de TDA-uri în Haskell
• Familiarizarea cu conceptul de TDA-uri polimorfice
• Introducerea tipului de date Maybe

Tipurile de date abstracte sunt modele pentru a defini tipuri de date în funcție de comportamentul acestora (valori posibile, axiome, operații), contrastând cu structurile de date, definite din punct de vedere al implementării.

Un TDA familiar este list. În primul laborator am lucrat cu liste de întregi, definind o listă ca fiind fie lista vidă, fie un întreg introdus în altă listă. Deasemena am definit o mulțime de operații posibile pe listă: isEmpty, head, tail, add, get, ins, show.
Pentru a lucra cu liste într-un limbaj ca Java, am scris două implementări distincte, și anume LinkedList și ArrayList. Ambele implementări respectă specificațiile din primul paragraf.

Valorile posibile ale unui TDA sunt date de constructorii acestuia.
Să considerăm un tip simplu de date: Bool, care poate avea două valori: False și True.
Sintaxa Haskell pentru a defini acest tip de date este următoarea:

data Bool = False | True

False și True nu sunt parametrizate și pot fi privite ca valori. Se mai numesc și constructori nulari.

Să considerăm un alt TDA care descrie un arbore binar cu valori întregi. Arborele poate fi gol sau un nod cu doi copii.

data Tree = Nil | Node Int Tree Tree

Node este un constructor care primește un argument de tipul Int și două argumente de tip Tree, pentru a creea o valoare de tip Tree. Putem să ne gândim la el ca la o funcție:

Prelude> :t Node
Node :: Int -> Tree -> Tree -> Tree

Constructorii sunt foarte importanți în pattern matching. Ca exemplu, vom scrie o funcție care însumează toate valorile dintr-un arbore:

treeSum :: Tree -> Int
treeSum Nil = 0
treeSum (Node v l r) = v + (treeSum l) + (treeSum r)

Observăm prezența a două pattern-uri: unul pentru arborele vid, celălalt pentru un nod, într-un fel foarte asemănător cu modul în care lucram cu liste, făcând pattern matching pe [] și (x:xs).

Prelude> Node 1 Nil Nil

<interactive>:38:1:
    No instance for (Show Tree) arising from a use of `print'
    In a stmt of an interactive GHCi command: print it

data Tree = Nil | Node Int Tree Tree deriving (Show)

Prelude> Node 1 Nil Nil
Node 1 Nil Nil

1. Implementați TDA-ul pentru propria voastră listă care poate conține doar numere întregi.

2. Scrieți o funcție care convertește valori ale TDA-ului vostru în liste din Haskell.

convertList :: List -> [Int]

3. Implementați TDA-ul “optiune”, care codifică valori opționale de tip Integer (e.g. fie None, fie o valoare întreagă).

-- presupunem ca Optiune are constructorii "None" si "Value Int"
rootValue :: Tree -> Optiune
rootValue Nil = None
rootValue (Node v _ _) = Value v

pretty :: Optiune -> String
pretty None = "No value"
pretty (Value v) = "Value is " ++ show v
 
printRootValue :: Tree -> String
printRootValue = pretty . rootValue

*Main> printRootValue (Node 1 (Node 1 Nil (Node 2 Nil Nil)) (Node 3 (Node 4 (Node 5 Nil Nil) Nil) (Node 6 Nil Nil)))
"Value is 1"
*Main> printRootValue Nil
"No value"

data Maybe a = Nothing | Just a

Vrem să definim un TDA pentru a descrie un student, folosind următoarele câmpuri: nume, prenume, an de studiu, medie.

-- tipul de date si constructorul au acelasi nume, ceea ce este ok
-- pentru ca reprezinta concepte diferite.
data Student = Student String String Int Float

Observăm că semnficația câmpurilor nu este evidentă din definiție. Vrem să extragem valori dintr-un Student; definim funcțiile:

nume :: Student -> String
nume (Student n _ _ _) = n
 
prenume :: Student -> String
prenume (Student _ p _ _) = p
 
an :: Student -> Int
an (Student _ _ a _) = a
 
medie :: Student -> Float
medie (Student _ _ _ m) = m

Pentru a face descrierea tipului de date mai clară și a evita să scriem manual acele funcții, putem folosi sintaxa:

data Student = Student { nume :: String
                       , prenume :: String
                       , an :: Int
                       , medie :: Float
                       }

4. a) Scrieți un TDA care codifică un tuplu (înregistrare) format din următoarele câmpuri:

• Nume (codificat ca String)
• Vârstă (codificat ca Integer)
• Prieteni (codificat ca o lista de String-uri)
• Notă PP (codificat ca Integer). Acest câmp este opțional!

b) Scrieți o funcție care primește o listă de înregistrări și le întoarce pe acelea pentru care vârsta este mai mare ca 20.

c) Scrieți o funcție care primește o listă de înregistrări și le întoarce pe acelea care conțin cel puțin un prieten cu numele “Matei”.

d) Scrieți o funcție care primește o listă de înregistrări și le întoarce pe acelea care conțin câmpul “Notă PP”.

e) Scrieți o funcție care primește o listă de nume, o listă de vârste, o listă ce conține liste de prieteni, și întoarce o listă de înregistrări corespunzătoare.

Până acum, am definit TDA-uri care lucrează doar cu întregi. Dorim să scăpăm de această limitare și să definim TDA-uri care pot lucra cu orice alt tip de date. De exemplu, are sens să considerăm capul unei liste care conține elemente de tip a, ca fiind un element de tip a, indiferent de cum arată acest tip.

Într-adevăr, aceasta este definiția funcției head existentă în Haskell:

Prelude> :t head
head :: [a] -> a

a se numește variabilă de tip și poate să reprezinte orice tip de date (evident, cu condiția ca toate a-urile care apar să se refere la același tip).

Prelude> :t map
map :: (a -> b) -> [a] -> [b]

Listele din Haskell sunt polimorfice. Ele pot conține date de orice tip. O instanță a listelor are însă un tip concret:

Prelude> :t ['a', 'b', 'c']
['a', 'b', 'c'] :: [Char]

Care este tipul listei vide?

Prelude> :t []
[] :: [a]

Observăm că tipul listei vide este general. Asta înseamnă că lista vidă poate fi tratată ca o listă de orice tip.

Prelude> [1,2,3] ++ "123" -- eroare, tipuri diferite
Prelude> [1,2,3] ++ []
[1,2,3]
Prelude> "123" ++ []
"123"

Spunem că [] este o constantă polimorfică.

Prelude> 1 + 2
3
Prelude> 1 + 2.71
3.71

Prelude> (1 :: Int) + 2.71

<interactive>:60:14:
    No instance for (Fractional Int) arising from the literal `2.71'
    In the second argument of `(+)', namely `2.71'
    In the expression: (1 :: Int) + 2.71
    In an equation for `it': it = (1 :: Int) + 2.71

Pentru a implementa în Haskell un TDA polimorfic, folosim sintaxa:

data List a = Empty | Cons a (List a)

5. Pornind de la TDA-ul polimorfic List a definit mai sus:

a) Reimplementați o funcție ce convertește Lista a în liste (polimorfice) din Haskell.
b) Implementați foldl, foldr și map pentru TDA-ul creat.

6. a) Implementați TDA-ul pentru arbori polimorfici.
b) Implementați o funcție tmap care este echivalentul lui map pe arbori.
c) Implementați o funcție tzipWith care este echivalentul lui zipWith pe arbori.
d) Implementați o funcție ce determină suma tuturor elementelor dintr-un arbore.
e) Generalizați funcția anterioară, pentru a codifica o operație asociativă pe elementele din arbore.
f) Implementați foldT. Câte implementări posibile există?
g) Implementați tmap pe baza foldT.

7. a) Implementați TDA-ul Pereche, care poate conține două valori de orice tip.
b) Implementați o funcție care primește două liste (reprezentate folosind TDA-ul anterior) și construiește o listă de perechi.

• ADT - Haskell wiki
• Maybe - Haskell wiki

• Rezolvări