Viikko 8 - Applikatiivisten funktoreiden paluu.

Johdanto

Esimerkkivastaukset

* Huom* Tehtävistä saa esittää kritiikkiä. Tällä kertaa näitä on myös paljon, mutta varmaankin käytämme jälleen kaksi viikkoa näiden miettimiseen.

Yksi helpoimmin ymmärrettävä ja samalla hyvä esimerkki monadien käytöstä on merkkijonon tulkinta. Siispä leikimme jälleen olevamme rakentamassa pätevää ohjelmaa suorakaiteiden käsittelyyn. Tällä kertaa saamme kuitenkin tehtäväksemme lukea suorakaiteita koskevia lausekkeita tekstitiedostosta.

Tiedostossa voi olla joko suorakaide literaaleja, kuten <100,200-10+10> mikä tarkoittaisi suorakaidetta, jonka oikea ylänurkka on pisteessä (–10,10) ja jonka leveys on 100 ja korkeus 200 yksikköä. Lisäksi tiedostossa on laskutoimituksia, kuten esimerkiksi:

<10,10+0+0> `yhdiste` (<10,10+5+5> `leikkaus` <10,10+0+5>)
(<10,10+5+5> `leikkaus` <10,10+0+5>) `leikkaus` (<10,10+8+5> `leikkaus` <20,10+0+5>)

Lisää esimerkkejä löydät rectangles-tiedostosta

Kokeilu

Kokeile noin 15–20min luoda sopivaa funktiota, joka lukee tekstitiedoston ja palauttaa siinä määritellyt suorakulmiot.

1. Saitko tehtyä?
2. Mitä hankaluuksia esiintyi?

Lauseke-tyyppi

Määrittele sopiva tyyppi kuvaamaan lausekkeita. Käytä hyväksesi edellisten demojen tulosta. Esimerkiksi:

data Lauseke = Suorakaide (Rectangle)
	     | Yhdiste Lauseke Lauseke 
	     | Leikkaus Lauseke Lauseke

on hyvä lähtökohta.

Perustyyppi ja perusoperaatiot

Perustyyppimme on String -> Maybe (a, String), eli funktio joka ottaa merkkijonon ja yrittää lukea siitä jonkun arvon a. Jos lukeminen onnistuu palautetaan arvo ja jäljelle jäänyt merkkijono. Jos lukeminen ei onnistu, palautetaan Nothing

Määrittele

1. Tyyppi Jäsennin a = J (String -> Maybe (a,String).
2. Määrittele jäsennin merkki :: Char -> Jäsennin Char, joka lukee annetun kirjaimen tai epäonnistuu.
3. Määrittele jäsennin tyhjä :: Jäsennin (), joka lukee yhden tyhjän merkin, kuten välilyönnin tai epäonnistuu.
4. Määrittele jäsennin aakkonen :: Jäsennin Char, joka lukee yhden aakkosen tai epäonnistuu.
5. Määrittele jäsennin numeroMerkki :: Jäsennin Char, joka lukee yhden numeromerkin tai epäonnistuu.
6. Määrittele jäsennin failure :: Jäsennin (), joka epäonnistuu aina.
7. Määrittele jäsennin return :: a -> Jäsennin a, joka onnistuu aina vakioarvolla a.
8. Määrittele operaatio ajaJäsennin :: Jäsennin a -> String -> Maybe (a,String)

Funktori

Jäsentimen olisi hyvä olla funktori, sillä tällöin voisimme käyttää monia valmiita funktioita. Esimerkiksi voisimme määritellä jäsentimen, joka lukee numeron ja palauttaa sen kokonaislukuna:

numero :: Jäsennin Int
numero = fmap (read . box) numeroMerkki
box x  = [x]

1. määrittele Functor instanssi jäsentimelle
2. (tähti) Osoita, että funktoreiden lainalaisuudet pätevät määritelmillesi

Applikatiivinen Funktori

Applikatiivinen funktori olisi myös hyödyllinen määritelmä jäsentimelle, sillä jos jäsennin olisi applikatiivinen funktori, niin voisimme kirjoittaa esimerkiksi seuraavat näppärät määritelmät:

sulutettu a = merkki '(' *> a <* merkki ')' 
pari a      = (,)  <$> a <*> a
kolmikko a  = (,,) <$> a <*> a <*> a

1. Mitä operaattorit (*>) ja (<*) tekevät?
2. Määrittele Applicative-instanssi jäsentimelle.
3. (tähti) Todista, että instanssisi noudattaa applikatiivisten funktoreiden lakeja.

Vaihtoehtoinen Funktori

Tyyppiluokka Alternative laajentaa Applicative tyyppiluokkaa operaatiolla <|>, joka esittää vaihtoehtoisuutta. Jos jäsentimemme olisi Alternative voisimme kirjoittaa:

etumerkki = merkki '+' <|> merkki '-'

1. Määrittele jäsentimelle Alternative-instanssi.
2. Selvitä mitä Alternative-luokalle määritellyt funktiot some ja many tekevät, ja miten ne on oletusarvoisesti määritelty.
3. Määrittele em. funktioiden avulla jäsennin tyhjää :: Jäsennin (), joka lukee kaikki tyhjät merkit, mutta ei epäonnistu vaikka niitä ei olisikaan.
4. Määrittele em. funktioiden avulla jäsennin sana :: Jäsennin String.
5. Määrittele em. funktioiden avulla jäsennin luku :: Jäsennin Int.

Monoidi (Tähti)

Monoidi on joukko, jolla on yksikköalkio ja assosiatiivinen operaatio. Esimerkiksi kokonaisluvut, nolla ja yhteenlasku muodostavat monoidin. Myös parserit muodostavat monoidin.

1. Tutustu monoideihin tarkemmin artikkelin Haskell Monoids and their Uses perusteella.
2. Mikä olisi sopiva yksikköalkio ja operaatio, mikäli jäsentimestä haluttaisiin tehdä monoidi.
3. Määrittele jäsentimelle Monoid-instanssi.
4. Todista, että se on Monoidi.
5. Mitä tekisit monoidi-instanssillasi?

Monadi

Jäsentimet ovat varmaan myös monadeja, sillä on helppo keksiä tarve bind operaatiolle:

kaksiSamaaKirjainta = bind merkki $ aakkonen

Lisäksi, monadeilla on hyviä yleiskäyttöisiä operaatioita, kuten mapM ja replicateM, sekä niitä on helppo ketjuttaa peräkkäin (>>=) ja >> operaattoreilla.

vakioSana           = mapM_ merkki 
kolmeKirjainta      = replicateM 3 aakkonen
etumerkillinenLuku  = (plus <|> miinus) <*> numero
    where
     plus   = merkki '+' >> return id
     miinus = merkki '-' >> return negate

1. määrittele operaatio

bindJäsennin :: (a -> Jäsennin b)
		->
		(Jäsennin a -> Jäsennin b)

2. Määrittele jäsentimelle Monad-instanssi.
3. (tähti) Todista, että monadisi on monadi.

QuickCheck jäsentimelle (Tähti)

1. Määrittele Arbitrary-instanssi lauseketyypillesi.
2. Määrittele fiksu Show-instanssi lausekkeille.
3. Määrittele olennainen quickCheck-invariantti jäsentimellesi.

Jäsennin suorakaidelausekkeille

1. Tee jäsennin suorakaide :: Jäsennin Suorakaide, joka lukee yhden suorakaiteen
2. Tee jäsennin lauseke :: Jäsennin Lauseke, joka lukee suorakaiteita koskevan lausekkeen.

HUOM: Jos tähän meinaa kulua yli 100 riviä koodia, mieti uudelleen miten eo. instansseja voi hyödyntää!