KAL
Menu

Struktur tak hingga

Range, siklus, dan algoritme pada stream tak hingga.

Daftar isi

Keanggunan evaluasi lazy paling terlihat pada struktur data yang tidak pernah selesai. Haskell memungkinkan sebuah list didefinisikan tanpa batas karena elemennya baru dihitung saat diminta, dan struktur semacam ini lazim disebut stream, yaitu list yang dihasilkan secara bertahap. Topik ini membahas cara membuat stream tak hingga dengan range dan fungsi pembangkit, cara mengambil sebagiannya, serta dua algoritme klasik yang merujuk pada dirinya sendiri. Setelah membacanya, stream dapat ditulis dengan aman, lengkap dengan batasan yang menyertainya.

Range tanpa batas#

Notasi range tanpa batas atas menghasilkan list yang tak pernah habis. Notasi range dengan batas atas sudah dikenal dari pembahasan list, dan penggunaan di sini hanya menghilangkan batasnya. Yang berbeda bukan penulisannya, melainkan akibat evaluasi lazy, yaitu elemen dihitung satu per satu sesuai permintaan sehingga list yang mencakup seluruh bilangan asli tetap dapat dioperasikan.

haskell stream-dasar.hs 
-- Range tanpa batas atas menghasilkan list tak hingga
genap :: [Int]
genap = [2, 4 ..]

main :: IO ()
main = do
  print (take 6 genap)
  print (take 5 [1 ..])
  print (take 3 (drop 10 [1 ..]))
text Keluaran 
[2,4,6,8,10,12]
[1,2,3,4,5]
[11,12,13]

Fungsi take mengambil sejumlah elemen pertama, sedangkan drop melewati sejumlah elemen pertama tanpa menghitung sisanya. Keduanya berhenti segera setelah jumlah yang diminta terpenuhi, sehingga tidak ada bagian tak hingga yang benar-benar dihitung. Fungsi pengambil sebagian seperti ini menjadi pasangan wajib bagi setiap stream, dan konsumen yang tidak berhenti dibahas pada bagian kesalahan umum.

repeat, cycle, dan iterate#

Selain range, pustaka standar menyediakan tiga fungsi pembangkit yang membentuk pola berbeda. Fungsi repeat menghasilkan nilai yang sama terus-menerus, cycle mengulang list hingga secara periodik, dan iterate menerapkan satu fungsi berulang kali pada nilai awalnya. Ketiganya lazim digunakan sebagai sumber list tak hingga bagi fungsi orde tinggi seperti map dan zipWith.

haskell siklus.hs 
-- repeat, cycle, dan iterate menghasilkan list tak hingga
satu :: [Int]
satu = repeat 1

pola :: [Int]
pola = cycle [1, 2, 3]

duaPangkat :: [Int]
duaPangkat = iterate (* 2) 1

main :: IO ()
main = do
  print (take 4 satu)
  print (take 7 pola)
  print (take 6 duaPangkat)
text Keluaran 
[1,1,1,1]
[1,2,3,1,2,3,1]
[1,2,4,8,16,32]

Keluaran tersebut memperlihatkan tiga pola, yaitu pengulangan satu nilai, pengulangan periodik [1, 2, 3], dan rangkaian dua pangkat yang dihasilkan dari (* 2) yang diterapkan berulang-ulang. Fungsi cycle memerlukan list hingga yang tidak kosong karena list kosong tidak memiliki pola untuk diulang. Error akibat list kosong baru muncul ketika elemen pertamanya diminta, bukan ketika cycle ditulis, sebagaimana sifat evaluasi tertunda pada umumnya.

Menyandingkan stream dengan list hingga#

Fungsi zipWith menyandingkan dua list elemen demi elemen dan berhenti pada list yang lebih pendek. Sifat ini memungkinkan stream tak hingga dipasangkan dengan list hingga tanpa memunculkan error, karena kelebihan panjang pada sisi stream tidak pernah disentuh. Pola yang paling sering digunakan adalah memberikan nomor urut pada list hingga.

haskell bernomor.hs 
-- zipWith menyandingkan penghitung tak hingga dengan list hingga
bernomor :: [String] -> [String]
bernomor = zipWith (\n s -> show n ++ ". " ++ s) [1 ..]

daftar :: [String]
daftar = ["beras", "telur", "minyak"]

main :: IO ()
main = mapM_ putStrLn (bernomor daftar)
text Keluaran 
1. beras
2. telur
3. minyak

Penghitung [1 ..] tidak pernah habis, tetapi zipWith berhenti bersamaan dengan habisnya daftar. Fungsi lambda menyambung nomor dan isinya menjadi satu string, lalu hasilnya dicetak baris demi baris. Pola ini bekerja untuk list apa pun tanpa perlu menghitung panjangnya terlebih dahulu, dan penghitung yang tersisa di sisi stream tidak pernah dibuat.

Algoritme yang merujuk pada dirinya sendiri#

Definisi list yang merujuk pada dirinya sendiri mungkin dilakukan karena thunk dan sharing. Deret Fibonacci pada program berikut didefinisikan sebagai list 0 : 1 : zipWith (+) fibs (tail fibs), artinya setiap elemen baru adalah penjumlahan dua elemen dari list yang sedang dibangun itu sendiri. Definisi ini sah karena zipWith hanya menuntut elemen yang sudah tersedia, sedangkan sharing memastikan setiap elemen dihitung satu kali dan hasilnya digunakan oleh kedua rujukan.

haskell fibs-dan-prima.hs 
-- Deret Fibonacci merujuk pada dirinya sendiri
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- Ayak Eratosthenes versi lazy
sieve :: [Integer] -> [Integer]
sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

prima :: [Integer]
prima = sieve [2 ..]

main :: IO ()
main = do
  print (take 10 fibs)
  print (take 10 prima)
text Keluaran 
[0,1,1,2,3,5,8,13,21,34]
[2,3,5,7,11,13,17,19,23,29]

Fungsi sieve menerapkan pola yang sama pada ayak Eratosthenes. Elemen pertama dipastikan prima, seluruh kelipatannya disaring dari ekor list, lalu proses yang sama diterapkan pada sisanya. Rujukan prima = sieve [2 ..] mengubah ayak tersebut menjadi stream prima yang dapat diambil sebagian dengan take.

Ayak versi lazy ini menyimpan setiap prima yang ditemukan sebagai penguji kelipatan pada tahap berikutnya, sehingga jumlah pemeriksaan per elemen bertambah seiring bertambahnya prima. Ayak ini tetap tepat untuk pengambilan yang pendek, sedangkan kebutuhan pada skala besar lazimnya dipenuhi dengan struktur data khusus yang lebih hemat.

Kesalahan umum#

Kesalahan yang paling sering terjadi adalah memanggil konsumen penuh pada stream. Fungsi sum, product, maximum, dan length harus memindai seluruh list sebelum menghasilkan nilainya, sehingga pemanggilan seperti sum [1 ..] tidak pernah selesai dan program tampak menggantung tanpa pesan apa pun.

Perbaikannya adalah membatasi stream terlebih dahulu, baik dengan take maupun dengan mengganti sumbernya menjadi range berbatas. Kesalahan kedua adalah mendefinisikan deret rujukan-diri tanpa nilai awal. Ekspresi fibs = zipWith (+) fibs (tail fibs) tanpa benih 0 : 1 : tidak memiliki elemen pertama untuk dihitung, sehingga hasilnya tidak pernah terbentuk. Benih itulah yang memicu seluruh rantai perhitungan, sehingga definisi rujukan-diri selalu disertai benih yang cukup.

Ringkasan#

  • Range tanpa batas atas beserta repeat, cycle, dan iterate menghasilkan stream yang elemennya dihitung sesuai permintaan.
  • take dan drop mengambil bagian stream tanpa menyentuh sisanya, sedangkan zipWith berhenti pada list yang lebih pendek.
  • Deret Fibonacci dan ayak Eratosthenes dapat dibuat karena sharing thunk, dengan syarat benih nilai awal tersedia.
  • Konsumen penuh seperti sum dan length tidak pernah selesai pada stream, sehingga stream harus dibatasi terlebih dahulu.

Referensi#