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

PROGRAMIRANJE U HASKELLU

Ak.god. 2011/12.

LEKCIJA 11: korisnički razredi, ugrađeni tipovi podataka

v1.0

(c) 2011 Jan Šnajder

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

> import Data.Char
> import Data.Functor
> import Data.Foldable
> import Prelude hiding (foldr,foldl,foldr1)
> import qualified Data.Set as S
> import qualified Data.Map as M
> import qualified Data.Tree as T

== VLASTITI RAZREDI ==========================================================

Sjetimo se definicije tipa 'Person':

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

Dosada smo definirali vlastite tipove, tipske konstruktore i instance
razreda. Definirajmo sada neki vlastiti razred.

> class Ageing a where
>   currentAge :: a -> Int
>   maxAge     :: a -> Int
>   makeOlder  :: a -> a

Sada 'Person' možemo definirati kao instancu ovog razreda:

> instance Ageing Person where
>   currentAge  = age
>   makeOlder p = p {age = age p + 1}
>   maxAge    _ = 123

U našoj definiciji 'maxAge' ne ovisi o konkretnoj vrijednosti, nego je ista za
sve vrijednosti tipa 'Person' (tj. ista je za sve osobe).

Recimo da imamo neki drugi tip:

> data Breed = Beagle | Husky | Pekingese deriving (Eq,Ord,Show,Read)
> data Dog = Dog {
>   dogName  :: String,
>   dogBreed :: Breed,
>   dogAge   :: Int } deriving (Eq,Ord,Show,Read)

Možemo ga također učiniti instancom ovog razreda:

> instance Ageing Dog where
>   currentAge  = dogAge
>   makeOlder d = d {dogAge = dogAge d + 1}
>   maxAge d = case dogBreed d of 
>     Husky -> 29
>     _     -> 20

Sada možemo napraviti funkciju:

> veryOld :: Ageing a => a -> Bool
> veryOld x = 10 * currentAge x >= 8 * maxAge x

Ova funkcija se može primijeniti na bilo koji tip iz razreda 'Ageing'.

> toto = Dog "Toto" Beagle 16
> ines = Person "2692" "Ines" "Seni" Female 16 Nothing []
> dado = Person "2692" "Dado" "Dadić" Male 105 Nothing []

> b1 = veryOld toto
> b2 = veryOld ines
> b3 = veryOld dado

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

1.1.
- Napišite funkciju 
    compareRelativeAge :: (Ageing a, Ageing b) => a -> b -> Ordering 
  koja uspoređuje godine relativno u odnosu na maksimalne godine (tako
  da je npr. pas od 10 godina stariji od čovjeka od 20 godina).

1.2.
- Definirajte razred 'Nameable' s funkcijom
    name :: a -> String
  Zatim definirajte 'Person' i 'Dog' kao instance te klase. Za ime osobe
  vratite "Ime Prezime", a za ime psa "X the Dog".

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

Razmotrimo drugi primjer. Često se tipski razredima definira sučelje prema
nekoj općenitoj strukturi podataka. Npr. možemo definirati tipski razred za sve
tipove u koje se može umetati podatak i iz kojih se taj isti podatak može
izvaditi:

> class Pushable t where
>   push   :: a -> t a -> t a
>   peek   :: t a -> a
>   pop    :: t a -> t a

Primijetite da je razred 'Pushable' definiran za tipski konstruktor 't', koji
je vrste '* -> *', a ne za tip 't a', koji je vrste '*". To znači da, kada ćemo
u nastavku definirati instance, nećemo pisati tipsku varijablu uz taj
konstruktor, jer to onda ne bi više bila vrsta '* -> *', nego vrsta '*' (tj.
običan tip).

Npr. instanca za listu:

> instance Pushable [] where
>   push x xs   = x:xs
>   peek (x:_)  = x
>   peek []     = error "Empty list"
>   pop (_:xs)  = xs

(Napomena: tipski konstruktor za listu je '[]' i njegova je vrsta, očekivano,
'* -> *'. To znači da lista cijelih brojeva ima tip '[] Int', stringovi imaju
tip '[] Char', polimorfna lista ima tip '[] a' itd. Notacija '[a]' je zapravo
sintaksni šećer za '[] a', koja je osnovna notacija i konzistentna s notacijom
za sve druge tipske konstruktore.)

Ili naša lista 'MyList':

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

> instance Pushable MyList where
>   push x xs          = x `Cons` xs
>   peek (x `Cons` _)  = x
>   peek Empty         = error "Empty MyList"
>   pop  (_ `Cons` xs) = xs

Ili naše stablo:

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

> instance Pushable Tree where
>   push x t          = Node x t Null
>   pop  (Node _ t _) = t
>   peek (Node x _ _) = x
>   peek Null         = error "Empty Tree"

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

2.1.
- Definirajte razred 'Takeable' s funkcijom 
    takeSome :: Int -> t a -> [a]
- Definirajte '[]' i 'Tree' kao instance od 'Takeable'. Kod stabla elemente
  uzimajte u inorder-poretku.

2.2.
- Definirajte razred 'Headed' s funkcijama
    headOf  :: t a -> a      -- uzima glavu strukture
    headOff :: t a -> t a    -- uklanja glavu strukture i vraća ostatak
- Definirajte '[]', 'Tree' i 'Maybe' kao instance tog razreda. 
  (Glava podatka tipa 'Maybe' je ono što je zapakirano unutar 'Just', a rep 
  je "Nothing")

== FUNCTOR ===================================================================

Neke operacije nad strukturama općenitim strukturama podataka toliko su česte
da ima smisla za njih definirati posebne tipske razrede.

Npr. operacija mapiranja. Za listu imamo:

  map :: (a -> b) -> [a] -> [b]
  map _ []     = []
  map f (x:xs) = f x : map f xs

Slično možemo definirati i za stablo:

> treeMap :: (a -> b) -> Tree a -> Tree b
> treeMap _ Null         = Null
> treeMap f (Node x l r) = Node (f x) (treeMap f l) (treeMap f r)

A također i za 'Maybe':

> maybeMap :: (a -> b) -> Maybe a -> Maybe b
> maybeMap _ Nothing  = Nothing
> maybeMap f (Just x) = Just $ f x

Ova operacija apstrahirana je u razredu 'Functor' u modulu 'Data.Functor':

  class Functor f where
    fmap :: (a -> b) -> f a -> f b

Dakle, instance ovog razreda su svi tipovi po kojima se može "mapirati", a to
mogu biti svi tipovi koji služe kao "kontejneri". Funkcija 'fmap' je poopćenje
funkcije 'map', koja je inače definirana samo za liste.

  instance Functor [] where
    fmap = map

  instance Functor Maybe where
     fmap f (Just x) = Just $ f x
     fmap _ Nothing  = Nothing

> instance Functor Tree where
>   fmap _ Null         = Null
>   fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)

Napomena: kada radimo s listama, svejedno je pišemo li 'fmap' ili 'map', ali
ovo drugo je ipak češće.

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

3.1. 
- Napišite pomoću 'fmap' funkciju 'mapOnTreeMaybe' koja će primijeniti 
  funkciju 'f' na svaki element stabla 'Tree (Maybe a)'. Npr.
    tr = Node (Just 1) (Node (Just 2) Null Null) (Node Nothing Null Null)
    mapOnTreeMaybe (+1) tr =>
    Node (Just 2) (Node (Just 3) Null Null) (Node Nothing Null Null)
  
3.2.
- Definirajte tip 'RoseTree' za stablo kod kojeg svaki čvor može imati više
  podstabala (šumu). Za podatkovne konstruktor koristite 'RoseTree' i
  'RoseEmpty'.
- Definirajte instancu tog tipa za razred 'Functor'. 

== FOLDABLE ==================================================================

Drugi koristan razred je 'Foldable'. To je razred za tipove koji se mogu
presavijati. Definicija razreda je iz 'Data.Foldable' (malo pojednostavljena):

  class Foldable t where
    foldr  :: (a -> b -> b) -> b -> t a -> b
    foldl  :: (a -> b -> a) -> a -> t b -> a
    foldr1 :: (a -> a -> a) -> t a -> a
    foldl1 :: (a -> a -> a) -> t a -> a

Najmanja potpuna definicija je 'foldr'. Za listu znamo kako je definirana:

  instance Foldable [] where
    foldr f z []     = z 
    foldr f z (x:xs) = f x (foldr f z xs) 

Za naše stablo tipična bi definicija bila:

> instance Foldable Tree where
>   foldr f z Null         = z
>   foldr f z (Node x l r) = f x (foldr f (foldr f z r) l)

'foldr' mora biti napisan tako da funkcija 'f' kao prvi argument uzima trenutni
element stabla, a kao drugi argument akumulator. Treba se pobrinuti da se
rekurzivno obiđu sve grane. Zato nam trebaju dva rekurzivna 'foldr' poziva
(jedan za lijevu i jedan za desnu granu). Svaki od ta dva rekurzivna poziva
vraćaju novu vrijednost akumulatora.

Kad bismo imali stablo s tri grane:

> data Tree3 a = Null3 | Node3 a (Tree3 a) (Tree3 a) (Tree3 a) 
>   deriving (Show,Eq)

> instance Foldable Tree3 where
>   foldr f z Null3           = z
>   foldr f z (Node3 x l m r) = f x (foldr f (foldr f (foldr f z r) m) l)

(Kako bi 'foldr' izgledao za "rose tree"? Pokušajte poopćiti gornji slučaj.)

Isprobajmo kako to radi:

> intTree = Node 1 (Node 2 Null Null) (Node 3 Null Null)

> intTree3 = Node3 5 
>   (Node3 6 Null3 Null3 Null3) 
>   (Node3 7 Null3 Null3 Null3) 
>   (Node3 8 Null3 Null3 Null3)

> r1 = foldr (+) 0 intTree
> r2 = foldr (+) 0 intTree3

Bilo koju strukturu koja je 'Foldable' Pomoću 'foldr' lako možemo pretvoriti u
običnu listu:

  toList :: Foldable t => t a -> [a]
  toList = foldr (:) []

Zapravo, na svaku instancu razreda 'Foldable' možemo primijeniti sljedeće
funkcije iz 'Data.Foldable':

  concat :: Foldable t => t [a] -> [a]
  concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
  and :: Foldable t => t Bool -> Bool
  or :: Foldable t => t Bool -> Bool
  any :: Foldable t => (a -> Bool) -> t a -> Bool
  all :: Foldable t => (a -> Bool) -> t a -> Bool
  sum :: (Foldable t, Num a) => t a -> a
  product :: (Foldable t, Num a) => t a -> a
  maximum :: (Foldable t, Ord a) => t a -> a
  maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
  minimum :: (Foldable t, Ord a) => t a -> a
  minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
  elem :: (Foldable t, Eq a) => a -> t a -> Bool
  notElem :: (Foldable t, Eq a) => a -> t a -> Bool
  find :: Foldable t => (a -> Bool) -> t a -> Maybe a

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

4.1.
- Pomoću 'foldr' iz razreda 'Foldable' definirajte funkciju
    sumPositive :: (Foldable t, Num a) => t a -> Int
  koja zbraja pozitivne elemente u strukturi 't a'.

4.2.
- Pomoću 'foldr' definirajte funkciju 'size' koja će
  vraćati veličinu bilo koje strukture čiji je tip u razredu 'Foldable':
    size :: Foldable t => t a -> Int
    size intTree   => 3
    size [1,5..99] => 25
    size (Just 5)  => 1

4.3.
- Napišite funkciju koja provjerava jesu li svi elementi strukture 't a'
  svi jednaki.  
    eqElems :: (Foldable t, Eq a) => t a -> Bool

4.4.
- Napišite instancu razreda 'Foldable' za 'RoseTree'.

=== UGRAĐENE PODATKOVNE STRUKTURE ============================================

U Haskellovoj standardnoj biblioteci, u modulu 'Data', definirane su mnoge
korisne podatkovne strukture i operacije nad njima.

http://www.haskell.org/ghc/docs/latest/html/libraries/

=== Data.Set ===

  data Set a = ...

Struktura za skupove (redoslijed elemenata je nebitan i nema višestrukih
elemenata), implementirana kao uravnoteženo binarno stablo. 

Glavne funkcije:

  empty :: Set a
  insert :: Ord a => a -> Set a -> Set a
  delete :: Ord a => a -> Set a -> Set a
  
  elems :: Set a -> [a]
  toList :: Set a -> [a]
  fromList :: Ord a => [a] -> Set a

  union :: Ord a => Set a -> Set a -> Set a
  difference :: Ord a => Set a -> Set a -> Set a
  intersection :: Ord a => Set a -> Set a -> Set a

  map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
  filter :: Ord a => (a -> Bool) -> Set a -> Set a
  fold :: (a -> b -> b) -> b -> Set a -> b

  null :: Set a -> Bool
  size :: Set a -> Int
  member :: Ord a => a -> Set a -> Bool
  isSubsetOf :: Ord a => Set a -> Set a -> Bool

Primijetite da većina funkcija ima ograničenje 'Ord a' jer je ova struktura
interno implementirana kao uravnoteženo stablo pa je potrebno raditi usporedbe
elemenata pri umetanju i obilasku strukture.

Npr. 

> s1 = S.fromList [2,1,1,2,5,6,5]
> s2 = S.insert 100 s1
> s3 = S.insert 1 s2
> s4 = s3 `S.difference` s1

Umetanje elemenata iz liste us tablo i zatim vraćanje u listu je ekvivalentno
kao kompozicija 'sort . nub', ali bez ograničenja 'Eq a':

> xs = S.toList $ S.fromList [2,1,1,2,5,6,5]

Ako radimo sa skupovima cijelih brojeva, preporuča se koristiti 'Data.IntSet'.

=== Data.Map ===

  data Map k a = ...

Struktura riječnika (pohranjuje parove ključ-vrijednost), također
implementirana kao uravnoteženo binarno stablo. Varijabla 'k' je tip ključa, a
'a' je tip pohranjene vrijednosti. Npr. 'Map Int String' je mapa stringova s
cjelobrojnim ključevima.

Glavne funkcije:

  lookup :: Ord k => k -> Map k a -> Maybe a
  insert :: Ord k => k -> a -> Map k a -> Map k a
  insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
  delete :: Ord k => k -> Map k a -> Map k a
  adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a
  toList :: Map k a -> [(k, a)]
  fromList :: Ord k => [(k, a)] -> Map k a

'Data.Map' ima definirane instance 'Functor' i 'Foldable' (dakle možemo
mapirati i presavijati).

Npr.

> m1 = M.fromList [("342",ines),("231",dado)]
> Just p1 = M.lookup "231" m1
> m2 = M.fromList [(1,["haskell","python"]),(5,["java"]),(8,["c#","c++"])]
> m3 = M.insertWith (++) 9 ["ocaml"] m2
> m4 = M.insertWith (++) 5 ["scala"] m3
> m5 = M.map (map $ map toUpper) m4

Ako radimo s cjelobrojnim ključevima, preporuča se koristiti 'Data.IntMap'.

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

5.1.
- Definirajte funkciju za prebacivanje podataka iz bilo koje 'Foldable'
  strukture u strukturu 'Set'.
    toSet :: (Foldable t, Ord a) => t -> t a -> S.Set a

5.2.
- Definirajte funkciju 'indexWords' koja indeksira pozicije riječi u tekstu i
  vraća indeks (mapu). Ključevi mape su pojedine riječi, a vrijednosti su liste
  indekasa (pozicija na kojima se dotična riječ pojavljuje).
    indexWords :: String -> M.Map String [Int]
    indexWords "to be or not to be" => 
    fromList [("be",[1,5]),("not",[3]),("or",[2]),("to",[0,4])]
  (Uputa: treba koristiti 'insertWith'.)