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

PROGRAMIRANJE U HASKELLU

Ak.god. 2011/12.

LEKCIJA 4: tipovi, polimorfni tipovi i tipski razredi

v1.0

(c) 2011 Jan Šnajder

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

> import Data.Char
> import Data.List

=== TIPOVI ===================================================================

Svaki izraz u Haskellu ima tip. Tip izraza u principu se može odrediti
automatski pomoću mehanizma zaključivanja o tipovima (type inference).

Naredba ':type' (skraćeno ':t') i operator '::'.

Tipovi za brojeve, stringove, liste, n-torke...

Funkcije također imaju tipove. Npr. lines, chr, ord, toUpper, and, or.

Dobra je praksa uvijek pisati tip funkcije (tipsku signaturu) iznad definicije
funkcije (i to prije nego što se krene pisati definicija funkcije).

> addPairs :: [(Int,Int)] -> [Int]
> addPairs xs = [x+y | (x,y) <- xs]

> lowerCase :: [Char] -> [Char]
> lowerCase s = [toLower c | c <- s]

'Char' je istoznačan sa 'String'. Npr.:

> onlyAlpha :: [Char] -> [Char]
> onlyAlpha s = [c | c <- s, isAlpha c]

Zašto pisati signature prije definicija, kad ih Haskell ionako može sam izvesti? 

Barem su tri razloga:
* To je vrsta dokumentacije.
* Signature nam pomažu da razjasnimo (sami sebi) što bi zapravo funkcija
  trebala raditi, prije nego što je uopće definiramo.
* Signature nam omogućavaju da otkrijemo tipske pogreške: ako
  se definicija ne podudara sa signaturom, kompajler će nam to javiti.

Standardni tipovi: Int, Integer, Char, Float, Double, Bool.

> factorial :: Int -> Int  
> factorial n = product [1..n] 

> circumference :: Float -> Float  
> circumference r = 2 * pi * r 

> circumference' :: Double -> Double  
> circumference' r = 2 * pi * r 

Što je s funkcijama s više argumenata?

> number :: Int -> Int -> Int
> number x y = x*10 + y

> concatThree :: String -> String -> String -> String
> concatThree s1 s2 s3 = s1 ++ s2 ++ s3

> trimBy :: Int -> String -> String
> trimBy n xs = reverse $ drop n $ reverse $ drop n xs

Ovakav oblik pisanja funkcije od više varijabli zove se CURRYJEV oblik funkcija
(currying).

Ako funkcija uzima više argumenta, možemo ih objediniti u n-torku, npr.:

> concatThree' :: (String,String,String) -> String
> concatThree' (s1,s2,s3) = s1 ++ s2 ++ s3

ali pravi Haskellaši to nikada ne rade. :-)

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

Bez uporabe narebe ':t' odredite tipove sljedećih funkcija:

> foo10 w = [x ++ y | x <- lines w, y <- lines w]
> foo11 w = [(x,y) | x <- lines w, y <- lines w]
> foo12 w = [y : x | x <- lines w, y <- w]
> foo13 w = [(y : x,w) | x <- lines w, y <- w]
> foo14 w = [(x, x=='a') | x <- w ]
> foo15 s = tail [ c | c <- s, isLower c ]
> foo16 s = zip [ c | c <- s, isLower c ] "Haskell"
> foo17 n c = reverse $ drop n $ c : "Haskell" 
> foo18 xs = last $ words xs
> foo19 x z = x : 'y' : z

=== POLIMORFNI TIPOVI ========================================================

Tipovi mogu biti polimorfni (višeoblični), tj. mogu biti općeniti i po potrebi
se prilagođavati konkretnijem tipu.

Polimorfne funkcije: head, last, tail, fst, length, take, drop, concat, (++), 

Varijable 'a', 'b',... (malim slovima pisane varijable) zovu se TIPSKE VARIJABLE.

> listifySnd :: (a,b) -> [b]
> listifySnd p = [snd p]

Funkcije mogu biti manje ili više polimorfne, tj. manje ili više općenite. Npr.

> myConcat :: [a] -> [a] -> [a]
> myConcat s1 s2 = s1 ++ s2

ali:

> myConcat' :: String -> String -> String
> myConcat' s1 s2 = s1 ++ " " ++ s2

Još jedan primjer općenite funkcije:

> swap1 :: (a,b) -> (b,a)
> swap1 p = (snd p,fst p)

Evo tri primjera specifičnijih verzija ove funkcije (definicija je uvijek ista,
samo je tip drugačiji):

> swap2 :: (a,Int) -> (Int,a)
> swap2 p = (snd p,fst p)

> swap3 :: (a,a) -> (a,a)
> swap3 p = (snd p,fst p)

> swap4 :: (Int,Int) -> (Int,Int)
> swap4 p = (snd p,fst p)

Ove su funkcije (bez nekog posebnog razloga) specifičnije nego što bi zapravo
mogle biti. Međutim, dobra je praksa uvijek pisati što općenitije funkcije i
definirati što općenitiji tip funkcije. Naredba ":t" nalazi upravo
najopćenitiji tip.

Tipski mehanizam Haskella pronaći će sve tipske greške već kod kompajliranja.

bogus1 x = 2 + "abc"

bogus2 x = if x==5 then 1 else "greška"

bogus3 x y = x ++ ' ' ++ y

bogus4 x = tail x ++ head x

Primjer tipske pogreške:

bogus5 :: Int -> Char -> [String]
bogus5 c n = take n [c,c..]

Kojeg je tipa funkcija 'error' ?

Često se događa da nam treba neka standardna funkcija, ali ne znamo kako se
zove. Ako znamo što bi funkcija trebala raditi, možemo naslutiti njezin
tip. Tada za pretraživanje možemo koristiti Hoogle (approximate type signature
Haskell API search engine):

http://www.haskell.org/hoogle/

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

Bez uporabe narebe ':t' odredite tipove sljedećih funkcija:

> foo20 xs = tail xs ++ [head xs]
> foo21 xs = (head xs,tail xs)
> foo22 x xs = x:xs
> foo23 l = init $ tail l
> foo24 xss ys = concat xss ++ ys
> foo25 xss ys = (head $ concat xss,head ys)
> foo26 xs = head $ concat $ concat xs
> foo27 cs = [[c1,c2] | c1 <- cs, c2 <- cs]
> foo28 cs = [ concat [c1,c2] | c1 <- cs, c2 <- cs]
> foo29 cs = concat [[c1,c2] | c1 <- cs, c2 <- cs]

=== TIPSKI RAZREDI ===========================================================

Prvo i osnovno: tipski razred nema veze s razredima u OOP!

Tipski razred je "sučelje" koje definira neko ponašanje tipa.

Ako tip 'a' pripada tipskom razredu, onda znači da tip 'a' podržava operacije
koje definira taj razred.

Tipske definicije mogu imati OGRANIČENJA RAZREDA (class constraints), za što se
koristi znak (=>).

Npr. definicija funkcije 'elem' ili operatora (==).

Ograničenja razreda tipično nalazimo kod polimorfnih funkcija. Funkcija je
dakle polimorfna (općenita), ali tip s kojim barata ipak mora podržavati neke
operacije.

Osnovni tipski razredi: Eq, Ord, Show, Read, Enum, Bounded, Num, Integral,
Floating.

'Eq' je tipski razred za tipove koji podržavaju provjeru jednakosti tj.
operatore (==) i (/=). Većina tipova je u ovom razredu, tj. za većinu tipova
možemo provjeravati jesu li jednaki. Nažalost, tip "funkcija" nije u ovom
razredu. To znači da ne možemo provjeravati jesu li dvije funkcije jednake.
(Zašto je to tako?)

1 == 1
(1,2) == (1,2)
[1,2,3] == [3,2,1,0]

Ali ovo nije dobro:

(1,2) /= (1,2,3)

budući da je riječ o različitim tipovima, a operatori (==) i (/=) rade
usporedbu nad dvama dvrijednostima istog tipa!

'Ord' je tipski razred za tipove koji podržavaju usporedbu, tj. operatore (>),
(>=), (<), (<=) i funkciju 'compare'. 

1 < 2
"voda" <= "vatra"
(1,2) < (2,1)
compare 1 2
compare "voda" "vatra"

(Što mislite, koja je veza između razreda 'Eq' i 'Ord'?)

'Show' je tipski razred za tipove koji se mogu prikazati kao string. Svi takvi
tipovi imaju podržanu funkciju 'show':

show :: Show a => a -> String

show 2.3
show [1,2,3]
show (1,2)

'Read' je tipski razred za tipove koji se mogu učitati iz stringa. Svi takvi
tipovi imaju definiranu funkciju 'read':

read :: Read a => String -> a

Npr.:

read "True" || False
read "3.14" + 5.0
read "[1,2,3]" ++ [4]
read "(1,2)" : [(2,2)]

Međutim, zbog polimorfizma, nekad nije moguće automatski odrediti tip ako ne
postoji kontekst:

read "4"
read "True"
read "[1,2,3]"

Treba ili postojati kontekst, kao u gornjim primjerima, npr:

[read "True",True,False]

ili treba eksplicitno napisati koji je tražen tip:

read "4" :: Int
read "4" Float
read "True" :: Bool
read "[1,2,3]" :: [Double]
read "[1,2,3]" :: [Int]

'Enum' je tipski razred za prebrojive tipove (tipove s definiranim uređajem).
Npr. takvi tipovi su Bool, Char, Int, Integer, Float, Double. Tipovi imaju
definirane funkcije 'succ' i 'pred' te mogu generirati liste sa zadanim
rasponom.

succ 'a'
succ '1'
['a'..'z']
['1'..'2']

succ 1.5
[1.5..5.5]

Ali nije definirano:

succ (1,2)
succ [1]

'Bounded' je tipski razred za tipove koji imaju gornju i donju ogradu.

maxBound :: Int
minBound :: Int

maxBound :: Char
minBound :: Char

Tipovi Double, Float, Integer, String... nemaju ograda.

Vrijednosti 'maxBound' i 'minBound' nisu funkcije nego su zapravo polimorfne
konstante tipa '(Bounded a) => a'.

'Num' je tipski razred za brojeve.

:t 100

Cijeli brojevi su polimorfne konstante. Mogu poprimiti tip prema potrebi
(ovisno o kontekstu ili ovisno o tome što zatražimo):

100 :: Int
100 :: Integer
100 :: Float
100 :: Double

Npr. funkcija 'sum'.

'Fractional' je tipski razred za razlomke koji podržava operator (/).

'Floating' je tipski razred za realne brojeve (razlomci + trigonometrijske
operacije, logaritamska i eksponencijalna funkcija).

'Integral' je tipski razred za cijele brojeve.

Npr. funkcije 'odd' i 'even'.

Pretvorba tipa 'Integra' u viši tip 'Num':

fromIntegral :: (Num b, Integral a) => a -> b

fromIntegral (length [1,2,3]) / 2

Više o numeričkim tipovima: http://www.haskell.org/tutorial/numbers.html

Očito, između klasa postoji nasljeđivanje.

Dijagrami:
- http://www.haskell.org/onlinereport/classes.gif
- http://lh4.ggpht.com/_PiUWFeprZSw/Sd72lQjUr3I/AAAAAAAAKfA/4PLE8uFQqUk/hs-nums.png

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

Bez uporabe narebe ':t' odredite tipove sljedećih funkcija:

> foo30 x ys = if x==head ys then x else last ys
> foo31 x ys = if x<head ys then x else last ys
> foo32 xs yss = if xs==head yss then (head xs) else last xs
> foo33 x ys = if x then zip [1..9] ys else []
> foo34 w = zip [0..] (lines w)
> foo35 x y = if odd x then y else x / 10
> foo36 xs = sort xs == xs
> foo37 x xs = show x ++ (show $ concat xs)
> foo38 xs = sum $ concat xs
> foo39 xs yss = sum $ [min x y | x <- xs, ys <- yss, y <- ys]