foldr dan foldl

Penjumlahan, perkalian, pencarian nilai maksimum, dan pembalikan list memiliki pola yang sama, yaitu memindai seluruh elemen list lalu merangkai hasilnya menjadi satu nilai. Pola tersebut diabstraksikan oleh fold, yaitu fungsi yang menerima penggabung, nilai awal, dan list yang diproses. Topik ini membahas foldr dan foldl, perbedaan arah pengolahannya, serta pertimbangan memilih varian yang tepat untuk kasus yang dihadapi.

Pola konsumsi struktur#

Pola konsumsi list paling mudah diamati dari definisi rekursif. Fungsi penjumlahan menangani dua kasus, yaitu list kosong yang menghasilkan nol dan pasangan kepala-ekor yang menjumlahkan kepala dengan hasil pengolahan ekornya. Fungsi perkalian mengikuti bentuk yang persis sama, dengan nol diganti satu dan penjumlahan diganti perkalian.

-- Konsumsi list dengan rekursi: kasus kosong dan kasus kepala-ekor
jumlahList :: [Int] -> Int
jumlahList []     = 0
jumlahList (x:xs) = x + jumlahList xs

kaliList :: [Int] -> Int
kaliList []     = 1
kaliList (x:xs) = x * kaliList xs

main :: IO ()
main = do
  print (jumlahList [1, 2, 3, 4])
  print (kaliList [1, 2, 3, 4])

10
24

Perbedaan kedua definisi hanya terletak pada fungsi penggabung dan nilai awalnya, sedangkan bentuk rekursinya identik. Bentuk tersebut sudah dikenal dari pembahasan list, yaitu setiap konsumen list menangani kasus kosong dan kasus kepala-ekor. Fold melengkapi dua bagian tersebut dengan dua argumen, yaitu nilai awal untuk kasus list kosong dan fungsi penggabung untuk kasus kepala-ekor. Karena bentuk rekursinya diserahkan kepada fungsi umum, pembaca definisi fold cukup menilai dua hal itu tanpa menulis rekursi lagi. Fungsi umum tersebut adalah fold, dan dua varian yang paling lazim adalah foldr dan foldl, sedangkan pola yang sama berlaku untuk tipe rekursif lain sehingga kebiasaan membacanya mudah dibawa ke struktur yang lebih besar.

foldr#

Fungsi foldr menggantikan peran konstruktor list dengan fungsi penggabung. Definisinya untuk list berbunyi foldr f z [] = z dan foldr f z (x:xs) = f x (foldr f z xs), artinya nilai z menggantikan [] dan f x (foldr f z xs) menggantikan x : xs. Dengan pembacaan tersebut, ekspresi foldr (+) 0 [1, 2, 3] terurai menjadi 1 + (2 + (3 + 0)), sehingga tanda kurungnya menumpuk di kanan dan itulah asal huruf r pada namanya.

-- foldr menyusun penggabungan elemen dengan nilai awal
jumlah :: [Int] -> Int
jumlah = foldr (+) 0

kali :: [Int] -> Int
kali = foldr (*) 1

-- Elemen diabaikan, akumulator ditambah satu
panjang :: [a] -> Int
panjang = foldr (\_ acc -> acc + 1) 0

main :: IO ()
main = do
  print (jumlah [1, 2, 3, 4])
  print (kali [1, 2, 3, 4])
  print (panjang "haskell")
  print (foldr (:) [] [1, 2, 3])

10
24
7
[1,2,3]

Baris terakhir keluaran memperlihatkan sifat yang mendasar, yaitu penggabungan elemen dengan konstruktor : dan nilai awal [] menghasilkan list yang sama persis dengan list asalnya. Dengan kata lain, foldr mampu membangun kembali struktur yang dipindainya, sehingga fungsi jumlah, kali, dan panjang hanyalah kasus khusus dari satu pola yang sama. Lambda pada panjang, yaitu fungsi anonim \ _ acc -> acc + 1, mengabaikan elemennya dan menambah satu pada akumulator.

Evaluasi lazy membuat foldr mampu berhenti lebih awal. Apabila penggabungnya tidak selalu meminta hasil rekursinya, pemindaian berhenti pada elemen terakhir yang benar-benar diperlukan. Perintah berikut mengambil elemen pertama dari list tak hingga melalui foldr, dan sisanya tidak pernah dihitung.

# ambil elemen pertama list tak hingga melalui foldr
ghc -e 'foldr (\x _ -> x) 0 [1 ..]'

1

foldl dan foldl'#

Fungsi foldl memindai list dari kiri dan menyimpan hasil sementara pada akumulator (accumulator), yaitu nilai yang terus diperbarui setiap langkah. Definisinya berbunyi foldl f z [] = z dan foldl f z (x:xs) = foldl f (f z x) xs, sehingga penggabung diterapkan pada akumulator terlebih dahulu sebelum elemen berikutnya diproses. Ekspresi foldl (+) 0 [1, 2, 3] terurai menjadi ((0 + 1) + 2) + 3, dengan tanda kurung menumpuk di kiri.

-- foldl mengolah akumulator lebih dahulu, baru elemen berikutnya
import Data.List (foldl')

jumlah :: [Int] -> Int
jumlah = foldl' (+) 0

terbalik :: [a] -> [a]
terbalik = foldl (\acc x -> x : acc) []

main :: IO ()
main = do
  print (jumlah [1, 2, 3, 4])
  print (terbalik [1, 2, 3])
  print (foldl (-) 10 [1, 2, 3])
  print (foldr (-) 10 [1, 2, 3])

10
[3,2,1]
4
-8

Baris ketiga dan keempat keluaran menunjukkan perbedaan arah secara nyata. Ekspresi foldl (-) 10 [1, 2, 3] menghitung ((10 - 1) - 2) - 3 sehingga hasilnya 4, sedangkan foldr (-) 10 [1, 2, 3] menghitung 1 - (2 - (3 - 10)) sehingga hasilnya -8. Apabila pengurangan diganti penjumlahan, keduanya memberikan hasil yang sama karena penjumlahan bersifat asosiatif. Pembalikan list pada program tersebut memanfaatkan arah kiri foldl, yaitu setiap elemen disisipkan di depan akumulator hingga list asal terbalik.

Memilih arah fold#

Pilihan arah fold menentukan hasil dan kelayakan penggunaannya. Tabel berikut merangkum ketiga varian yang tersedia pada library standar.

Tiga pertimbangan praktis menyertai tabel tersebut. Pertama, pada penggabung yang tidak asosiatif seperti pengurangan, arah pemindaian mengubah hasil, sehingga arahnya harus dipilih secara sadar. Kedua, untuk list panjang dengan akumulator sederhana, foldl' dipilih demi hemat memori. Ketiga, untuk hasil berupa list atau struktur yang menyertai elemen terakhir, foldr dipilih karena rekonstruksinya mengikuti bentuk list. Fungsi standar seperti sum, product, maximum, dan reverse merupakan spesialisasi dari pola ini, sehingga fold yang ditulis manual hanya diperlukan untuk penggabung khusus.

Kesalahan umum#

Kesalahan pertama adalah menukar urutan parameter pada lambda penggabung. Tipe foldr untuk list menuntut penggabung bertipe a -> b -> b, artinya elemen diterima lebih dahulu dan akumulator menyusul. Perintah berikut menerapkan penggabung penyambungan dengan akumulator awal [9], dan hasilnya menunjukkan setiap elemen disambung sebelum akumulator.

# elemen diterima lebih dahulu, baru akumulator [9]
ghc -e 'foldr (\x acc -> x : acc) [9] [1, 2, 3]'

[1,2,3,9]

Nilai [9] muncul di ujung hasil karena posisinya sebagai akumulator awal, sedangkan elemen [1, 2, 3] disambung satu per satu di depannya. Lambda yang parameternya tertukar tidak selalu ditolak compiler, sebab penggabung bertipe sederhana seperti Int -> Int -> Int tetap lolos pemeriksaan tipe, tetapi semantiknya berubah dan hasilnya keliru. Kesalahan kedua adalah menggunakan foldl untuk list panjang dengan akumulator sederhana. Perhitungan yang tertunda menumpuk pada akumulator sebagaimana ditegaskan pada peringatan di atas, sehingga foldl' menjadi pilihan yang lebih aman untuk kasus tersebut.

Ringkasan#

• Fold merangkum pola memindai list menjadi satu fungsi yang menerima penggabung, nilai awal, dan list.
• foldr menggantikan konstruktor list dengan penggabung dan nilai awal, sehingga tanda kurung menumpuk di kanan dan pemindaian dapat berhenti lebih awal pada list tak hingga.
• foldl memperbarui akumulator dari kiri, sedangkan foldl' dari Data.List menghitung akumulator setiap langkah untuk menghindari penumpukan perhitungan tertunda.
• Pada penggabung yang tidak asosiatif seperti pengurangan, arah fold menentukan hasil akhirnya.

Referensi#

• Haskell 2010 Language Report, Bab 9 — haskell.org — Definisi foldr dan foldl pada spesifikasi resmi bahasa.
• Data.List — Hackage — Dokumentasi foldl' dan fungsi list lainnya pada library standar base.
• Foldr/Foldl/Foldl’ — Haskell Wiki — Perbandingan perilaku ketiga varian fold beserta akibat memorinya.