Lajittelu ja lambda-funktiot

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ää ns. lambda-funktiona suoraan lajittelufunktion kutsun yhteydessä. Lambda-funktio on pelkistetty nimetön funktiomääritys, joka koostuu parametrilistasta, nuolesta eli merkkiyhdistelmästä “->”, ja funktion rungosta. 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 tavallisen funktion tapaisesti koodilohkona tai vaihtohtoisesti pelkistetysti suoraan funktion paluuarvon (ilman erillistä return-lausetta) määrittävänä lauseena. Javan lambda-funktioiden syntaksi on hyvin samantapainen JavaScriptin kanssa. Alla on kolme toiminnaltaan lähes indenttistä 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 alphabetical) 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 alphabetical) 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ää tarvittaessä 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 alphabetical) 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 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?