Pelipatan dan agregasi

Pelipatan (folding) adalah menguraikan sebuah koleksi menjadi satu nilai akhir dengan menjalankan operasi biner berulang kali. Topik ini membahas foldLeft yang bekerja dengan nilai awal, reduce yang menuntut koleksi tidak kosong, serta groupBy untuk agregasi per kelompok. Bagian terakhir menyusun pipeline agregasi lengkap yang diakhiri sorted, sehingga keluarannya teratur dan tidak bergantung pada urutan internal Map.

foldLeft: akumulator dan nilai awal#

foldLeft(z)(op) memulai pelipatan dari nilai awal z, lalu berjalan dari kiri ke kanan. Pada setiap elemen, operasi op menerima akumulasi sejauh ini beserta elemen tersebut, lalu mengembalikan akumulasi yang baru. Untuk List(78, 45, 90) dengan nilai awal 0, pelipatannya berlangsung sebagai ((0 + 78) + 45) + 90.

Bentuk panggilannya memuat dua kelompok parameter, yaitu nilai awal lalu operasinya, dan pemisahan ini disengaja. Nilai awal diberikan sekali di awal, sedangkan operasinya ditempatkan pada kelompok kedua, sehingga tipe akumulator dan tipe elemen diperiksa compiler secara terpisah. Pustaka juga menyediakan foldRight yang berjalan dari kanan, tetapi foldLeft menjadi pilihan yang lazim karena List diproses secara alami dari depan.

Akumulator tidak harus bertipe sama dengan elemennya, sehingga satu pola yang sama memenuhi banyak kebutuhan agregasi. Nilai awal 0 dengan penjumlahan menghasilkan total, penghitung yang bertambah satu untuk setiap elemen menghasilkan banyaknya data, dan pembagian total dengan hitungan menghasilkan rata-rata. Program berikut menjalankan ketiganya pada satu List nilai ujian.

// foldLeft melipat koleksi dari kiri dimulai dari nilai awal
@main def pelipatan(): Unit =
  val nilai: List[Int] = List(78, 45, 90, 62, 55, 84)

  val total: Int = nilai.foldLeft(0)((akumulasi, n) => akumulasi + n)
  val banyak: Int = nilai.foldLeft(0)((hitungan, _) => hitungan + 1)
  val rataRata: Double = total.toDouble / banyak

  println(total)
  println(banyak)
  println(rataRata)

# menjalankan program pelipatan.scala
scala-cli run pelipatan.scala

414
6
69.0

Baris pertama menjumlahkan seluruh nilai, baris kedua menghitung banyaknya elemen dengan mengabaikan isi elemen melalui _, dan baris ketiga membagi total yang dikonversi menjadi Double. Ketiga hasil berasal dari pola yang sama, yaitu akumulasi yang diperbarui elemen demi elemen, sehingga agregasi baru hanya berarti mengubah nilai awal dan operasinya.

reduce dan batasannya#

reduce adalah pelipatan tanpa nilai awal, sehingga elemen pertama menjadi nilai awalnya. Bentuk ini ringkas untuk operasi yang bersifat asosiatif seperti penjumlahan atau pencarian nilai terbesar, tetapi ia memuat asumsi bahwa koleksinya tidak kosong. Untuk koleksi yang berisi, reduce(op) berperilaku sama dengan foldLeft yang menggunakan elemen pertama sebagai nilai awalnya, sehingga keduanya dapat dipertukarkan begitu keberadaan elemen pertama sudah pasti. Perbedaan yang menentukan muncul pada koleksi kosong, karena foldLeft masih memiliki jawaban yang sudah ditentukan, sedangkan reduce tidak memiliki apa pun untuk dikembalikan. Program berikut menjalankan reduce untuk mencari nilai terbesar, pertama pada koleksi yang berisi lalu pada koleksi kosong.

// reduce bekerja pada koleksi berisi dan berhenti pada koleksi kosong
@main def reduceTerbesar(): Unit =
  val nilai: List[Int] = List(78, 45, 90, 62, 55, 84)
  val kosong: List[Int] = List.empty

  println(nilai.reduce((a, b) => if a > b then a else b))
  println(kosong.reduce((a, b) => if a > b then a else b))

# menjalankan program reduce.scala; baris kedua sengaja membuat program berhenti
scala-cli run reduce.scala

90
Exception in thread "main" java.lang.UnsupportedOperationException: empty.reduceLeft
	at scala.collection.IterableOnceOps.reduceLeft$(IterableOnce.scala:876)
	at scala.collection.AbstractIterable.reduceLeft(Iterable.scala:979)
	at scala.collection.AbstractIterable.reduce(Iterable.scala:979)
	at reduce$package$.reduceTerbesar(reduce.scala:7)
	at reduceTerbesar.main(reduce.scala:2)

Program mencetak 90 dari koleksi yang berisi, kemudian berhenti dengan java.lang.UnsupportedOperationException: empty.reduceLeft ketika reduce dijalankan pada List kosong. Tidak ada nilai yang dapat menjadi akumulasi awal pada koleksi kosong, sehingga error itu konsisten dengan definisi reduce. Apabila koleksi bisa kosong, gunakan foldLeft dengan nilai awal yang masuk akal, atau reduceOption yang menghasilkan Option berisi hasilnya.

groupBy dan peringkasan kelompok#

groupBy(f) membagi koleksi menurut hasil fungsi kuncinya dan menghasilkan Map yang memetakan setiap kunci ke kelompok elemennya. Pada pustaka immutable, urutan iterasi Map hasil groupBy tidak dijamin, sedangkan setiap kelompok tetap berupa koleksi asalnya, yaitu List pada contoh berikut. Karena setiap kelompok berupa koleksi utuh, tahap berikutnya bebas memperlakukannya sebagai List biasa, misalnya menghitung, menjumlah, atau mengurutkan isinya.

Peringkasan per kelompok ditulis dengan view.mapValues lalu dimaterialisasi. Metode mapValues langsung pada Map telah ditinggalkan karena menyembunyikan evaluasi yang ditunda di balik tipe Map, sehingga padanan yang disarankan adalah view.mapValues(...) yang menampilkan evaluasi tertunda tersebut secara eksplisit.

// groupBy mengelompokkan elemen, lalu setiap kelompok diringkas dan diurutkan
@main def kelompok(): Unit =
  val nilai: List[Int] = List(78, 45, 90, 62, 55, 84, 47, 81)

  val berpuluhan: Map[Int, List[Int]] = nilai.groupBy(n => n / 10)
  val rentang: Seq[(Int, Int)] =
    berpuluhan.view.mapValues(isinya => isinya.size).toSeq.sortBy(_._1)

  rentang.foreach((puluhan, banyak) => println(s"$puluhan puluhan: $banyak nilai"))

# menjalankan program grup.scala
scala-cli run grup.scala

4 puluhan: 2 nilai
5 puluhan: 1 nilai
6 puluhan: 1 nilai
7 puluhan: 1 nilai
8 puluhan: 2 nilai
9 puluhan: 1 nilai

Kelompok dibentuk menurut hasil n / 10, yaitu digit puluhannya, dan view.mapValues(isinya => isinya.size) menghitung banyaknya anggota setiap kelompok. Pencetakan dilakukan setelah sortBy(_._1) mengurutkan pasangan menurut kuncinya, sehingga keenam baris tampil menurut rentang nilai dari kecil ke besar. Tanpa pengurutan itu, urutan cetaknya bergantung pada struktur internal Map dan tidak dapat diandalkan.

Pipeline agregasi yang diakhiri sorted#

Pipeline agregasi lengkap menyambungkan tahap-tahap pada topik ini, yaitu memecah sumber menjadi elemen, mengelompokkan, merangkum setiap kelompok, lalu mengurutkan hasil akhirnya. Tahap pengurutan di ujung bukan pelengkap kosmetik, melainkan jaminan bahwa keluaran tidak bergantung pada urutan iterasi internal Map.

Program berikut menghitung frekuensi kata pada satu kalimat melalui pipeline tersebut.

// Pipeline agregasi: pecah kalimat, kelompokkan, ringkas, lalu urutkan di ujung
@main def frekuensi(): Unit =
  val kalimat: String = "koleksi scala menyimpan data dan data diolah menjadi informasi"

  val terurut: Seq[(String, Int)] =
    kalimat.split(" ").toList
      .groupBy(identity)
      .view.mapValues(isinya => isinya.size).toMap
      .toSeq
      .sortBy((kata, hitung) => (-hitung, kata))

  terurut.foreach((kata, hitung) => println(s"$kata: $hitung"))

# menjalankan program pipeline.scala
scala-cli run pipeline.scala

data: 2
dan: 1
diolah: 1
informasi: 1
koleksi: 1
menjadi: 1
menyimpan: 1
scala: 1

Kalimat dipecah menjadi kata dengan split(" ").toList, dikelompokkan dengan groupBy(identity), diringkas dengan view.mapValues, lalu diurutkan dengan sortBy((kata, hitung) => (-hitung, kata)). Kunci pengurutannya adalah frekuensi menurun, disusul kata menaik, sehingga kata yang muncul dua kali tampil paling atas dan kata-kata dengan frekuensi yang sama tampil menurut abjad. Fungsi identity adalah fungsi yang mengembalikan argumennya apa adanya, sehingga pengelompokannya dilakukan menurut kata itu sendiri.

Ringkasan#

• foldLeft melipat koleksi dari kiri dengan nilai awal yang eksplisit, dan akumulatornya boleh bertipe apa pun.
• reduce berjalan tanpa nilai awal sehingga hanya sah pada koleksi yang berisi, dan koleksi kosong membuat program berhenti dengan UnsupportedOperationException.
• groupBy menghasilkan Map berisi kelompok, peringkasannya ditulis dengan view.mapValues, dan urutan iterasinya wajib diatur sebelum dicetak.
• Pipeline agregasi yang diakhiri sorted atau sortBy menghasilkan keluaran yang teratur dan dapat direproduksi.

Referensi#

• Collections Overview — Scala Documentation — Ringkasan operasi pelipatan dan agregasi pada pustaka koleksi bawaan.
• List — Scala Standard Library — Dokumentasi API foldLeft, reduce, reduceOption, dan groupBy pada List.
• View — Scala Standard Library — Dokumentasi API View yang menjadi dasar padanan mapValues yang disarankan.