Viikko 3 - Funktionaalit

Johdanto

Tällä viikolla keskitymme funktio-ohjelmoinnin toiseksi olennaisimpaan asiaan, eli funktioiden käyttöön arvoina. Edellisillä harjoituskerroilla olemme tavanneet joitain funktionaaleja, eli funktioita joiden parametrit tai paluuarvo ovat myös funktioita, mutta tällä kertaa niiden kanssa pyritään sinuiksi asti tekemällä joukko aivoja vääntäviä tehtäviä.

Perustelen termin higher-order function suomentamisen funktionaaliksi sillä, että voin laittaa demoihin kuvan naalinpoikasesta.

Tehtävät voidaan pääosin ratkaista Learn You a Haskell kirjan kappaleen 6 ja mielikuvituksen avulla.

Perusfunktionaaleja

Tarkastellaan kahta edellisen demokerran ratkaisua:

ilman _ [] = []
ilman y (x:xs) 
    | x /= y    = x : ilman xs
    | otherwise = ilman xs

parilliset [] = []
parilliset (x:xs) 
    | even x    = x : parilliset xs
    | otherwise = parilliset xs

Nämä funktiot ovat likipitäen identtisiä, joten tulee mieleen kysyä, että voisiko nämä jotenkin yhdistää? Toki voi, nostetaan testi even x ja x != y funktion parametriksi:

yleinen _ [] = []
yleinen testi (x:xs) 
    | testi x   = x : yleinen xs
    | otherwise = yleinen xs

Koska funktiokielissä funktio on arvo, samalla tavalla kuin esimerkiksi luku 2, se voidaan nimetä muuttujaksi, viedä parametrina tai tallettaa tietorakenteeseen.

Voimme kirjoittaa alkuperäiset funktiot apufunktiomme avulla näin:

ilman x xs      = yleinen (/=x) xs 
parilliset x xs = yleinen even  xs

Tämä sievenee seuraavaan muotoon:

ilman x      = yleinen (/=x) 
parilliset x = yleinen even

Mihin päädyimme? Paitsi, että jälkimmäinen ratkaisumme on paljon lyhyempi rivimäärältään, niin se on myös yksinkertaisempi lukea ja erityisesti se on turvallisempi. Turvallisuus tulee siitä, että koska rekursio on piilotettu yleinen funktion sisälle, emme voi tehdä vahingossa esimerkiksi päättymätöntä rekursiota (vrt. off-by-one virhe). Toinen hyödyllinen asia on se, että on helppo osoittaa, että funktio yleinen noudattaa tiettyjä lainalaisuuksia: Se tuottaa aina lyhyemmän tai yhtä lyhyen listan kuin parametrina annettu ja se suorittaa maksimissaan listan mitan verran testejä. Näitä lainalaisuuksia voimme käyttää ohjelmointityön tukena ja jopa erilaisten ohjelman toimintaa koskevien väittämien todistamiseen.

Lisäksi voisimme teoriassa kirjoittaa rinnakkaislaskevan tai vaikkapa näytönohjainta hyödyntävän yleinen funktion.

Myöhemmin käytämme yleinen funktiolle nimeä filter ja määrittelemme sen käyttäen if -lausekketta typografisista syistä.

Listankäsittelyä

Mitä seuraavat funktiot tekevät?

map
zipWith
filter
tail
(+)
(:)

Mitkä niistä ovat funktionaaleja? Miksi? Koosta näistä määritelmä listalle, joka sisältää kaikki fibonaccin luvut.

Katamorfismeja

Monet rekursiiviset funktiot operoivat listoilla käymällä niitä järjestelmällisesti läpi, kuten esimerkiksi:

sum (x:xs) = x + sum xs 
sum []     = 0

filter cond (x:xs) = if cond x then x:filter cond xs else filter cond xs
filter _ [] = []

Seuraavassa yritetään löytää näiden kahden funktion yhteinen tekijä laskemalla¹. Laskun strategiana on siirtää parametreiksi kaikki ne määritelmän osat, jotka liittyvät pelkästään summaamiseen ja katsoa mitä jää jäljelle². Tälläiseen laskuun kannattaa suhtautua hieman samoin kuin lausekkeen sieventämiseen matematiikassa ja tavoitteemme onkin näyttää, että Haskellin kanssa voit tuottaa ohjelmia “laskemalla”.

sum (x:xs) = x + sum xs 
sum []     = 0

== {- Siirretään + operaattori funktioksi -}

sum (x:xs) = op x (sum xs) 
 where op a b = a + b
sum []     = 0

== {- Siirretään vakio 0 where lauseeseen -}

sum (x:xs)   = op x (sum xs) 
 where op a b  = a + b
sum []       = empty
 where empty = 0

== {- Lisätään 'kuorifunktio' ja siirretään vanha sum funktio sen
      where-lauseeseen. Tämä siksi, että aiomme kohta lisätä käsitellylle funktiolle
      parametreja, mutta haluamme kuitenkin säilyttää alkuperäisen rajapinnan -}

sum xs = sum' xs
 where
  sum' (x:xs) = op x (sum' xs)
  sum'  []    = empty
  op    a b   = a + b
  empty       = 0

== {- nostetaan op ja empty sum' funktion parametreiksi. Huomaa, että edellisen
      askeleen ansiosta sum-funktion rajapinta säilyy entisenlaisena. -}

sum xs = sum' op empty xs
 where
  sum' op empty (x:xs) = op x (sum' op empty xs)
  sum' _  empty     []     = empty
  op   a  b = a + b
  empty = 0

== {- nimetään sum' uudestaan foldr:ksi ja siirretään se omaksi määritelmäkseen -}

foldr op empty (x:xs) = op x (foldr op empty xs)
foldr _  _     []     = empty

sum xs = foldr op empty xs
 where
  op    a b = a + b
  empty     = 0

== {- huomataan, että op on itseasiassa sama funktio kuin (+) -}
foldr op empty (x:xs) = op x (foldr op empty xs)
foldr _  _     []     = empty

sum xs = foldr op empty xs
 where
  op    = (+)
  empty = 0

== {- poistetaan where  -}

foldr op empty (x:xs) = op x (foldr op empty xs)
foldr _  _     []     = empty

sum xs = foldr (+) 0 xs

Lopputulos sum xs = foldr (+) 0 xs on varsin kompakti määritelmä summalle. Tämän lisäksi saimme eristettyä ohjelmasta listaa läpikäyvän osan omaksi uudelleenkäytettäväksi funktiokseen. Voisikohan sen avulla määritellä filter funktion? Lasketaanpa:

filter cond (x:xs) = if cond x then x:filter cond xs else filter cond xs
filter _ [] = []

== {- Irroitetaan ehtolauseke omaksi funktiokseen-} 

filter cond (x:xs) = op  x (filter cond xs)
  where
   op x rest = if cond x then x:rest else rest
filter _ [] = []

== {- Huomataan, että tämä on samaa muotoa kuin sum. empty on [] ja op juuri määritelty funktio -}

filter cond xs = foldr op [] xs
  where
   op x rest = if cond x then x:rest else rest

== {- Siistimmin -}

filter cond = foldr op [] 
  where
   op x rest | cond x    = x:rest
             | otherwise = rest

Eli kyllä voi. Tästä voi jo arvata, että lähdes kaikki listaa läpikäyvät funktiot voidaan määritellä foldeina. Tästä on muutama etu, sillä määritelmät ovat lyhyempiä, niille ei tarvitse antaa erillistä nimeä kuten rekursiivisten määritelmien tapauksessa ³ ja ennenkaikkea voimme olla aina varmoja, että rekursio päättyy. Emme siis voi vahingossa jumittaa koko konetta unohtamalla lopetusehtoa rekursiostamme!

Tällä hyödyllisellä foldr funktiolla on veli nimeltä foldl, jonka op ottaa parametrinsa käänteisessä järjestyksessä. Graafisesti, foldit näyttävät tältä⁴:

foldr foldl

Map, Filter, Sum

Toteuta seuraavat funktiot käyttäen foldeja ja imitoiden yo. ohjelman johtamisketjua:

map
filter
sum

Head, Last, Reverse

Toteuta käyttäen foldeja:

head
last
reverse
average, eli listan keskiarvon laskeva funktio

Missä,

head (x:xs) = x

last [x] = x
last (x:xs) = last xs

reverse = kaanna -- Ks. viikon 2 harjoitukset

Takaisinfoldaus

Määrittele funktio backfold, jolle pätee

backfold (\a b -> foldl a b x) == x

kaikilla x. (Tehtävän voi toki tehdä foldl:llä, mutta alkuperäinen tarkoitus oli käyttää määritelmässä foldr funktiota.)

Yhdistetyistä funktioista

Funktio on mitä parhain rajapinta monelle asialle. Erityisen hauskaa on luoda suurempia toiminnallisia kokonaisuuksia yhdistetyistä funktioista, mutta se ei ole aina helppoa. Jos esimerkiksi haluamme lisätä logituksen funktioihimme, niin yhdistys-operaattori ei enää toimi:

> foo, bar :: Int -> (Int, String)
> foo x = (x+1 , "lisättiin yksi")
> bar x = (x*2 , "kerrottiin kahdella")

> -- yhd = bar . foo . foo -- VIRHE! Tyypit väärin ja logi ei kasva!

Sama tapahtuu osittaisilla funktioilla:

> type Man   = String
> type Woman = String
> type Name = String

> fathers :: [(Name,Man)]
> fathers =  [("Henry Frederick","James I")
>            ,("Elizabeth Palatine","James I")
>            ,("Charles I","James I")
>            ,("Robert","James I")
>            ,("Sophia of Brunswick","Frederick V")
>            ,("Charles II", "Charles I")]

> mothers :: [(Name,Woman)]
> mothers =  [("James I", "Mary, Queen of Scots")
>            ,("Henry Frederick","Anne of Denmark")
>            ,("Elizabeth Palatine","Anne of Denmark")
>            ,("Robert","Anne of Denmark")
>            ,("Sophia of Brunswick","Elizabeth Palatine")
>            ,("Charles II", "Henrietta Maria of France")]

> father :: Name -> Maybe Man
> father = (flip lookup) fathers

> mother :: Name -> Maybe Woman
> mother = (flip lookup) mothers

> -- grandfather = father . father                 -- VIRHE! 
> -- grandmother = mother . mother                 -- VIRHE!
> -- grandfathersMother = mother . father . father -- VIRHE!

Toteuta yhd, siten, että se kääntyy ja logimerkkijono kasvaa.
Toteuta grandfathersMother, siten, että se toimii.

Aika työlästä ja ikävää, eikö?

Toteuta funktio

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

siten, että määritelmä

yhd = bind1 bar . bind1 foo . foo

vastaa a-kohdan määritelmääsi.

Toteuta funktio bind2 siten, että määritelmä
```
grandfathersMother = bind2 mother . bind2 father . father
```
vastaa b-kohdan funktiota.
Päättele (itse) funktion bind2 tyyppi.
Poimi annetusta listasta kaikki iso-isät ja iso-äidit.

Aika kätevää, eikö?

Reflektiota

Tutkaile oppimistasi.

Mitä opit,
mikä oli vaikeaa,
mikä oli helppoa ja
mistä yllätyit?

Tässä == merkitsee, sitä että molemmat määritelmät toteuttavat saman sum funktion. ↩
Huomaa, että vaikka tässä on laskettu suoraan lopputulokseen askel askeleelta, niin oikeasti tähänkin kuluisi pari sivua suttupaperia, joihin ensin kirjoitetaan haluttu lopputulos ja sitten kokeillaan askelia sieltä täältä. ↩
Rekursion voi toki korvata fix f = f (fix f) funktiolla, mutta siinä on aina aivonyrjähdyksen riski. ↩
kiitokset Cale Gibbardille ja wikipedialle. ↩