KAL
Menu

map dan filter

Dua fungsi orde tinggi keseharian untuk memetakan dan menyaring list.

Daftar isi

Fungsi orde tinggi (higher-order function) adalah fungsi yang menerima fungsi lain sebagai argumen atau menghasilkan fungsi sebagai nilainya. Topik ini membahas dua fungsi orde tinggi yang paling sering digunakan sehari-hari, yaitu map untuk memetakan setiap elemen list dan filter untuk menyaring elemen yang memenuhi syarat. Setelah membacanya, transformasi list yang pada bahasa imperatif ditulis sebagai perulangan dapat dinyatakan dengan satu ekspresi, dan alasan kedua fungsi tersebut bekerja pada list tak hingga dapat dijelaskan.

Fungsi orde tinggi pada list#

Kemampuan menerima fungsi sebagai argumen berakar pada status fungsi sebagai nilai kelas satu, sehingga fungsi diteruskan ke fungsi lain sebagaimana nilai biasa. Tipe map untuk list adalah (a -> b) -> [a] -> [b], yaitu menerima fungsi dari a ke b, menerima list dari a, dan menghasilkan list dari b. Tipe filter adalah (a -> Bool) -> [a] -> [a], yaitu menerima fungsi penentu lolos atau tidak, menerima list, dan menghasilkan list bertipe sama. Fungsi bertipe a -> Bool yang diberikan kepada filter disebut predikat (predicate).

Anotasi tipe tersebut sekaligus menjadi kontrak hasil. map selalu menghasilkan list dengan panjang sama dengan list asal dan urutan elemen yang tidak berubah, sedangkan filter menghasilkan list yang panjangnya nol hingga sebanyak list asal tergantung banyaknya elemen yang lolos. Karena keduanya hanya menyusun list baru tanpa menyentuh list asal, keduanya mengikuti sifat data immutable yang berlaku di seluruh bahasa.

Kedua fungsi terdapat pada Prelude, sehingga dapat digunakan tanpa pernyataan impor sebagaimana fungsi list bawaan lainnya. Aturan hasil yang tetap itu memudahkan penalaran, yaitu bentuk map f xs dan filter p xs selalu bertipe list, sehingga hasilnya dapat langsung dipasangkan dengan fungsi list lain tanpa konversi.

Memetakan list dengan map#

Fungsi map menerapkan satu fungsi kepada setiap elemen list dan mengumpulkan hasilnya dalam list baru. Argumen fungsinya dapat berupa fungsi bernama sebagaimana duaKali pada program berikut, fungsi bawaan seperti abs, maupun fungsi yang mengubah tipe elemen seperti show. Program berikut memperlihatkan ketiga bentuk tersebut sekaligus keutuhan list asal setelah pemetaan.

haskell peta-nilai.hs 
-- map menghasilkan list baru, sedangkan list asal tetap utuh
angka :: [Int]
angka = [3, 1, 4]

duaKali :: Int -> Int
duaKali n = n * 2

main :: IO ()
main = do
  print (map duaKali angka)
  print angka
  print (map abs [-3, -1, 4])
  print (map show [10, 20, 30])
text Keluaran 
[6,2,8]
[3,1,4]
[3,1,4]
["10","20","30"]

Baris pertama keluaran menunjukkan hasil pemetaan, sedangkan baris kedua menunjukkan list angka yang tidak berubah setelah map dijalankan. Pemetaan tidak menimpa elemen lama, melainkan menyusun list baru dari hasil setiap penerapan fungsi. Baris terakhir memperlihatkan perubahan tipe yang sah, yaitu map show [10, 20, 30] mengubah list Int menjadi list String karena tipe map memang mengizinkan a dan b berbeda.

Pemetaan yang sama dapat ditulis dengan rekursi, yaitu memetakan kepala list lalu menyambung hasilnya dengan pemetaan atas ekornya. Bentuk rekursif seperti itu begitu sering muncul sehingga map mengabstraksinya menjadi satu fungsi tunggal. Apabila ekspresi map duaKali angka dibaca, panjang list yang tetap dan pemrosesan yang seragam langsung dipahami tanpa membaca definisinya.

Menyaring list dengan filter#

Fungsi filter menyimpan elemen yang lolos predikat dan membuang sisanya, dengan urutan elemen tetap dipertahankan. Predikat menerima satu elemen dan menghasilkan Bool, sehingga seluruh elemen diperiksa dengan pertanyaan yang sama. Program berikut menyaring bilangan genap, menyaring nilai yang lebih besar dari tiga dengan section (> 3), dan menyaring sub-list yang kosong dengan fungsi null.

haskell saring-genap.hs 
-- filter menyimpan elemen yang lolos predikat
genap :: Int -> Bool
genap n = n `mod` 2 == 0

main :: IO ()
main = do
  print (filter genap [1 .. 10])
  print (filter (> 3) [1, 2, 3, 4, 5])
  print (filter null [[1, 2], [], [3], []])
text Keluaran 
[2,4,6,8,10]
[4,5]
[[],[]]

Keluaran ketiga menegaskan bahwa predikat boleh bekerja pada tipe apa pun selama menerima satu elemen list dan menghasilkan Bool. Fungsi null bertipe [a] -> Bool, sehingga sub-list kosong pada list [1, 2], [], [3], [] dapat disaring dan hanya yang kosong yang tersisa. Apabila tidak ada elemen yang lolos, filter menghasilkan list kosong, sehingga hasil penyaringan tetap bertipe list dan dapat langsung diproses fungsi lain.

Penyaringan dengan filter menggantikan perulangan yang di dalamnya terdapat percabangan untuk memilih elemen. Pembacaan filter genap xs menyatakan maksudnya secara langsung, sedangkan detail pemeriksaan satu per satu diserahkan kepada fungsi standar. Pendekatan ini mengurangi kemungkinan salah urutan dan menjaga maksud kode tetap terbaca dari namanya.

Merangkai map dan filter#

Kombinasi kedua fungsi memenuhi sebagian besar kebutuhan pengolahan list harian. Pola yang lazim adalah menyaring dahulu, lalu memetakan hasilnya, sebagaimana program berikut yang memisahkan nilai ujian yang lulus dan menghitung nilai remedial.

haskell nilai-lulus.hs 
-- map dan filter dirangkai: saring dahulu, lalu petakan hasilnya
nilai :: [Int]
nilai = [45, 58, 72, 60, 91]

lulus :: Int -> Bool
lulus n = n >= 60

remedi :: Int -> Bool
remedi n = n < 60

naikkan :: Int -> Int
naikkan n = n + 5

main :: IO ()
main = do
  print (filter lulus nilai)
  print (map naikkan (filter remedi nilai))
  print (length (filter lulus nilai))
text Keluaran 
[72,60,91]
[50,63]
3

Ekspresi map naikkan (filter remedi nilai) dibaca dari dalam ke luar, yaitu penyaringan dihitung lebih dahulu, lalu hasilnya dipetakan. Karena filter menghasilkan list baru, map dapat langsung dipasangkan tanpa variabel sementara. Apabila hasil sementara perlu digunakan lebih dari satu kali, memberi nama padanya melalui where lebih jelas daripada menghitung ulang, sebagaimana filter lulus nilai yang pada program di atas dipanggil dua kali untuk keperluan cetak dan penghitungan. Rantai yang lebih panjang tetap ditulis dengan cara yang sama, dan notasi komposisi yang merapikannya dibahas pada topik komposisi dan gaya point-free.

List tak hingga tidak menghalangi pola ini. Evaluasi lazy membuat map dan filter berhenti segera setelah kebutuhan hasil terpenuhi, sebagaimana perintah berikut yang memetakan list tanpa batas lalu mengambil tiga elemen pertamanya.

bash 
# petakan list tak hingga, lalu ambil tiga elemen pertamanya
ghc -e 'take 3 (map (* 2) [1 ..])'
# jumlahkan kuadrat lima bilangan pertama
ghc -e 'sum (map (^ 2) [1 .. 5])'
text Keluaran 
[2,4,6]
55

Kesalahan umum#

Kesalahan yang sering terjadi adalah meneruskan fungsi dua argumen kepada map, misalnya map (+) [1, 2, 3] dengan harapan menghasilkan angka. Operator + bertipe a -> a -> a, sehingga penerapannya pada satu elemen menghasilkan fungsi, bukan angka. Perintah berikut menunjukkan tipe hasilnya.

bash 
# tipe hasil penerapan map pada operator dua argumen
ghc -e ':t map (+) [1, 2, 3]'
text Keluaran 
map (+) [1, 2, 3] :: Num a => [a -> a]

Tipe [a -> a] menyatakan list berisi fungsi, bukan list berisi angka. Perbaikannya bergantung pada maksudnya, yaitu map (+ 10) [1, 2, 3] apabila setiap elemen perlu ditambah sepuluh, atau fungsi bernama apabila perhitungannya lebih rumit. Kesalahan kedua adalah mengira map dan filter mengubah list asalnya. Kedua fungsi selalu menghasilkan list baru, sehingga hasilnya perlu diberi nama atau langsung digunakan pada ekspresi berikutnya. Kesalahan ketiga adalah menerapkan map dua kali untuk perhitungan yang sebenarnya dapat digabung menjadi satu fungsi, misalnya map f (map g xs). Hasilnya benar, tetapi list perantara dibangun dua kali, sehingga kedua pemetaan itu lebih baik digabung menjadi satu fungsi atau dirapikan dengan komposisi.

Ringkasan#

  • map menerapkan satu fungsi ke setiap elemen list dan menghasilkan list baru dengan panjang dan urutan yang tetap, sedangkan tipe elemennya boleh berubah.
  • filter menyimpan elemen yang lolos predikat a -> Bool dan menghasilkan list bertipe sama dengan list asalnya.
  • Kedua fungsi dapat dirangkai karena sama-sama menghasilkan list, dan evaluasi lazy membuat rangkaiannya bekerja pada list tak hingga.
  • Fungsi dua argumen yang diteruskan ke map menghasilkan list berisi fungsi, sehingga bentuk aplikasi parsial seperti (+ 10) biasanya yang dimaksud.

Referensi#