Lajittelu ja lambda-funktiot

Lambda-funktiot

Lambda-funktio (lambda function) eli lambda on funktionaalisen ohjelmoinnin peruskäsitteitä. Tässä luvussa ei perehdytä niinkään lambdojen teoreettiseen taustaan, vaan pyritään esittämään lambda-funktioiden perusidea ja pohditaan, kuinka Javassa valmiina olevia lambda-funktioita hyödynnetään, kun halutaan ilmaista jokin toiminnallisuus lyhyemmin. Sovelluskohteeksi on valittu lajittelu, joka on usein sujuvinta toteuttaa siten, että lajittelukriteeri määritellään tiiviisti lambda-funktion avulla.

Lambda on nimetön funktio, jota voidaan käsitellä arvon tavoin. Lambda voidaan muun muassa sijoittaa muuttujan arvoksi, se voidaan palauttaa toisen funktion paluuarvona ja se voidaan välittää parametriarvona toiselle funktiolle.

Lambda-funktion määrittely koostuu parametrilistasta, nuolesta eli merkkiyhdistelmästä -> ja funktion rungosta:

(parametrilista) -> {lauseet}

Lambda-funktion parametrilistassa ei ole pakko mainita tyyppejä, parametrilistan ympäriltä voi jättää sulut pois, jos parametreja on vain yksi, ja funktion rungon saa määrittää joko tavalliseen tapaan lohkona tai suoraan ilman erillistä return-lausetta funktion paluuarvon määrittävänä lausekkeena. Javan lambda-funktioiden syntaksi on hyvin samantapainen JavaScriptin kanssa.

Seuraavassa esimerkissä pyritään esittämään lambda-funktioiden idea. Esimerkin lambdoja ei voi vielä käyttää Java-ohjelmassa. Näet myöhemmässä luvussa kuinka funktionaalisen rajapinnan avulla tehty määrittely mahdollistaa esimerkissä annettujen lambdojen määrittelyn omassa ohjelmassa.

Oletetaan, että tavoitteena olisi ilmaista alla tavanomaisena funktiona annettu toiminnallisuus (kahdella kertominen ja tulon palauttaminen) lyhyemmin lambda-funktiota käyttäen.

public int multiplyBy2(int x) {
   return x * 2;
}

Lambdan ensimmäinen muoto on ilmeinen:

(int x) -> {return x * 2;}

Tätä voidaan pelkistää edelleen poistamalla parametrin tyyppi, koska Java-kääntäjä osaa päätellä sen ja paluuarvon tyypin automaattisesti.

(x) -> {return x * 2;}

Lambda pelkistyy edelleen muotoon:

(x) -> x * 2

koska funktion runko koostuu pelkästä return-lauseesta. Kaikkein yksinkertaisimpaan muotoon:

x -> x * 2

päästään poistamalla parametrilistan sulkeet. Tämä on mahdollista, kun parametreja on vain yksi kappale.

Lajittelu lambda-funktioilla

Javan luokkakirjasto tarjoaa funktion Arrays.sort tavallisten taulukoiden ja funktion Collections.sort listojen (joihin myös ArrayList lukeutuu) lajitteluun. Näillä funktioilla voi suoraan sellaisenaan lajitella Javan perustyyppejä (kuten luvut ja String-merkkijonot) niiden luonnolliseen kasvavaan järjestykseen. Jos lajitellaan muunlaisia alkioita, tai halutaan muuten vain käyttää erilaista järjestyskriteeriä, voi lajittelufunktioille antaa parametrina oman lajittelussa käytettävän vertailufunktion. Lisäksi Javan listoilla (mukaanlukien ArrayList) on jäsenfunktio sort, jolle pitää aina (myös Javan perustyyppien yhteydessä) antaa parametrina vertailufunktio.

Vertailufunktion tulee ottaa kaksi lajiteltavien alkioiden tyyppistä parametria ja palauttaa int-arvo, joka kertoo kyseisten kahden alkion välisen järjestyksen: negatiivinen arvo tarkoittaa, että ensimmäinen alkio on pienempi, nolla, että alkiot ovat yhtäsuuria, ja positiivinen arvo, että toinen alkio on pienempi.

Lajittelufunktiolle välitettävä vertailufunktio on usein näppärintä määrittää lambda-funktiona suoraan lajittelufunktion kutsun yhteydessä, jolloin lambda välitetään lajittelufunktiolle parametriarvona. Alla on kolme toiminnaltaan lähes identtistä lambda-funktiota. Niistä kukin saa kaksi parametria a ja b, joiden tässä esimerkissä oletetaan olevan lukuja, ja suorittaa alenevaa järjestystä vastaavan vertailun. Esimerkki ilmentää toisaalta parametrien tyyppien vapaaehtoisuutta ja toisaalta mahdollisuutta korvata runko pelkällä lauseella, jos funktion logiikka on riittävän yksinkertainen sellaisella toteutettavaksi. Huomaa, että tässä keskimmäinen lambda-funktio on oikeastaan kahta muuta hieman rajoitetumpi, koska siinä parametrien tyypiksi on kiinnitetty double. Jos lambda-funktion parametrien tyypit jätetään pois, funktio käyttäytyy aivan kuin parametrien tyypeiksi olisi määritetty päätelty tyyppi var.

(a, b) -> a < b ? 1 : (a > b ? -1 : 0)

(double a, double b) -> a < b ? 1 : (a > b ? -1 : 0)

(a, b) -> {
  if(a < b) {
    return 1;
  }
  if(a > b) {
    return -1;
  }
  return 0;
}

Alla annettu esimerkkiohjelma havainnollistaa lajittelufunktioita ja lambda-funktioita. Ohjelma lajittelee saamansa komentoriviparametrit muutamalla eri tavalla.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Sorting {
  public static void main(String[] argArr) {
    // Duplikoidaan komentoriviparametrit myös ArrayList-olioon, jotta
    // voidaan testata sekä tavallisten taulukoiden että listojen lajittelua.
    // List.of luo listan parametreinaan saamista alkioista tai taulukosta.
    ArrayList<String> argList = new ArrayList<>(List.of(argArr));

    System.out.println("Original order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("  list: " + argList);

    // Ensimmäinen lajittelu antamatta vertailufunktiota: nouseva aakkosjärjestys.
    Arrays.sort(argArr);
    Collections.sort(argList);
    System.out.println("Default sorting (= increasing lexicographical) order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("  list: " + argList);

    // Toinen lajittelu: laskeva kirjainkoosta välittämätön aakkosjärjestys.
    // Määritetään vertailufunktio kutsun parametrilistassa lambda-funktiona,
    // jonka rungon tilalla on suoraan vertailun tuloksen palauttava lause
    // (tässä tapauksessa String-luokan compareToIgnoreCase-funktion kutsu).
    // Alla molemmat vertailufunktiot toimivat samalla tavalla. Ensimmäisessä
    // on annettu parametrien yhteydessä String-tyyppi, mutta tyypit voi jättää
    // pois, kuten jälkimmäisessä lambda-funktiossa onkin tehty.
    Arrays.sort(argArr, (String a, String b) -> b.compareToIgnoreCase(a));
    Collections.sort(argList, (a, b) -> b.compareToIgnoreCase(a));
    System.out.println("Decreasing case-insensitive alphabetical order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("  list: " + argList);


    // Kolmas lajittelu: ensisijaisesti pituuden mukaan kasvava järjestys,
    // ja toissijaisesti (keskenään samanpituiset) kasvavaan
    // kirjainkoosta välittämättömään aakkosjärjestykseen.
    // Molemmat lambda-funktiot tuottavat saman lopputuloksen, mutta ensimmäisen
    // runko on toteutettu tavallisena koodilohkona ja toisen jälleen suoraan
    // tuloksen määrittävänä lauseena.
    Arrays.sort(argArr, (a, b) -> {
      if(a.length() != b.length()) {
        return a.length() - b.length();
      }
      return a.compareToIgnoreCase(b);
    });
    argList.sort((a, b) -> (a.length() != b.length()) ? a.length() - b.length()
                                  : a.compareToIgnoreCase(b));
    System.out.println("Ordered by length, secondarily in alphabetical order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("  list: " + argList);
  }
}

Tämän esimerkkiohjelman suoritus tapaan java Sorting One two Three seven ten tuottaa tulostuksen:

Original order:
  array: [One, two, Three, seven, ten]
  list: [One, two, Three, seven, ten]
Default sorting (= increasing lexicographical) order:
  array: [One, Three, seven, ten, two]
  list: [One, Three, seven, ten, two]
Decreasing case-insensitive alphabetical order:
  array: [two, Three, ten, seven, One]
  list: [two, Three, ten, seven, One]
Ordered by length, secondarily in alphabetical order:
  array: [One, ten, two, seven, Three]
  list: [One, ten, two, seven, Three]

Edellinen esimerkki ei sitä ilmennä, mutta Javan lambda-funktioiden sisältä voi oletusarvoisesti viitata niiden kutsukontekstissa näkyvissä oleviin muuttujiin ja jäseniin. Tämä eroaa C++-kielestä, jossa pitää tarvittaessa erikseen määrittää, mitä ulkoisia arvoja lambda-funktion käyttöön tuodaan.

Jos vertailun toteuttava lambda-funktio olisi muotoa (a, b) -> x.f(a, b), missä x on luokka tai olio, tai muotoa (a, b) -> a.f(b), ei lambda-funktiota tarvitse määrittää: vertailufunktioksi voi tällöin välittää funktion f sellaisenaan käyttäen Javan funktioviite-operaattoria ::. Kun f on määritetty luokassa C, voi funktioon viitata tilanteesta riippuen jollain seuraavista kolmesta tavasta:

  • Jos f on luokkafunktio, on siihen viittaava funktioviittaus aina muotoa C::f ja tuottaa saman tuloksen kuin lambda-funktio (a, b) -> C.f(a, b).

  • Jos f on tavallinen jäsenfunktio, riippuu viittaustapa siitä, vastaisiko tilanne lambda-funktiota (a, b) -> o.f(a, b), missä o on jokin luokan C olio, vai lambda-funktiota (a, b) -> a.f(b).

    • Tapausta (a, b) -> o.f(a, b) vastaava funktioviittaus on muotoa o::f.

    • Tapausta (a, b) -> a.f(b) vastaava funktioviittaus on muotoa C::f (eli samanlainen kuin luokkafunktion kohdalla). Huomaa, kuinka tässä tapauksessa funktio f on lajiteltavan tyypin jäsenfunktio, jota kutsutaan ensimmäisen parametrin a kautta, ja funktiolle f välitetään parametriksi vain toinen parametri b.

Edellä on oleellista huomata, kuinka Java tulkitsee funktioviittauksia konkreettisesti eri tavalla riippuen siitä, tehdäänkö funktioviittaus olion vai luokan kautta.

Alla annettu esimerkkiohjelma tekee täysin samanlaiset lajittelut kuin edellä, mutta käyttäen lambda-funktioiden sijaan funktioviittauksia. Ohjelman tulostekin on identtinen edellisen kanssa.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class FuncRefs {

  // Sisäinen apuluokka, jonka jäsenfunktio cmp vertailee merkkijonoja
  // kirjainkoosta välittämättä. Vertailujärjestys riippuu siitä, millainen
  // alustusarvo luokan rakentimelle annetaan.
  private class StrCmp {
    // Käytetäänkö käännettyä (laskevaa) järjestystä?
    private boolean reversed;

    StrCmp(boolean reversed) {
      this.reversed = reversed;
    }

    int cmp(String a, String b) {
      if(!reversed) {
        return a.compareToIgnoreCase(b);
      }
      return b.compareToIgnoreCase(a);
    }
  }

  // Jäsenfunktio, joka vertailee merkkijonoja ensisijaisesti pituuden ja
  // toissijaisesti kirjainkoosta välittämättömän aakkosjärjestyksen mukaan.
  private int lenCmp(String a, String b) {
    if(a.length() != b.length()) {
      return a.length() - b.length();
    }
    return a.compareToIgnoreCase(b);
  }

  // Muuten samanlainen funktio kuin edellä, mutta määritetty luokkafunktioksi.
  private static int staticLenCmp(String a, String b) {
    if(a.length() != b.length()) {
      return a.length() - b.length();
    }
    return a.compareToIgnoreCase(b);
  }

  private void execute(String[] argArr) {
    ArrayList<String> argList = new ArrayList<>(List.of(argArr));
    System.out.println("Original order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("  list: " + argList);

    // Oletusjärjestykseen lajittelu ei vaatisi vertailufunktiota. Mutta annetaan
    // tässä esimerkin vuoksi viite String-luokan jäsenfunktioon compareTo,
    // johon oletusjärjestyskin pohjautuu. Kyseessä on tavallinen jäsenfunktio,
    // ja lajittelun aikana tehtävät vertailut ovat muotoa a.compareTo(b).
    // Näin ollen funktioviite määritetään muodossa String::compareTo.
    Arrays.sort(argArr, String::compareTo);
    Collections.sort(argList, String::compareTo);
    System.out.println("Default sorting (= increasing lexicographical) order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("  list: " + argList);

    // Luodaan StrCmp-olio, jonka vertailu vastaa laskevaa järjestystä.
    StrCmp descStrCmp = new StrCmp(true);

    // Lajitellaan sekä argArr että argList laskevaan kirjainkoosta
    // välittämättömään aakkosjärjestykseen olion descStrCmp jäsenfunktion
    // cmp avulla. Tässä lajittelun aikaiset vertailut ovat muotoa descStrCmp.cmp(a, b),
    // joten funktioviittaus tehdään muodossa descStrCmp::cmp.
    Arrays.sort(argArr, descStrCmp::cmp);
    Collections.sort(argList, descStrCmp::cmp);
    System.out.println("Decreasing case-insensitive alphabetical order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("  list: " + argList);

    // Lajitellaan sekä argArr että argList ensisijaisesti pituuden mukaiseen järjestykseen ja
    // toissijaisesti kirjainkoosta välittämättömään aakkosjärjestykseen.
    // Ensimmäinen lajittelu käyttää tavallista jäsenfunktiota lenCmp, joka vertailee
    // tapaan this.lenCmp(a, b), joten funktioviittaus tehdään muodossa this::lenCmp.
    // Toinen käyttää luokkafunktiota staticLenCmp ja viittaus on muotoa FuncRefs::staticLenCmp.
    Arrays.sort(argArr, this::lenCmp);
    argList.sort(FuncRefs::staticLenCmp);
    System.out.println("Ordered by length, secondarily in alphabetical order:");
    System.out.println("  array: " + Arrays.toString(argArr));
    System.out.println("  list: " + argList);
  }

  // Tässä esimerkissä käytetään ei-staattisia jäseniä StrCmp ja lenCmp. Tämän
  // mahdollistamiseksi main-funktiossa luodaan dynaamisesti FuncRefs-olio, jonka
  // jäsenfunktio execute suorittaa ohjelman varsinaiset askeleet.
  public static void main(String[] argArr) {
    new FuncRefs().execute(argArr);
  }
}

Palaamme myöhemmin funktionaalisten rajapintojen yhteydessä siihen, miten Javassa määritetään funktio, jolle voi välittää funktioviitteen parametrina.

Millä seuraavista lambda-funktioista saadaan lajiteltua alkiot järjestykseen pisimmästä lyhimpään?