Viikko 1 - Johdatus ja syntaksi

Johdanto

Tämän viikon harjoituksissa on tarkoitus oppia Haskellin syntaksi päällisin puolin. Lisäksi opiskelemme Haskellin tyyppijärjestelmää niin paljon, että pystymme tulkitsemaan suuren osan kääntäjän virheilmoituksista ja ennakoimaan millaisia tyyppejä lausekkeilla on.

Näissä tehtävissä esitetyt asiat löytyvät seuraavista lähteistä:

• [Learn You a Haskell for Great Good], Kappaleet 1–4 ja 7. Myös luvun 8. alku voi olla hyödyksi.
• [Real World Haskell], Kappaleet 1–3.

Hyvä strategia tehtävien suorittamiseen on lukea ensin LYAH kevyesti läpi ja tehdä tehtäviä palaten materiaaliin siinä vaiheessa kun tiedot loppuvat. Jos jokin asia jää täysin mysteeriksi, siitä pitää kysyä. Kysymykset lähetetään tiistai-aamuksi luennoijalle (ville.tirronen@jyu.fi), jolloin niihin ehditään saada kunnolliset vastaukset tiistain harjoituksissa.

Tehtävien tekemistä varten joudut noutamaan Haskell-ympäristön … Tutustu erityisesti GHCi -tulkkiin, jolla voit testata Haskell lausekkeita.

Kaikki tehtävät tulee olla tehtynä ja palautettuna torstaina kello 12. Mutta ei hätää, vaikka näitä on paljon, niin ne ovat helppoja ja niitä saa (ja tulee) tehdä porukalla!

Perussyntaksi

Tässä kappaleessa tarkastelemme, mitkä ovat Haskell-kielen yleiset rakenteet ja miten ne eroavat muiden, tutujen kielten vastaavista. Syntaksin opetteluun voidaan käyttää aluksi GHCi-tulkkia. Tulkkiin voit sekä kirjoittaa lausekkeen, esimerkiksi 1 + 1 tai siltä voit kysyä antamasi lausekkeen tyyppiä: :t 1+1. Huomaa kuitenkin, että et voi määritellä arvoja¹ tai tyyppejä tulkissa.

Tehtävä — perusrakenteet

Kokeile seuraavia rakenteita GHCi-tulkissa ja kuvaile esimerkkien kanssa mitä ne tekevät. (Kokeile siis esimerkin lisäksi myös muita vastaavia lausekkeita)

1. even 8
2. (1,'a') ja ("kissa","minttu",12)
3. [1..10]
4. [x^2 | x <- [1..20], even x]
5. case
6. if
7. let

Tehtävä — perusfunktiot

Kutsu seuraavia funktiota tulkissa. Selvitä niiden tyyppi tulkin avulla ja kerro kuinka monta parametria kullekin funktiolle on annettava.

1. (+), (-), (/), mod
   
2. (:), head, tail
3. (++)
4. (+1), (2*), (/3), (3/)
5. zip, concat, take, drop, null, length
6. fst, snd
7. sum
8. (.) (Testaa vaikkapa d-kohdan arvoilla)
9. Just, Nothing, Left, Right

Huomaa, että tuttujen + ja - operaattoreiden ympärillä on sulut. Mitä se tarkoittaa?

Tehtävä — Erilaiset funktiot?

Edellisen tehtävän viimeisessä kohdassa on kirjoitettu vakioiden nimiä isolla alkukirjaimella. Yleensähän vain tyypit kirjoitetaan isolla. Mistä on kysymys?

Tehtävä — Tietotyyppien määritteleminen

Tietotyypit poikkeavat haskellissa varsin paljon olio-ohjelmoinnin tietyypeistä. Esimerkiksi lista määritellään haskellissa näin:

> data MyList a = Cons a (MyList a)     
>               | EmptyList

Tietysti, konstruktori Cons vastaa edellisen tehtävän : operaattoria ja EmptyList merkintää []. Itse lista [1,2,3,4] on vain “syntaktista sokeria” määritelmälle 1:2:3:4:[]. Huomaa, että ylläoleva määrittely on rekursiivinen: lista voi olla Cons elementti, jossa on yksi alkio ja toinen Lista. Koska haskell käyttää laiskaa laskentaa, rekursion ei tarvitse sinänsä päättyö koskaan. Voimme määritellä äärettömiä tietorakenteita ilman huolta. Itseasiassa, varuskirjaston ja edellisten demojen lista on yksi tälläinen:

> data MyList a = Cons a (MyList a)     
>               | EmptyList

Nimeä seuraavat osat yo. määritelmästä ja selvitä mitä ne ovat

1. `MyList
2. a
3. |
4. Cons ja EmptyList

Määrittele seuraavat tietotyypit a) Kelmien kerhon kelmi, jolla on nimi ja useita harrastuksia. c) Sellainen tietotyyppi, jonka palauttaisit funktiosta, joka saattaa epäonnistua tietyissä virhetilanteissa. b) Takametsän asukas, joka saattaa olla kelmi tai possu. c) Binääripuu.

Tehtävä — Sektiot

Haskellissa operaattorista (esim. +) voi tehdä funktion ja funktiosta (esim. mod) operaattorin. Miten?

Tehtävä — if

Haskell kielessä on tuttu if rakenne:

> eval:
> if 5>7 then "Oho!" else "Fiksua!"

Haskellin if eroaa kuitenkin Javan iffistä olennaisella tavalla, miten? Miksi esimerkiksi seuraava ohjelma ei toimi:

> eval:
> if (5>7) then "Oho!" else True

Mitä voit kuitenkin tehdä Haskellin if:llä, mitä et voi tehdä Javan if:llä? (Vinkki: minne sen saa kirjoittaa?) Anna esimerkki.

Tehtävä — let ja where

Rakenteilla let ja where voidaan sitoa muuttujille arvoja.

1. Mitä olennaista eroa where ja let rakenteilla on? (Vinkki: ed. tehtävä)

Tehtävä — Pieniä funktiota

Määrittele Haskellissa seuraavat vakiot käyttäen hahmonsovitusta (Pattern Matching):

> and' :: Bool -> Bool -> Bool
> or'  :: Bool -> Bool -> Bool
> not' :: Bool -> Bool
> implication' :: Bool -> Bool
> lift' :: (a -> b) -> ([a] -> [b]) -- Vihje: mitä tämäntyyppinen yksinkertainen mutta hyödyllinen funktio mahtaisi tehdä?

Määritelmän heittomerkki tulee siitä, että Haskellin standardikirjasto toteuttaa muuten samannimisiä funktioita.

Tehtävä — Toisen asteen yhtälö

1. Määritä tyyppi funktiolle, joka ratkaisee toisen asteen yhtälön termien kertoimien perusteella ja palauttaa molemmat juuret.
2. Miten voit palauttaa useamman arvon funktiosta? (ks. tehtävä ‘perusrakenteet’)
3. Toteuta
4. Testaa funktioille x², x² + x - 5 ja x² + 2x + 4.

Tehtävä — Karkausvuosi

"Juliaanisessa kalenterissa karkausvuosi oli
poikkeuksetta joka neljäs vuosi[1], vuosiluvun ollessa jaollinen neljällä.
Gregoriaanisessa kalenterissa tästä on se poikkeus, että täydet vuosisadat (eli
sadalla jaolliset vuodet) eivät ole karkausvuosia muulloin kuin joka 400. vuosi
(eli vuosi on jaollinen 400:lla). Esimerkiksi vuodet 1700, 1800 ja 1900 eivät
olleet karkausvuosia, mutta 2000 oli." -- *Wikipedia*

Tee funktio, joka kertoo onko annettua numeroa vastaava vuosiluku karkausvuosi vai ei

1. Käyttäen if-lausekkeita
2. Käyttäen quard:eja
3. Käyttäen case-lauseketta ja quard:eja

Tehtävä — Sulutusta

Ohjelmien suluttaminen on hieman sama asia kuin tavuttaminen ala-asteella. Käsittämättömän tylsää ja turhantuntuista, mutta pakko osata, ellei sitten aio lisp-ohjelmoijaksi.

Lisää kaikki sulut mitä voit seuraaviin lausekkeisiin. Korvaa myös . ja $ operaattorit suluilla määritelmiensä ((f . g) x = f (g x) ja a $ b = a b) mukaisesti.

1. 1 + 2 + 3 + 4
2. hcat . map snd . zip [1..] $ circles a
3. (pad 1.1 . dashing [0.2,0.05] 0 . lc purple . lw 0.05 . fc blue) circle

Lisää sulut seuraaviin tyyppilausekkeisiin

1. a
2. a -> Maybe a
3. a -> a -> b
4. a -> a -> b -> Int (Joo, en keksinyt useampaa olennaista tapausta)

Poista tarpeettomat sulut seuraavista tyyppilausekkeista

1. (a -> (a -> b))
2. ((a->a) -> b)
3. (Maybe (a-> (a->b))) -> (a -> (a))

Tehtävä — Referential Transparency

Eräs poikkeuksellisen tärkeä ominaisuus Haskellissa on viite-eheys, eli Referential Transparency. Mitä sillä tarkoitetaan? (Vinkki. Kurssilla voi käyttää wikipediaa ja googlea).

Tehtävä — Käsin laskemista

Edellisen tehtävän nojalla voidaan havaita, että pöytätestaushan on kertaluokkaa helpompaa kuin Javalla tai C:llä. Tästä havainnosta innostuneena pöytätestaammekin heti pari Haskell ohjelmaa! Olkoon seuraavat määritelmät annettuja:

> doubleIt x    = 2*x
> (f . g) x     = f (g x)
> both op (a,b) = (op a, op b)
> fst (x,_)     = x 
> snd (_,x)     = x
> 
> fromMaybe a (Just x) = x
> fromMaybe a Nothing  = a

Esimerkiksi fst (both (doubleIt . doubleIt) (1,2)) sievenisi näin:

>  fst (both (doubleIt . doubleIt) (1,2))
> == {- 1. both:n määritelmä -}
>  fst ((doubleIt . doubleIt) 1, (doubleIt . doubleIt) 2)
> == {- 2. fst:n määritelmä -}
>  (doubleIt . doubleIt) 1
> == {- 3. (.) määritelmä -}
>  doubleIt (doubleIt 1)
> == {- 4. doubleIt määritelmä -}
>  2 * (doubleIt 1)
> == {- 5. doubleIt määritelmä -}
>  2 * (2 * 1)
> == {- 6. kertolasku -}
>  2 * 2
> == {- 7. kertolasku -}
>  4

1. Kohdassa 2 sievennettiin fst ennen lauseketta (doubleIt . doubleIt) 1. Miksi näin? Mitä seurauksia tälläisellä laskutavalla on?
2. Sievennä, välivaiheiden kanssa seuraavat ohjelmat.
   1. fst (both (1/) (10,0))
   2. (fst . snd . fst) ((1, (2, 3)), 4)

Tyypeistä

Tyypit ovat ehkäpä tärkein asia, mikä aloittelevan Haskell-ohjelmoijan tulee tuntea. Erityisesti siksi, että aina kun jotain menee pieleen, edessä on nippu tyyppejä, jotka kertovat mikä meni pieleen. Tyyppivirheet ovat aluksi hankalan tuntuisia ja rasittavia, mutta tämä johtuu vain siitä, että emme vielä osaa lukea niitä kunnolla. Myöhemmin tyypit ovat Haskell ohjelmoijalle suureksi avuksi!

Tehtävä - Haskell B. Curry

Haskellissa kaksi parametrinen funktio määritellään usein seuraavanlaisella tyypillä String -> Int -> String. Saman asian voisi määritellä myös tyypillä (String,Int) -> String, joka näyttää paljon tutummalle.

1. Mitä eroa näillä kahdella tyypillä on? Entä käytännössä?
2. Määrittele jokin funktiot, jotka vastaavat annettua tyyppiä.
3. Tutustu funktioihin curry ja uncurry. Niillä on kovin hankalt tyypit, mutta edellisen perusteella, mitä ne tekevät?

Tehtävä - Sanaselityksiä

1. Mitä ovat tyyppimuuttujat?
2. Mitä ovat tyyppiluokat?
3. Miten merkitään funktiotyyppi?

Tehtävä - Arvaa Tyypit

Arvaa millaiset tyypit seuraavilla funktioilla olisi Haskellissa:

> muutaMerkkijonoIsoiksiKirjaimiksi :: ?
> merkkijononPituus :: ?
> merkkijonoSanoiksi :: ?
> listanAlkioN :: ?
> listanSumma  :: ?
> kelminHarrastuksetTiedot :: ?
> mitaKerhossaHarrastetaan :: ?

Tehtävä - Tyyppiluokat 101

GHCi tulkissa voidaan tarkastella muuttujan tai lausekkeen tyyppiä komennolla :t <lauseke>. Esimerkiksi näin:

> ghci> :t (==)  

1. Mitä rajoite (Eq a) yo. lausekkeessa tarkoittaa?
2. Miten tämä näkyisi edellisen tehtävän vastauksessa?
3. Millaisia tyyppiluokkia Haskellissa on? Anna viisi esimerkkiä.

Tehtävä - Päättele tyypit

Olkoon annettu seuraavat tyypit:

> (>>=)     :: Monad m => m a -> (a -> m b) -> m b
> (.)       :: (b -> c) -> (a -> b) -> a -> c 
> getLine   :: IO String
> print     :: Show a => a -> IO ()
> reverse   :: [a] -> [a] 

Mikä on seuraavien lausekkeiden (yleisin mahdollinen) tyyppi? Älä käytä GHCi:tä.

> a = x y z               
> b = (\x -> x) 3           
> c = \x -> \y -> False      
> d = getLine >>= print 
> h = print . reverse
> g = (.) . (.) -- Tämä on ihan tarkoituksella hankala.

Ensimmäinen projekti

Kurssilla pyritään järjestämään viikottaisia miniprojekteja, joissa käytetään demotehtävien tietoja ja tuotetaan jokin pieni ohjelma tai kirjasto.

Tehtävä — Tikku-ukot

Gloss-piirroskirjasto ei liene paras Haskell piirrostyökalu, mutta se on hyvin yksinkertainen. Gloss koostuu olennaisesti seuraavista funktioista:

> animateInWindow :: String -> (Int, Int) -> (Int, Int) -> Color -> (Float -> Picture) -> IO ()
> blank     :: Picture
> polygon   :: Path -> Picture
> line      :: Path -> Picture
> circle    :: Float -> Picture
> text      :: String -> Picture
> color     :: Color -> Picture -> Picture
> translate :: Float -> Float -> Picture -> Picture
> rotate    :: Float -> Picture -> Picture
> scale     :: Float -> Float -> Picture -> Picture
> pictures  :: [Picture] -> Picture

Näistä ensimmäinen, animateInWindow tuottaa, viisi parametria saatuaa IO ()-tyyppisen arvon. Käännettäessä Haskell ohjelmia, main on nimenomaan tätä tyyppiä:

> import Graphics.Gloss
> main =  animateInWindow
>                "Ympyra"
>                (500, 650) 
>                (20,  20)
>                black
>                piirros
> 
> piirros aika = color green (circle (30*aika))

1. Piirrä tanssiva takametsän kelmi
2. Piirrä tanssiva takametsän possu
3. Piirrä 25 tanssivaa takametsän asukasta