Agregasi dengan fold

Fold dan reduce sebagai pola konsumsi umum untuk membangun hasil dari kumpulan data.

Daftar isi

Fold adalah pola konsumsi koleksi yang mengalirkan setiap elemen ke dalam sebuah akumulator (accumulator) hingga tersisa satu hasil akhir. Topik ini membahas List.fold beserta arah akumulatornya, contoh nyata berupa rekap nilai ujian, penghitung kata, dan penerjemahan angka ke teks, dilanjutkan List.reduce serta List.foldBack, dan ditutup dengan posisi fold sebagai pola konsumsi umum di atas fungsi koleksi lainnya.

List.fold dengan akumulator#

List.fold menerima tiga hal secara berurutan, yaitu fungsi dua argumen, nilai awal akumulator, dan listnya. Signature lengkapnya adalah ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State, yang berarti tipe akumulator boleh berbeda dari tipe elemen. Fungsi tersebut dipanggil sekali per elemen dari kiri ke kanan, dengan argumen pertama berupa akumulator terkini dan argumen kedua berupa elemen yang sedang diproses, lalu nilai baliknya menjadi akumulator untuk langkah berikutnya.

fsharp fold-total.fsx

// List.fold mengalirkan setiap elemen ke dalam akumulator
let nilai = [ 80; 45; 75; 90; 60 ]

let total = List.fold (fun acc x -> acc + x) 0 nilai
printfn "total : %d" total

// akumulator berupa pasangan: jumlah dan banyaknya elemen
let jumlah, banyak = List.fold (fun (s, c) x -> (s + x, c + 1)) (0, 0) nilai
printfn "rata-rata : %f" (float jumlah / float banyak)

text Keluaran

total : 350
rata-rata : 70.000000

Perhitungan total berjalan sebagai rangkaian berikut, yaitu 0 lalu 0 + 80 = 80, 80 + 45 = 125, 125 + 75 = 200, 200 + 90 = 290, dan berakhir di 290 + 60 = 350. Nilai awal 0 menjamin hasil tetap sah pada list kosong, karena tanpa satu pun elemen, fold langsung mengembalikan akumulator awalnya. Contoh kedua memperlihatkan kekuatan signature yang bebas, yaitu akumulator berupa pasangan (s, c) yang menghitung jumlah sekaligus banyaknya elemen, sehingga rata-rata diperoleh tanpa menjalankan penelusuran kedua kalinya. Bentuk perhitungan semacam ini mengubah penghitung yang biasanya ditulis dengan mutable menjadi aliran nilai murni.

Putaran	acc sebelum	elemen	acc sesudah
1	0	80	80
2	80	45	125
3	125	75	200
4	200	90	290
5	290	60	350

Tabel di atas memperlihatkan jalannya akumulator pada perhitungan total dari awal hingga akhir. Setiap baris hanya bergantung pada baris sebelumnya dan satu elemen baru, sehingga perilaku fold dapat diperiksa per langkah tanpa membaca seluruh program. Sifat berurutan inilah yang menjadikan fold mudah ditelusuri pada data kecil sebelum dipercaya pada data yang lebih besar.

Penghitung kata dengan fold#

Aplikasi fold yang umum adalah membangun struktur agregat dari data mentah, dan penghitung kata merupakan contohnya. Masukannya berupa list baris, yang diratakan menjadi list kata dengan List.collect, lalu diproses dengan List.fold menjadi Map<string, int> yang memetakan setiap kata ke banyaknya kemunculannya. Akumulator pada contoh ini berupa Map kosong di awal dan bertumbuh sepanjang penelusuran.

fsharp fold-kata.fsx

// Penghitung kata: fold membangun Map dari daftar kata
let baris = [ "belanja beras"; "belanja telur"; "cuci sepatu"; "belanja beras" ]

let kata =
    baris
    |> List.collect (fun s -> s.Split(' ') |> List.ofArray)
    |> List.fold (fun tabel k ->
        let n = tabel |> Map.tryFind k |> Option.defaultValue 0
        Map.add k (n + 1) tabel) Map.empty

// penelusuran Map.toSeq menghasilkan entri terurut menurut kunci
kata
|> Map.toSeq
|> Seq.map (fun (kunci, n) -> sprintf "%s: %d" kunci n)
|> String.concat ", "
|> printfn "rekap kata : %s"

text Keluaran

rekap kata : belanja: 3, beras: 2, cuci: 1, sepatu: 1, telur: 1

Setiap kata diperiksa dengan Map.tryFind, dan Option.defaultValue 0 menyediakan angka nol untuk kata yang belum pernah muncul, sehingga satu langkah Map.add cukup untuk menaikkan hitungannya. Penyajian akhirnya melalui Map.toSeq menampilkan entri terurut menurut kunci sebagaimana susunan pohon di dalam tipe tersebut, dengan belanja tiga kali dan beras dua kali sesuai isinya. Contoh ini menegaskan bahwa akumulator tidak terbatas pada angka, melainkan dapat berupa struktur apa pun yang diinginkan sebagai hasil akhir, dan perubahan aturan penghitungan cukup disunting pada satu fungsi fold saja tanpa menyentuh pembacaan data maupun pencetakan hasilnya.

Menerjemahkan angka ke teks dengan fold#

Fold juga cocok untuk menerjemahkan sebuah nilai menjadi teks, dan penerjemahan angka ke angka Romawi adalah contohnya. Masukannya berupa angka, sedangkan akumulatornya berupa pasangan sisa angka dan teks yang sudah tersusun. List pemrosesnya berisi pasangan nilai dan simbol yang diurutkan menurun, sehingga setiap langkah mengambil simbol sebanyak mungkin sebelum melanjutkan ke simbol berikutnya.

fsharp fold-angka.fsx

// Penerjemahan angka ke teks Romawi dengan fold
let tabel =
    [ (1000, "M"); (900, "CM"); (500, "D"); (400, "CD")
      (100, "C"); (90, "XC"); (50, "L"); (40, "XL")
      (10, "X"); (9, "IX"); (5, "V"); (4, "IV"); (1, "I") ]

let keRomawi angka =
    List.fold (fun (sisa, teks) (v, s) ->
        let banyak = sisa / v
        (sisa - banyak * v, teks + String.replicate banyak s)) (angka, "") tabel
    |> snd

printfn "%s" (keRomawi 2026)
printfn "%s" (keRomawi 75)
printfn "%s" (keRomawi 4)

text Keluaran

MMXXVI
LXXV
IV

Pada angka 2026, langkah pertama membagi sisa dengan 1000 sehingga diperoleh dua simbol M, lalu sisa 26 melewati entri ratusan sampai 10 yang menghasilkan XX, dan diakhiri V beserta I. Hasilnya MMXXVI tanpa satu pun percabangan khusus pada angka tertentu, karena seluruh aturan penerjemahan sudah terkandung dalam urutan entri tabelnya. Fungsi String.replicate mengulang simbol sesuai banyak bagiannya, dan snd mengambil teks dari pasangan akumulator pada akhir penelusuran. Pemisahan antara tabel dan proses membuat penambahan simbol baru cukup dilakukan pada list tanpa mengubah fungsi foldnya sama sekali.

List.reduce dan List.foldBack#

List.reduce adalah bentuk fold tanpa nilai awal yang fungsi duanya bertipe 'T -> 'T -> 'T, sehingga tipe hasilnya sama dengan tipe elemennya. Elemen pertama bertindak sebagai akumulator awal, dan fungsi diterapkan berpasangan sampai habis. List.foldBack berpasangan dengan List.fold, tetapi menelusuri list dari kanan ke kiri dengan akumulator yang mengalir ke arah sebaliknya.

fsharp reduce-foldback.fsx

// List.reduce memakai elemen pertama sebagai akumulator awal
printfn "%d" (List.reduce (+) [ 1..5 ])
printfn "%s" (List.reduce (fun a b -> a + "-" + b) [ "a"; "b"; "c" ])

// arah akumulasi membedakan fold dan foldBack
let digit = [ 1; 2; 3 ]
printfn "%s" (List.fold (fun acc d -> string d + acc) "" digit)
printfn "%s" (List.foldBack (fun d acc -> string d + acc) digit "")

text Keluaran

15
a-b-c
321
123

Dua baris pertama memperlihatkan List.reduce pada penjumlahan dan penyambungan teks dengan pemisah, dan keduanya tidak memerlukan nilai awal karena tipe elemennya sudah mencukupi. Dua baris terakhir menyusun teks dari digit yang sama menggunakan fungsi yang mirip, tetapi hasilnya berkebalikan. List.fold menempelkan setiap digit di depan akumulator sehingga digit terakhir berada paling depan, sedangkan List.foldBack memproses dari kanan sehingga teksnya tersusun sesuai urutan asli list. Pemilihan arah ini penting pada operasi yang hasilnya bergantung pada urutan, sedangkan operasi seperti penjumlahan memberikan hasil yang sama pada kedua arah.

Fold sebagai pola konsumsi umum#

Fungsi-fungsi koleksi yang sudah dikenal sebenarnya dapat dituliskan kembali di atas fold, dan List.filter adalah contohnya. Akumulator menampung elemen lolos predikat, lalu urutannya dipulihkan di akhir. Contoh berikut membandingkan hasil versi fold dengan fungsi bawaannya.

fsharp filter-dari-fold.fsx

// filter dapat dituliskan kembali di atas fold
let saring pred daftar =
    daftar
    |> List.fold (fun acc x -> if pred x then x :: acc else acc) []
    |> List.rev

printfn "%A" (saring (fun n -> n % 2 = 0) [ 1..6 ])
printfn "%A" (List.filter (fun n -> n % 2 = 0) [ 1..6 ])

text Keluaran

[2; 4; 6]
[2; 4; 6]

Kedua baris keluaran identik karena kedua penulisan menjalankan penyaringan yang sama, dan hal ini berlaku pula bagi map, sum, maupun length. Karena itu, fold diposisikan sebagai pola konsumsi paling umum, yaitu bentuk paling murni untuk menghabiskan koleksi demi membangun satu hasil. Dalam penulisan sehari-hari, fungsi bawaan tetap diutamakan ketika tersedia karena namanya menyatakan maksudnya secara langsung, sedangkan fold digunakan untuk agregasi yang tidak punya nama bawaan, seperti rata-rata berbobot maupun penghitung kata pada contoh di atas. Bentuk umum tersebut juga berlaku pada koleksi yang isinya belum diketahui lengkap, karena fold hanya menuntut kemampuan menelusuri elemen satu per satu. Padanan fold juga tersedia untuk koleksi lain, yaitu Array.fold dan Seq.fold, dengan mekanisme yang persis sama.

Ringkasan#

List.fold menerima fungsi dua argumen, nilai awal, dan list, lalu mengalirkan setiap elemen dari kiri ke kanan ke dalam akumulator yang tipenya bebas.
Akumulator dapat berupa pasangan, Map, maupun teks, sehingga rekap nilai, penghitung kata, dan penerjemahan angka ke teks ditulis dengan pola yang sama.
List.reduce menggunakan elemen pertama sebagai akumulator awal dan melempar exception pada list kosong, sedangkan List.foldBack menelusuri dari kanan ke kiri.
Fold adalah pola konsumsi paling umum di atas koleksi, dan fungsi bawaan seperti filter maupun map dapat dituliskan kembali di atasnya.

Referensi#

F# collection types — Microsoft Learn — Ringkasan koleksi bawaan F# beserta modul agregasinya.
Lists — Microsoft Learn — Dokumentasi resmi list F# yang menjadi sasaran List.fold, List.reduce, dan List.foldBack.
F# Language Reference — Microsoft Learn — Rujukan induk sintaks bahasa F# yang menaungi seluruh topik di jalur ini.