Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

PROGRAMIRANJE U HASKELLU

Ak.god. 2011/12.

LEKCIJA 10: korisnički tipovi podataka 2

v1.0

(c) 2011 Jan Šnajder

==============================================================================

> import Data.List

=== REKURZIVNE PODATKOVNE STRUKTURE ==========================================

Podatkovne strukture mogu biti rekurzivne. Zapravo, najkorisnije podatkovne
strukture su one rekurzivne.

> data Sex = Male | Female deriving (Show,Read,Eq,Ord)

> data Person = Person {
>   idNumber :: String,
>   forename :: String,
>   surname  :: String,
>   sex      :: Sex,
>   age      :: Int,
>   partner  :: Maybe Person,
>   children :: [Person] } deriving (Show,Read,Eq,Ord)

Jedna obiteljska situacija: Pero i Ana su Markovi roditelji, Marko i Maja su
zajedno...

> pero  = Person "2323" "Pero"  "Perić" Male   45 (Just ana)   [marko]
> ana   = Person "3244" "Ana"   "Anić"  Female 43 (Just pero)  [marko,iva]
> marko = Person "4341" "Marko" "Perić" Male   22 (Just maja)  []
> maja  = Person "7420" "Maja"  "Majić" Female 20 (Just marko) []
> iva   = Person "4642" "Iva"   "Ivić"  Female 16 Nothing      []

Pokušajte ispisati vrijednost 'pero'. Što se događa? Zašto?

'pero' (i ostale osobe) su beskonačno rekurzivne strukture. To je zato što je
Perin partner Ana, a Anin partner je opet Pero, čiji je partner Ana itd. Ako
ove odnose prikažemo grafom, i ako graf ima cikluse, onda tom grafu odgovara
beskonačna rekurzivna struktura!

Što će se ovdje dogoditi?:

  pero == ana
  pero == pero

Prva usporedba radi OK, druga nikada ne terminira jer je 'pero' beskonačna
struktura.

Funkcija koja vraća partnerovo ime, ako takav postoji:

> partnersForename :: Person -> Maybe String
> partnersForename p = case partner p of
>   Just p  -> Just $ forename p
>   Nothing -> Nothing

ili kraće:

> partnersForename2 :: Person -> Maybe String
> partnersForename2 = fmap forename . partner

Zajednička djeca dvaju partnera:

> pairsChildren :: Person -> [Person]
> pairsChildren p = nub $ children p ++ case partner p of 
>   Nothing -> []
>   Just p  -> children p

ili kraće:

> pairsChildren2 :: Person -> [Person]
> pairsChildren2 p = nub $ children p ++ maybe [] children (partner p)

Hoće li ovo raditi? 

Ne, problem je 'nub' koji mora moći uspoređivati dva elementa. Ako postoje
jednaki elementi, takva usporedba nikada neće završiti.

A sad nešto drugačije. Imate li ideju kako napraviti sljedeću funkciju?

  partnersMother :: Person -> Maybe Person

Nažalost nikako, jer nemamo vezu nazad prema roditeljima. Trebamo bismo ili
dodati vezu prema roditeljima, ili sve osobe staviti u listu, pa tako naći
majku zadane osobe.

Prvi pristup:

> data Person2 = Unknown2 | Person2 {
>   forename2 :: String,
>   surname2  :: String,
>   sex2      :: Sex,
>   mother2   :: Person2,
>   father2   :: Person2,
>   partner2  :: Maybe Person2,
>   children2 :: [Person2] } deriving (Show,Read,Eq,Ord)

=== VJEŽBA 1 =================================================================

1.1.
- Napišite funkciju
  partnersMother :: Person2 -> Maybe Person2

1.2.
- Napišite funkciju
  parentCheck :: Person2 -> Bool
  koja provjerava je li zadana osoba jedno od djeteta nekog od njezinih
  roditelja.

1.3.
- Napišite funkciju
  sister :: Person2 -> Maybe Person2
  koja vraća sestru neke osobe, ako takva postoji.

1.4.
- Napišite funkciju koja vraća sve potomke neke osobe.
  descendant :: Person2 -> [Person2]
 
==============================================================================

Lista je također rekurzivna struktura, a k tome još i parametrizirana:

> data MyList a = Empty | Cons a (MyList a) deriving (Show,Read,Eq,Ord)

Npr.

> l1 = 1 `Cons` Empty
> l2 = 1 `Cons` (2 `Cons` (3 `Cons` Empty))

Radi preglednosti, možemo definirati svoj infiksni operator:

> infixr 5 -+-
> (-+-) = Cons

Razine su u rasponu 0 (najmanji prioritet) do 9 (najveći prioritet). Npr. ($)
ima prioritet 0, a (.) ima prioritet 9. Više na:
http://www.haskell.org/onlinereport/decls.html#fixity

Pa sada možemo pisati:

> l3 = 1 -+- 2 -+- 3 -+- Empty

=== VJEŽBA 2 =================================================================

2.1.
- Definirajte 
  listHead :: MyList a -> Maybe a
 
2.2.
- Definirajte funkciju koja radi kao 'map', ali nad listom tipa 'MyList'.
  listMap :: (a -> b) -> MyList a -> MyList b

==============================================================================

Prototipan primjer rekurzivne podatkovne strukture je stablo.

Evo binarnog stabla koje pohranjuje vrijednosti u unutarnjim čvorovima:

> data Tree a = Null | Node a (Tree a) (Tree a) deriving (Show,Eq)

Stablo cijelih brojeva:

> intTree :: Tree Int
> intTree = Node 1 (Node 2 Null Null) (Node 3 Null Null)

Funkcija koja zbraja elemente u binarnom stablu cijelih brojeva:

> sumTree :: Tree Int -> Int
> sumTree Null                = 0
> sumTree (Node x left right) = x + sumTree left + sumTree right

Funkcija koja provjerava nalazi li se zadani element u stablu:

> treeElem :: Eq a => a -> Tree a -> Bool
> treeElem _ Null = False
> treeElem x (Node y left right) 
>   | x == y    = True
>   | otherwise = treeElem x left || treeElem x right

=== VJEŽBA 3 =================================================================

3.1.
- Napišite funkciju
  treeMax :: Ord a => Tree a -> a
  koja nalazi maksimalan element u stablu, ili error ako je stablo prazno.

3.2.
- Napišite funkciju
  treeElems :: Ord a => Tree a -> [a]
  koja će pokupiti u listu sve elemente iz čvorova stabla u
  INORDER-redoslijedu (lijevo-korijen-desno).

3.3.
- Napišite funkciju koja reže stablo na zadanoj dubini (korijen je na dubini
  0).
  levelCut :: Int -> Tree a -> Tree a

==============================================================================

Sortirano stablo (binarno stablo pretraživanja): za svaki čvor, u lijevom
podstablu su manje vrijednosti, a u desnom veće od vrijednosti u tom čvoru.

Umetanje u binarno stablo pretraživanja:

> treeInsert :: Ord a => a -> Tree a -> Tree a
> treeInsert x Null = Node x Null Null
> treeInsert x t@(Node y l r) 
>   | x < y     = Node y (treeInsert x l) r
>   | x > y     = Node y l (treeInsert x r)
>   | otherwise = t

=== VJEŽBA 4 =================================================================

4.1.
- Napišite funkciju koja uzima listu i pretvara je u sortirano stablo.
  listToTree :: Ord a => [a] -> Tree a

4.2.
- Napišite obrnutu funkciju (u inorder-redoslijedu)
  treeToList :: Tree a -> [a]

4.3.
- Pomoću ovih dviju funkcija napravite funkciju:
  sortAndNub :: Ord a => [a] -> [a]

=== IZVOĐENJE INSTANCI TIPSKIH RAZREDA =======================================

Već smo vidjeli da Haskell za korisničke tipove može automatski izvesti
instance glavnih tipskih razreda: Eq, Ord, Show, Read, ...

Npr. (primjer od ranije):

  data Person = Person {
    idNumber :: String,
    forename :: String,
    surname  :: String,
    sex      :: Sex,
    age      :: Int,
    partner  :: Maybe Person,
    children :: [Person] } deriving (Show,Read,Eq,Ord)

> t1 = marko == ana
> t2 = ana > marko
> t3 = compare ana marko
> ps = sort [marko,ana,pero]

Ako je tip instanca razreda 'Read', onda ga možemo učitavati iz stringa:

> s = read "Male" :: Sex

> p3 = read $ "Person {idNumber=\"111\",forename=\"Ivo\",surname=\"Ivić\"," ++
>             "sex=Male,age=11,partner=Nothing,children=[]}" :: Person

Ugrađeni 'read' učitava vrijednost koja je pisana u Haskellovoj sintaksi. Isto
tako, ugrađeni 'show' ispisuje vrijednost u Haskellovoj sintaksi. Korisnik može
redefinirati 'read' i 'show' funkcije, ali to se preporuča samo u nekim
situacijama (vidjet ćemo kasnije). 'read' nam je koristan za učitavanje
podataka iz datoteke.

Razred 'Enum' omogućava pobrojavanje:

> data Weekday = 
>   Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
>   deriving (Show,Enum)

> yesterday :: Weekday -> Weekday
> yesterday = pred

> dayAfterYesterday :: Weekday -> Weekday
> dayAfterYesterday = succ . pred

> workDays = [Monday .. Friday]

=== INSTANCE TIPSKIH RAZREDA =================================================

Najprije podsjetnik: tipski razredi nemaju veze s razredima u OO-programiranju.

Kako bismo za naš podatkovni tip definirali drugačiju provjeru jednakosti?
Npr., dvije osobe možemo smatrati jednakima ako imaju isti matični broj. Tada
ne moramo niti provjeravati druga polja (što je dobro jer je ova struktura
beskonačna). Slično, možemo definirati poredak prema matičnom broju.

Pogledajmo prvo kako je u Haskellu uopće definiran razred 'Eq':

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

U definiciji razreda navodi se njegovo ime, zatim tipska varijabla, i onda
tipske signature funkcija koje moraju biti definirane za taj tip. U ovom
slučaju to su funkcije (==) i (/=). Ne definiraju se tijela funkcije, nego samo
tipske signature. 

Zatim se u nastavku mogu (ali ne moraju) dati podrazumijevane definicije
funkcija. U ovom slučaju to je napravljeno. 

Ako postoje podrazumijevane definicije funkcija, onda to znači da se ne moraju
definirati sve funkcije. Npr. u ovom slučaju dovoljno je definirati funkciju
(==), budući da je onda funkcija (/=) definirana pomoću funkcije (==). Dakle,
trebamo definirati samo one funkcije koje nemaju podrazumijevanu definiciju. To
se zove NAJMANJA POTPUNA DEFINICIJA (engl. minimal complete definition).

U slučaju klase 'Eq', minimalna potpuna definicija je ili funkcija (==) ili
funkcija (/=).

Kako se definira da je neki tip instanca nekog razreda, npr. razreda 'Eq'?
Ovako:

instance Eq Weekday where
  Monday    == Monday    = True
  Tuesday   == Tuesday   = True
  Wednesday == Wednesday = True
  Thursday  == Thursday  = True
  Friday    == Friday    = True
  Saturday  == Saturday  = True
  Sunday    == Sunday    = True
  _         == _         = False

Naravno, ovo bi bilo dosta naporno da to uvijek moramo raditi, pa baš zato
postoji mogućnost automatskog izvođenja instanci.

Sada možemo napraviti drugačiju definiciju jednakosti za tip 'Person':

  instance Eq Person where
    p1 == p2 = idNumber p1 == idNumber p2

Napomena: sada iz definicije 'Person' treba maknuti automatsko izvođenje
instance za razred 'Eq'.

Sada će 'pero == pero' raditi (provjerite).

Definirajmo i instancu razreda 'Ord'. Najmanja potpuna definicija je funkcija
(<=). Dakle dovoljno je ovako definirati:

  instance Ord Person where
    p1 <= p2 = idNumber p1 <= idNumber p2

Napomena: u ghici-u naredom ":info" možete vidjeti definiciju tipskog razreda i
svih njegovih instanci.

=== VJEŽBA 5 =================================================================

5.1.
- Definirajte instancu 'Eq' za tip 'Weekday' koja radi kao (==), osim što dva
  petka nikad nisu identična.

5.2.
- Definirajte 'Person' kao instancu razreda 'Show' tako da se umjesto partnera
  i djece ispisuju samo njihova imena (a ne vrijednosti), što će omogućiti
  prikaz strukture premda je beskonačna.

==============================================================================

Što ako želimo definirati instancu za parametrizirani tip?

Nije problem. Pri definiciji instance uz tipski konstruktor treba navesti i
tipsku varijablu. Npr.:

  instance Eq (Maybe a) 
    Just x  == Just y   = x == y
    Nothing == Nothing  = True
    _       == _        = False

Digresija: Zašto ne možemo napisati samo 'Maybe'? Zato što klasa 'Eq' očekuje
tip, a 'Maybe' nije tip, nego tipski konstruktor. To znači da tipski
konstruktor 'Maybe', kad mu se da neki tip, vraća tip. Npr. 'Maybe Int' je tip.
Znači 'Maybe' nije isto kao 'Int'. 'Either' očekuje čak dva tipa, prije nego
što vrati tip. Dakle, ovi tipski konstruktori su različitog "tipa". U Haskellu
govorimo o VRSTAMA (engl. kinds): Int, Maybe i Either su tipski konstruktori
različitih vrsta. Vrsta tipskog konstruktora se može provjeriti naredbom
":kind" u ghci-u:

  Int :: *
  Maybe :: * -> *
  Either :: * -> * -> *

O vrstama možete razmišljati kao o "tipovima tipova". 
Vrsta '*' je zapravo običan tip.
Vrsta '* -> *' je unarni tipski konstruktor, koji uzima običan tip i onda daje
običan tip. Itd.

== VJEŽBA 6 ==================================================================

6.1.
- Definirajte instancu 'Eq' za tip 'MyList a' tako da dvije liste budu
  identične ako imaju isti prvi element.

6.2.
- Definirajte instancu 'Eq' za tip 'Tree a' tako da dva stabla budu identična
  ako u čvorovima imaju pohranjene identične elemente, neovisno o redoslijedu i
  zanemarujući duplikate.