Pääsin harjoittamaan kunnolla Pythonin paria funktionaalista rakennetta. Koodissa on tarkoitus selvittää, onko alkiolle määrätyt tagit minkälaisessa kunnossa. Tarkoitus on rakentaa suodatin: jos alkiolla on jokin tagi, mikä on suodinlistalla, pääsee se näkyville. Suotimia säätämällä tietenkin rajaillaan alkioita. Halusin vielä toteuttaa erikseen suotimen “vähintään yksi riittää” ja “kaikkien on täsmättävä” -toiminnallisuudelle.

Matemaattisesti nämä Any ja All, vastaavasti, ovat kvanttoreiden säestämiä. , missä E on käyttäjän valitsema suodatinkokoelma ja A on tämän testattavan alkion tagijoukko. All on tietenkin vain kvanttorin vaihdos: , eli matemaattisesti asia on ilmaistavissa hyvin selkein keinoin. Entä imperatiivilla menetelmillä?

Imperatiivisella paradigmalla lähtisin kaiketi kaksoissilmukassa käymään ensin filttereitä (joukkoa E) läpi, alisilmukassa sitten testaisin filtteriä sitä alkiota (ja joukkoa A) vastaan. Tapauksessa Any pysäyttäisin heti silmukkatoiston, kun yksikin osuma löytyy. Se on yksinkertainen toteuttaa.

Tapauksessa All sitten taas pitää kai ylempään silmukkaan asettaa katkaisuehto: jos yksikin filtterin E sisältämistä alkioista ei kuulunut joukkoon A, palautetaan falsea. No, näin järkeiltynä ei sekään mikään sensaatiomaisen monimutkainen ratkaisu ollut.

Mutta miten tein sen Pythonilla?

  # Checks if a media item passes filters!
  def passFilter(self, item):
    hash = self.meta[item.GetData()][1]
    tags = self.db.getTags(hash)  # <---  A
    if self.filterType == self.ALL:
      return reduce(lambda x,y: x and y, map(lambda x: x in self.filter, tags))
    elif self.filterType == self.ANY:
      return reduce(lambda x,y: x or y, map(lambda x: x in self.filter, tags))

Kommentteihin merkkasin joukon A, joukko E on self.filter.

Ylläoleva koodi noudattaa sitten sekä hyviä että huonoja tapoja. Hyviin tapoihin voisi kuulua funktionaalinen lähestysmistapa, huonoihin tuo filterTypen käyttö. Se on onneksi helppo fiksata pythonissa.

Kuka tunteekaan funktiot map ja reduce tietää, että tämä ratkaisumalli on tehottomampi kuin esittämäni imperatiivinen pseudo. Syy tämän kirjailemiseen onkin toisaalta se, että matemaattinen mallinnustapa oli kirjoittamishetkellä helpompi löytää. Äsken järkeilemäni imperatiivinen tapa olisi nyt helppo kirjailla ylös koodiksi, joten voi olla, että sen teenkin.

Imperatiivinen toteutus, olettaen, että se toimii, ottaa Any-tapauksessa lähelle O(n):ää (oletetaan vaikka, että tageja on maltillisesti). All-tapauksessa ollaan lähellä O(m*n):ää, mutta silti viivytään kentällä mahdollisimman vähän aikaa.

Funktionaaliset toteutukseni sen sijaan eivät ainakaan Pythonissa edes yritä optimoitua. Ensin funktio map työstää nimettömän lambdafunktion jokaiselle alkion A tagille. Lambdafunktiossa tarkistetaan joukkoihin kuuluminen; se on hyvällä joukkototeutuksella luokkaa O(log n). Sitten reduce foldaa mapin tekemän uuden joukon siten, että kaikki alkiot laitetaan perätysten ja väliin laitetaan haluttu laskutoimitukset täyttävä funktio, tässä tapauksessa eli and.

Eli tyhmä toteutus purkaa lausekkeet auki suoriltaan. Vaikka tapauksessa All tulisi ensimmäisestä joukon E alkiosta hylsy, jatkaa funktionaalinen malli kulkuaan. Eihän se jaksa asiaa tarkastaakaan.

Haskellilla kirjailtuna sama funktio toimii sitä vastoin todella tehokkaasti; vaativuusluokaksi mutuilen saman kuin esittämälleni pseudo-imperatiiviselle koodille. Syynä on laiska laskenta. Haskell purkaa map-komennon toki auki, mutta ei suorita lambdoja vielä. Sitten kun se vielä purkaa reducenkin pois (Haskellissa tosin foldr), tuloksena on iso pino laskentaa. Kun nyt esimerkkitapauksessa otetaan ensimmäinen lauseke, ja saadaan False, osataan päätellä -merkkien ketjun perusteella koko lausekkeen totuusarvoksi False. Kaikki tämä nopeutus siis sen takia, että Haskell tekee ensin välivaiheen paperille ja vasta lopuksi suorittaa laskutoimitukset. En tiedä, mikä on Pythonin toimintamalli mutta sehän voisi hyvinkin tehdä samaa.

Lopuksi laitan refaktoroidun, oikeaoppisen version teille. En halua C-tyylisiä roskafunktioita esitellä kaikelle kansalle.

  # Checks if a media item passes filters!
  # This involves checking filters from the db
  def passFilter(self, item):
    hash = self.meta[item.GetData()][1] 
    tags = self.db.getTags(hash)
    return self.filterFunction(tags)

  def filter_any(self, tags):
      return reduce(lambda x,y: x or y, map(lambda x: x in self.filter, tags))

  def filter_all(self, tags):
      return reduce(lambda x,y: x and y, map(lambda x: x in self.filter, tags))

Ja sitten on erikseen setteri, jolla filtterifunktion voi laittaa. Homma on nyt oikein higher orderia ja melko funktionaalista. Haskellissahan tämä juuri tämänlainen operaatio sujuu prikulleen samanlaisin rivein. Ne vain sijaitsevat vähän eri paikoissa, mutta kun tässäkään ei muuttujiin kosketa, on tämä periaatteessa pelkällä siirtelyllä funktionaalista.