Luento 12 - Rekursiiviset tyypit

Tällä kertaa käsiteltiin rekursiivisia tyyppejä, jotka lienevät useille tuttuja esimerkiksi C:n linkitettyjen listojen toteutuksesta. Ajatuksena on, että tietue voi viitata itseensä. Täten voidaan luoda mitä mielenkiintoisimpia rakenteita. Toki ilman rekursiota pärjää ja on pärjättykin, mutta mikäli ohjelmointikieli sallii sen käytön, sitä voi kannattaa käyttää.

Luennon aluksi käsiteltiin myös tietuieiden samuutta. Helpoimmalla pääsee vertailemalla tietuiden nimiä (ns. nimisamuus). Toisaalta tässä tapauksessa kielen tasolla tulee huolehtia siitä, että nimet ovat uniikkeja tietuieita käytettäessä. Toinen tapa käsitellä samuutta on jättää nimen käsite omaan arvoonsa ja vertailla puhtaasti tietueiden sisältöä.

Tässä tapauksessa voidaan kiinnittää lisäksi huomiota tietueen sisäiseen järjestykseen tai jättää se huomiotta. Luennolla esitettiin edellä mainittuun tapaan bisimulaatioon pohjautuva ratkaisu, jossa vertailtavia tietueita askelletaan samanaikaisesti ja tutkitaan onko kunkin vertailtava tieto sama sen nimen ja tiedon suhteen. Tätä ehtoa voisi varmaan löyhentää keskittymällä vain tietotyyppiin ja jättämällä nimen huomiotta. Tosin mikäli nimi jätetään huomiotta voivat semanttisesti hyvinkin erilaiset tietueet tulla tulkituiksi samoiksi! Käsittääkseni jälkimmäisessä järjestyksen huomiotta jättävässä tapauksessa bisimulaatio voidaan toteuttaa käyttämällä toista tietuetta referenssinä ja toista tutkittavana. Huomaa, että kummankin tietueen tulee vuorollaan toimia referenssinä, jotta voidaan taata ettei toisessa tietueessa satu olemaan ylimääräisiä alkioita! Seuraavana algoritmi pseudokoodina:

struct1, struct2 = Struct(), Struct()

def structs_are_equal(struct1, struct2):
  for ref_node in struct1:
      found_node = False

      for node in struct2:
          if str(ref_node) == str(node)
             and type(ref_node) == type(node):
              found_node = True
              break

      if not found_node:
          return False

  return True # tietueet ovat samoja

Sinänsä algoritmissa ei ole mitään ihmeellistä (ellen sattunut tekemään jotain radikaalia virhettä). Luennolla esitettiin myös rekursiivisten tyyppien toteutusta lambda-kielessä. Koko touhun ytimessä on kiintopisteoperaattori, johon määritelty tyyppi voi viitata mahdollistaen rekursion. Toinen varsin mielenkiintoinen sivuttu asia oli laskostaminen (isorekursio), jossa kiintopiste irrotetaan erikseen kokonaisuudesta ja rekursio mahdollistuu erityisten laskostamisaliohjelmien (fold, unfold) avulla, joilla tietue käsittääkseni voidaan kääriä auki (unfold, rekursio pois) ja kääriä kiinni (fold, rekursio takaisin).

Myös tietueilla operoimista käytiin läpi. Tässä yhteydessä huomioni herätti erityisesti jo Pythonista tuttujen sum ja lambda aliohjelmien toteutus. "reduce" lienee menee hieman samaan tapaan. Ajatuksena näissä pienissä apureissa on, että annettua tietuetta (tässä tapauksessa rajoituttiin NumListiin (numeroiden lista)) voidaan manipuloida annetun aliohjelman avulla. Esimerkiksi map suorittaa annetun aliohjelman kaikille tietueen alkioille ja palauttaa muunnetun tietueen.

Myös virtojen (stream) käsite kiinnitti huomioni. Virralta voidaan kysyä arvoja, kuten generaattorilta ikään. Virta voi palauttaa yksinkertaisimmillaan jonkin luvun. Se voi myös säilyttää tilansa mahdollistaen matemaattisten funktioiden kuvaamisen virtana. Myös satunnaislukugeneraattorinkin luulisi syntyvän helposti tätä kautta.