Viikko 2 - Rekursio ja Induktio

Johdanto

Tämän viikon tarkoituksena on oppia funktio-ohjelmoinnin tärkein kontrollirakenne, eli rekursio. Muuttuvien arvojen puuttuessa emme voi ilmaista toistorakenteita perinteisinä silmukoina vaan joudumme turvautumaan rekursiivisiin määritelmiin. Rekursion käyttö tuntuu aluksi silmukoihin tottuneista luonnottomalle ja hankalalle, mutta kun siihen tottuu, se on jopa luonnollisempi tapa ajatella asioita. Eli, osa tehtävistä tuntuu varmasti tuskastuttavan hankalille aluksi, mutta se on aivan luonnollista ja menee ohi!

Tässä vaiheessa tapaamme myös Curry-Howard yhteyden ohjelmien ja todistusten välillä — rekursiivinen ohjelma vastaa rakenteena täysin matematiikasta tuttua induktiotodistusta. Paitsi että C-H isomorfismi on hauska triviatieto, niin induktiotodistuksia tekemällä oppii nopeammin ohjelmoimaan rekursiivisia funktioita: asiaa tulee katsottua ikäänkuin molemmilta puolilta.

Luentomateriaalista tulee lukea Learn You a Haskellin kappale 5

Rekursio listoilla

Koska rekursiivinen ajattelu on monelle uutta, hyödynnetään aluksi järjestelmällistä rekursiivisen funktion suunnittelumenetelmää:

Kerro ääneen, omin sanoin, mitä funktion tulisi tehdä.
Määrittele funktiosi tyyppi. Vaikka kyseessä olisi polymorfinen funktio, joka toimii kaikentyyppisille listoille, niin aluksi voit käyttää jotain konkreettia tietytyyppiä, kuten kokonaislukua. Virheilmoituksista tulee yksinkertaisempia.
Luetteloi perustapaukset. Useimmissa tehtävissä on perustapauksia, joiden ratkaisu on triviaali. Esimerkiksi listan pituutta laskettaessa perustapaus on tyhjä lista ja binääripuuta läpikäydessä se on lehtisolmu Muita perustapauksia saattavat olla esimerkiksi tyhjät alkiot, luku n+1, True tai False.
Luetteloi muut tapaukset. Mitkä tapaukset jäivät perustapausten ulkopuolelle? Näitä ovat esimerkiksi epätyhjä lista, binääripuun haarasolmu, n < N tai ylipäätänsäkin kaikki tapaukset joista ei suoraan näe mitä niille tulee tehdä.
Ohjelmoi perustapaukset. Kirjoita perustapausten määritelmät käyttäen (yleensä) pattern matchingia. Esimerkiksi sum [] = 0, length [] = 0 tai keyInTree key (Tip element) = if element==key then True else False.
Esittele muut tapaukset. Esittele kaikki muut tapaukset käyttäen (yleensä) pattern matchingia. Esimerkiksi sum (x:xs) = ? ja length (x:xs) = ? tai keyInTree key (Branch value left right) = ?.

Nyt sinulla on määritelmiä, joissa on ongelma on pilkottu useampaan osaan. Listan tapauksessa esillä on listan ensimmäinen alkio ja loput listasta. Puiden tapauksessa sinulla on solmun arvoa ja kaksi pienempää puuta, left ja right.

Tee rekursiivinen kutsu ja yhdistä tapaukset. Oleta, että osaat ratkaista osaongelmat ja käytä niiden ratkaisuja ratkaistaksesi koko ongelman.

Esimerkiksi summan tapauksessa oletamme, että osaisimme laskea listan xs summan. Siitä seuraa tietysti, että sum (x:xs) = x + sum xs. Binääripuun tapauksessa oletamme osaavamme löytää avaimen joko oikeasta tai vasemmasta alipuusta, joten tehtäväksi jää vain valita kummasta se etsitään: keyInTree key (Branch value left right) = if key < value then keyInTree left else keyInTree right.

Pidä pieni tauko, sillä ongelma on nyt ratkaistu. Voit toki yleistää tyypin, mikäli käytit kohdassa ii) jotain yksinkertaisempaa tyyppiä.

Summa

Tee rekursiivinen funktio summaa, joka laskee parametrina annetun listan alkioiden summan.

Toteuta suunnitteluohjeen kohta ii).
Toteuta suunnitteluohjeen kohta iii).
Toteuta suunnitteluohjeen kohta iv).
Toteuta suunnitteluohjeen kohta v).
Toteuta suunnitteluohjeen kohta vi).
Toteuta suunnitteluohjeen kohta vii).

Parilliset

Tee rekursiivinen funktio parilliset, joka palauttaa listan, jossa on annetun listan parilliset luvut.

Toteuta suunnitteluohjeen kohta ii).
Toteuta suunnitteluohjeen kohta iii).
Toteuta suunnitteluohjeen kohta iv).
Toteuta suunnitteluohjeen kohta v).
Toteuta suunnitteluohjeen kohta vi).
Toteuta suunnitteluohjeen kohta vii).

Ilman

Tee rekursiivinen funktio ilman, joka palauttaa listan ilman annettua alkiota. Esimerkiksi ilman 'i' "kissa istuu" == "kssa stuu".

Toteuta suunnitteluohjeen kohta ii).
Toteuta suunnitteluohjeen kohta iii).
Toteuta suunnitteluohjeen kohta iv).
Toteuta suunnitteluohjeen kohta v).
Toteuta suunnitteluohjeen kohta vi).
Toteuta suunnitteluohjeen kohta vii).

Yhdistä

Tee rekursiivinen funktio (++), joka palauttaa kaksi listaa yhdistettynä yhdeksi. Esim. [1,2,3] ++ [4,5,6] == [1,2,3,4,5,6]. Varuskirjastossa on jo samanniminen funktio, joten keksi uusi nimi, tai kirjoita import Prelude hiding ((++)) ohjelmasi alkuun.

Toteuta suunnitteluohjeen kohta ii).
Toteuta suunnitteluohjeen kohta iii).
Toteuta suunnitteluohjeen kohta iv).
Toteuta suunnitteluohjeen kohta v).
Toteuta suunnitteluohjeen kohta vi).
Toteuta suunnitteluohjeen kohta vii).

Puu

Tee rekursiivinen määritelmä puu, joka esittää (oikeaa) puuta ja jonka voi piirtää seuraavalla Gloss-kirjastoa käyttävällä ohjelmalla:

module Main where

import Graphics.Gloss

main = displayInWindow "Puu" (500,500) (20,20) blue puu

Toteuta suunnitteluohjeen kohta ii).
Toteuta suunnitteluohjeen kohta iii).
Toteuta suunnitteluohjeen kohta iv).
Toteuta suunnitteluohjeen kohta v).
Toteuta suunnitteluohjeen kohta vi).
Toteuta suunnitteluohjeen kohta vii).

Vinkki: Gloss kirjasto sisältää seuraavat hyödylliset funktiot.

green :: Color
rectangleSolid :: Float -> Float -> Picture
rotate :: Float -> Picture -> Picture
scale :: Float -> Float -> Picture -> Picture
color :: Color -> Picture -> Picture
green :: Color

ännääK!

Tee funktio, joka kääntää annetun listan tai merkkijonon toisin päin: kaanna "kissa" ==> "assik"

Toteuta suunnitteluohjeen kohta ii).
Toteuta suunnitteluohjeen kohta iii).
Toteuta suunnitteluohjeen kohta iv).
Toteuta suunnitteluohjeen kohta v).
Toteuta suunnitteluohjeen kohta vi).
Toteuta suunnitteluohjeen kohta vii).

merputaatiot ja treumapatiot

Tee funktio, joka laskee listan kaikki permutaatiot. Tässä kannattaa miettiä ensin, miten ongelma yleensä jakautuu kahteen pienempään ja että olisiko jo toteutetuissa funktioissa jotain köyttökelpoista..

Toteuta suunnitteluohjeen kohta ii).
Toteuta suunnitteluohjeen kohta iii).
Toteuta suunnitteluohjeen kohta iv).
Toteuta suunnitteluohjeen kohta v).
Toteuta suunnitteluohjeen kohta vi).
Toteuta suunnitteluohjeen kohta vii).

Mergesort

Tee funktio, joka yhdistää kaksi suuruusjärjestyksessä olevaa listaa:

 merge [1,5,7] [3,5,9]
 ==
 [1,3,5,5,7,9]

Toteuta ‘mergesort’ algoritmi listoille.

Pieniä todistuksia

Yksinkertaisen rekursiivisen ohjelman oikeaksi todistaminen on käytännössä hyvin samankaltainen temppu kuin sen kirjoittaminen. Tässä yhteydessä käytämme lukiosta tuttua [induktiotodistus]ta. Induktiotodistuksen idea on osoittaa, että

jos väite pätee yhdelle tapaukselle, se pätee myös seuraavalle, ja
väite pätee ensimmäiselle tapaukselle,

ja tehdä niistä johtopäätös

väite pätee kaikille tapauksille.

Voimme esimerkiksi todistaa, että aikaisemmissa tehtävissä tekemiemme määritelmien mukaan kahden listan pituuden summa on sama kuin sen listan pituus, joka saadaan yhdistämällä ne yhdeksi listaksi.

Tämä voidaan tehdä hyvin mekaanisesti käymällä seuraavat vaiheet läpi:

Määritelmät ja oletukset

Kirjoita kaikki olennaiset määritelmät ja oletukset paperille.

Esimerkki:

{- Length -}
length [] = 0                  -- length 1.
length (x:xs) = 1 + length xs  -- length 2.

{- (++) -}
[] ++ b = b                    -- (++) 1. 
(a:as) ++ b = a:(as ++ b)      -- (++) 2.

Väite

Kirjoita ylös mitä olet todistamassa, eli Väite.

Esimerkki:

{- Väite -}  
 length a + length b = length (a ++ b)

Triviaalit tapaukset

Osoitetaan kaikki triviaalit tapaukset tosiksi.

Esimerkki:

Tässä tehtävässä triviaali tapaus on a==[]. Siispä laskemme, että length [] + length b == length ([]++b)

 {- tapaus a==[] -}
 length [] + length b
== {- length 1. -}
 0 + length b
== {- 0 + a = a -}
 length b
== {- (++) 1, kääntäen: b = [] ++ b -}
 length ([] ++ b)
{- Väite on tosi triviaalissa tapauksessa -}

Induktio-askel

Osoitetaan, että jos väite pätee jollekin tapaukselle, se pätee myös ‘seuraavalle’. Tätä voi verrata rekursiivisen ohjelman suunnitteluun, jossa askel otetaan jakamalla tehtävä pienempiin osiin. Induktion kanssa puolestaan otetaan pienemmät osat ja koostetaan niistä suurempi kokonaisuus.

Esimerkki:

Tässä tapauksessa tarkastelemme siis listoja c:cs ja cs ja osoitamme, että jos (length cs + length b) == length (cs++b) pätee, niin length (c:cs) + length b == length ((c:cs) ++ b) pätee myös.

 length (c:cs) + length b 
== {- length 2 -}
 1 + (length cs + length b)
== {- Induktio-oletus (length cs + length b) == length (cs++b) -}
 1 + length (cs++b)
== {- length 2, kääntäen: 1 + length xs == length (x:xs) -}
 length (c:(cs++b))
== {- (++) 2, kääntäen: a:(as++b) = (a:as) ++ b -}
 length ((c:cs)++b)

Eli, osoitimme, että

 length (cs) + length b == length ((cs) ++ b)
=> {- Ks. edellinen todistus -}
 length (c:cs) + length b == length ((c:cs) ++ b)

Suomeksi sanottuna siis sen, että jos väite pätee jonkin kokoiselle listalle, se pätee myös yhtä pidemmälle listalle.

Todetaan alkuperäinen väite todeksi

Todetaan todistus valmiiksi induktioon nojaten. Väite pätee tyhjälle listalle. Induktio-askeleen mukaan sen täytyy päteä silloin yhden alkion mittaiselle listalle. Edelleen, koska se pätee yhden mittaisille listoille, niin se pätee myös kahden alkion mittaisille listoille. Tätä voidaan jatkaa loputtomiin, joten väite pätee kaikille äärellisen mittaisille listoille.

Ensimmäinen todistus!

Todista, että aiemmin määrittelemällesi summa funktiolle pätee

summa (xs++ys) == summa xs + summa ys

käyttäen ylläolevaa reseptiä induktiontodistukselle.

Toinen todistus!

Todista, että aiemmin määrittelemällesi ilman funktiolle pätee

length (ilman a b) <= length b

käyttäen ylläolevaa reseptiä induktiontodistukselle.

Kolmas todistus!

Todista, että aiemmin määrittelemällesi kaanna funktiolle pätee

summa (kaanna a) == summa a

Yhteenveto

Mitä yhteistä rekursiolla ja induktiotodistuksilla siis oli?