Viikko 4 - Tyyppiluokat, Monadit ja IO

Johdanto

* HUOM! Tällä kertaa tehtäviä on paljon. Ne on kuitenkin pyritty tekemään algoritmisesti helpoiksi. Jos tuntuu, että näitä on liikaa yhdelle viikolle, niin jatketaan seuraavalla viimeiset.*

* HUOM! Nämä demot ovat pahemmin rikki kuin männävuoden lada. Kannattaa siis katsoa onko jo tullut korjauksia tehtäviin tai kysyä, jos jokin asia näyttää ylettömän hankalalle: kyseessä ei ole kompa, vaan bugi tehtävän annossa.*

Olemme käsitelleet aiemmin miten funktiot toimivat arvoina, millaisia ovat algebralliset tietotyypit (Rock, AsteroidWorld, [x]), mikä on rekursio ja miten toimivat perusfunktionaalit kuten foldr/l ja map. Tässä vaiheessa voit taputtaa itseäsi, tai muita ryhmäläisiä (kysy lupa ensin!), selkään, sillä osaat nyt funktio-ohjelmoida!

Seuraavaksi kertaamme hieman tietotyyppejä, käsittelemme elämää helpottavia asioita, kuten tyyppiluokkia ja sitä, millaisia rakenteita oppimistamme funktioista ja tietotyypeistä kannattaa koostaa. Kuten tehtävistä havaitaan, mitään rakennetta ei tutkita vielä kovin syvällisesti. Riittää että tiedät, että ne ovat olemassa, joten voit yrittää käyttää niitä tulevissa harjoituksissa.

Tyyppejä

Olemme aiemmin määritelleet algebrallisia tietotyyppejä, mutta emme tietorakenteita. Tehdään kokeeksi yksi sellainen.

Binääripuu

Määrittele tietotyyppi binääriselle hakupuulle
Määrittele tyhjä puu
Määrittele funktio insert :: (Ord key) => key -> value -> BinaryTree key value -> BinaryTree key value
Määrittele funktio lookup :: (Ord key) => key -> BinaryTree key value -> Maybe value
Määrittele funktio fromList :: (Ord key) => [(key,value)] -> BinaryTree key value
(Tähti, tee jos ehdit) Määrittele funktio delete :: (Ord key) => key -> BinaryTree key value -> BinaryTree key value
Muuta edellisten demojen kuningasperhe-tehtävän listat binääripuiksi.

Tyyppiluokkia

Tutustu Learn you a Haskellin lukuun 8 ja selvitä itsellesi, mitä ovat tyyppiluokat.

Grafiikkaa

Luo tyyppiluokka Graphical, johon kuuluvat tyypit voidaan visualisoida Gloss-kirjastoa käyttäen.
Luo Graphical instanssit tyypeille Int, Char ja Double.
Luo Graphical instanssit tyypeille Graphical a => Graphical (Maybe a), Graphical a => Graphical [a]
Miksi tässä tehtävässä vaaditaan tyyppiluokan käyttöä? Millainen vastauksestasi tulisi, jos et käyttäisi tyyppiluokkaa? (Vinkki, kuinka monelle tyypille olet nyt toteuttanut graafisen piirtämisen?)
(Tähtitehtävä, eli tee jos huvittaa) Määritä instanssi (Graphical key, Graphical value) => Graphical (BinaryTree key value)

Funktoreita

Funktio map on varsin hyödyllinen kapistus listojen käsittelyssä. Samanlainen olisi varmastikin hyödyllinen binääripuille ja monille muille tietotyypeille. Esimerkiksi, jos haluaisimme muuttaa englannin kuningasperheen isien listan sisältämään vain isän ensimmäisen nimen, niin tekisimme sen varmaan karkeasti näin:

etunimi :: Name -> Name 
etunimi = head . words

etunimet = map (second etunimi) fathers
 where second f (a,b) = (a,f b)

Mutta kun edellisessä tehtävässä vaihdoimme tietorakenteemme listasta puuksi, tämäpä ei käykkään näin helposti. Lisäksi, haluamme varmaan tulevaisuudessa vaihtaa ennenpitkää naiivin binääripuumme vielä parempaan rakenteeseen, kuten trieen, joten olisi hyvä, jos emme joutuisi kirjoittamaan kaikkia tietorakenteenkäsittelyfunktioitamme uudestaan.

Määrittele funktio mapTree :: (value -> newValue) -> BinaryTree key value -> BinaryTree key newValue,
Lue mitä Funktorit ovat Learn You a Haskellista. (Vastaukseksi kirjoita ylös, tai nauhoita, kun selität sen kaverille)
Kirjoita Functor -tyyppiluokan instanssi tyypille BinaryTree key
Kirjoita Functor -instanssi Maybe tyypille.
Kirjoita Functor -instanssi Listoille
Toteuta funktio etunimet, joka toimii sekä listalla , että binääripuulla. Mitä funktiosi tekee Maybe Nimi -tyypille? (Huom: Luennoijan ajattelemattomuus: Joudut käyttämään listan sijaan newtype PariLista a b = PL [(a,b)] - kuorta listatyypin ympärillä, jotta ghc hyväksyy sopivan funktorimääritelmän. )

Funktoreiden pitää totella seuraavia lainalaisuuksia

fmap id = id                      -- Functor (1)
fmap (g . h) = fmap g . fmap h    -- Functor (2)

Miksi tämä olennaista?

(Tähti, eli tee jos ehdit) Osoita yo. lainalaisuudet oikeiksi.

* HUOM! Koska historiallisista syistä tyyppiluokkien instansseja ei saa piilotettua haskellissa, käytä Functorin sijaan seuraavia määritelmiä:*

class MyFunctor f where
  myfmap :: (a -> b) -> f a -> f b 

(<$>) = myfmap

Applikatiivisia Funktoreita

Edellisissä harjoituksissa tarkastelimme hyödyllistä bind-rakennetta:

grandfathersMother = bind2 mother . bind2 father . father

Tällä tavalla saimme kätevästi yhdistettyä ‘’monimutkaisia’’, yksiparametrisia funktioita. Kuitenkin joskus haluaisimme käyttää luonnollisesti kaksiparametrisia funktioita:

hasSameMother a b = mother a == mother b -- Ei toimi taaskaan

Funktion bind1 kanssa pohdittiin miten parametrit saadaan yhteensopivaksi (.)-operaattorin kanssa. Applikatiivisten funktoreiden kanssa mietitään, miten ($)-operaattoria voisi jatkaa siten, että edellisen voisi kirjoittaa näin:

hasSameMother a b = onSama <$> mother a <*> mother b 
 where onSama a b = a == b

Ota selvää Learn You a Haskellista, mitä applikatiiviset funktorit ovat. (Vastaukseksi kirjoita ylös, tai nauhoita, kun selität sen kaverille)
Määrittele Applicative-instanssi Maybe-tyypille, niin että yo. koodi toimii.

* HUOM! Koska historiallisista syistä tyyppiluokkien instansseja ei saa piilotettua haskellissa, käytä seuraavaa määritelmää Applicative-modulin sijasta:*

class MyFunctor f => MyApplicative f where
        pure  :: a -> f a
        (<*>) :: f (a -> b) -> f a -> f b

Yhdistetyt funktiot, jatkoa

Nyt tutustumme tietotekniikan historian pahimmin väärin nimettyyn asiaan, eli Monadeihin. Monadit eivät ole juuri monimutkaisempi asia, kun funktorit tai applikatiiviset funktoritkaan, mutta terminologiaa on enemmän. Samalla havaitsemme, ohimennen, miten IO toimii Haskellissa.

Sopivat esitiedot läydät Learn You a Haskellin kappaleesta [12]. Lisäksi voit lukea Dan Piponin erinomaisen monaditutoriaalin.

Edellisissä demoissa keksimme erilaisia bind operaattoreita, joilla on kätevä sovittaa yhteen muuten yhteensopimattomia funktioita, kuten esimerkiksi logittavia funktioita:

bind1 :: (a -> (b, String))
         ->
         ((a, String) -> (b, String))

Tämän tyyliset operaattorit toimivat mainiosti yhteen Functor-tyyppiluokan ja fmap funktion kanssa! Sitä varten joudumme kuitenkin nimeämään tyyppimme uudelleen, että saamme Functor instanssin määriteltyä kivuttomasti:

newtype Loggable a = Log (a,String)

Määrittele bindLoggable :: (a -> Loggable b) -> (Loggable a -> Loggable b) edellisten demojen mukaisesti. Määrittele uudelleen myös foo, bar ja yhd funktiot.
Määrittele funktio unitLoggable, siten, että
```
fmap f = bindLoggable (unitLoggable . f)
```
on kelvollinen funktorin määritelmä. * HUOM. Tämä tehtävä on korjattu tiistaina. Edellisessä versiossa oli aivo-typo*

Osoita, että

bindLoggable unitLoggable . f == bindLoggable f . unitLoggable == f

pätee kaikille f.

(Tähti) Mitä fmap tarkoittaa Loggable tyypille? Mihin sitä voisi käyttää?
(Tähti) Mitä c-kohdan väite merkitsee?

Listat (Tähti, eli tee, jos ehdit)

Joskus meillä on funktioita, jotka saattavat palauttaa useamman arvon. Esimerkiksi edellisten tehtävien kuningasperhettä käsittelevässä tehtävässä funktio, joka hakee jonkun henkilön vanhemmat on sellainen: kaikkien vanhempia ei ole tietokannassa, joten vastaus saattaa olla kaksi nimeä, yksi nimi tai ei yhtään nimeä. Voimme käyttää jälleen bind/unit ideaamme, ja kirjoittaa koodin näin:

parents :: Name -> [Name]

grandparents :: Name -> [Name]
grandparents = bindList parents . parents

unitList x = [x]
bindList f xs = concatMap f xs

Toteuta funktio parents. (Siinä ei tarvitse kombinaattoreita)
Mitkä ovat bindList ja unitList funktioiden tyypit? Mitä ne tekevät?
Toteuta funktio ancestors, joka palauttaa kaikki esi-isät. Käytä bindList funktiota.

Abstraktio

Edellisten tehtävien nojalla huomaamme, että meillä on koko joukko bind* ja unit* operaatioita, jotka tekevät loogisesti saman asian eri tyypeille, kuten Loggable a, [a] tai Maybe a. Annetaanpa näille nimet, niin erottuvat toisistaan:

Nyt voimme viimein selvittää mikä on monadi. Se on kolmikko (m,bind,unit), missä m on joku tyyppi, ja bind ja unit sille edellä määritellyt operaatiot, jotka toteuttavat seuraavat lainalaisuudet

bind f . unit == bind unit . f == f    -- (1)
bind (fmap f) . fmap g == fmap (f . g) -- (2)

Antamamme monadimääritelmä on hieman erilainen kuin Haskellin yleinen terminologia. Yleensä Haskellissa merkitään:

bind       = (=<<)
flip bind  = (>>=)   
bind f . g = f <=< g 
unit       = return
lift       = fmap

Mikä on tietysti olennaisesti sama kuin käyttämämme määritelmä, mutta johtaa siihen, että esimerkiksi seuraava funktio

yhd = bind1 bar . bind1 foo . foo

kirjoitetaan usein näin:

yhd x = foo x >>= foo >>= bar

tai näin:

yhd = foo >=> foo >=> bar

Koska emme halua keksiä operaattoreille uusia nimiä jokaisen monadin yhteydessä ja huomaamme, että on olemassa hyödyllisiä funktioita, jotka periaatteessa toimisivat kaikille monadeille, kuten esimerkiksi:

sequence []     = return []
sequence (x:xs) = x >>= \r -> sequence xs >>= \rest -> return (r:rest) 

mapM f = sequence . map f

joten on vain järkevää määritellä Monad tyyppiluokaksi:

class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  return :: a -> m a

Täytä seuraava instanssimääritelmä Tyypeille Loggable, Maybe ja listoille

instance Monad (??) where
  (>>=) = ?? 
  return  = ??

do-notaatio

Koska koodi, jossa esiintyy paljon (>>=) operaattoria näyttää varsin suttuiselle, niin haskellissa on erillinen do merkintätapa.

Opiskele do Learn You a Haskellin perusteella

Muuta seuraava lauseke käyttämään do notaatiota:

sequence []     = return []
sequence (x:xs) = x >>= \r -> sequence xs >>= \rest -> return (r:rest)

Poista do - notaatio seuraavasta lausekkeesta:

do
 x <- getLine
 y <- getLine 
 z <- getLine
 return $ length x < length z && length z < length y

Input / Output

Seuraavaksi valehtelen hieman.

Ongelma IO:n kanssa on se, että esimerkiksi lueRivi funktion pitäisi palauttaa aina sama vastaus. Tämä ei tietysti ole mahdollista, sillä käyttäjähän saattaa syöttää mitä tahansa. Jos luovumme siitä vaatimuksesta, että funktio on funktio, päädymme toiseen ongelmaan, eli siihen, että Haskellin laiskuuden takia emme voi sanoa, milloin rivi luettaisiin näppäimistöltä. Siispä näyttää siltä, että lueRivi funktio on mahdoton asia.

Kuitenkin, jos funktiomme olisikin tyyppiä lueRivi :: Maailman -> (String, Maailma), missä Maailma on kaikki maailmankaikkeuden syötteet, mitkä tietokoneemme voisi tietyllä hetkellä havaita (Ei hätää, Haskell on laiska, joten koko maailmankaikkeuden mallittaminen onnistuu ilman ongelmia). Tällöin, jos lueRivi-funktio palauttaa uuden Maailma arvon, sellaisen, joka kuvaa maailmankaikkueuden tilaa siinä vaiheessa kun ohjelma tulee lukemaan seuraavan syötteen, niin tämähän on ohjelmoijan kannalta ihan oikea ja aito funktio!

Lisäksi, jos jotenkin saisimme hoidettua asian niin, että samaa maailmantilaa voisi tarkastella vain kerran, ei jokaisen syötteen kohdalla tarvitsisi tallentaa kaikkien tietokoneeseen kytkettyjen IO-laitteiden tilaa, niin koko härvelihän olisi mahdollista toteuttaa ohjelmointikieleen, eikä tarvitse edes huijata kovin paljoa.

Edellä mainittu maailman tilan kapselointi onnistuu, sillä huomasimme logimonadimme kanssa, että käyttämällä sopivaa monadimääritelmää saamme kuljetettua logiviestit oikeassa järjestyksessä kaikkista sitä tarvitsevista funktioista läpi, ilman, että samaa viestiä voidaan käsitellä kahta kertaa. Sama idea toimii myös IO:n kanssa. Konseptitasolla IO määritelläänkin näin:

newtype IO a = IO (Maailma -> (a, Maailma))

Tietysti, IO:n toteuttaminen vaatii hieman tukea kääntäjältä, kuten sen, että IO funktion laskeminen joutuu tarkastelemaan syötelaitteiden tilaa.

Kirjoita nyt, neljän viikon opiskelun jälkeen, Hello world-ohjelma, joka tervehtii käyttäjää nimeltä.

Apuna voit käyttää sitä alla olevia funktioita ja tietoa, siitä että IO on monadi, funktori ja applikatiivinen funktori.

appendFile :: FilePath -> String -> IO ()
catch :: IO a -> (IOError -> IO a) -> IO a
getChar :: IO Char
getContents :: IO String
getLine :: IO String
interact :: (String -> String) -> IO ()
ioError :: IOError -> IO a
print :: Show a => a -> IO ()
putChar :: Char -> IO ()
putStr :: String -> IO ()
putStrLn :: String -> IO ()
readFile :: FilePath -> IO String
readIO :: Read a => String -> IO a
readLn :: Read a => IO a
writeFile :: FilePath -> String -> IO ()

Reflektio

Tärkeää: Tämäkin on tehtävä!

Listaa kaikki epäselväksi jääneet asiat, jotta osaat kysyä niistä demotilaisuudessa.
Käy ryhmäsi kanssa läpi kaikki tehtävät ennen torstain demopalautusta
Pohtikaa ryhmässä lyhyesti
- Mitä opit,
- mikä oli vaikeaa,
- mikä oli helppoa ja
- mistä yllätyit?
- (Vastaukset gittiin)