Tipe rekursif

Tipe rekursif (recursive type) adalah tipe yang definisinya menggunakan tipe itu sendiri sebagai bagian dari dirinya. List dan pohon (tree) adalah dua contoh yang paling sering ditemui, dan keduanya dapat dideklarasikan ulang dari nol hanya dengan kemampuan deklarasi data. Topik ini membangun list dan pohon biner sendiri, kemudian menunjukkan perilaku rekursif yang selalu menyertai keduanya. Setelah membacanya, fungsi yang menelusuri struktur data berantai dapat ditulis dengan mengikuti bentuk tipenya.

Definisi yang menggunakan dirinya sendiri#

Deklarasi tipe rekursif selalu tersusun dari dua macam kasus, yaitu kasus dasar yang tidak menggunakan tipe itu lagi dan kasus rekursif yang menggunakannya. Kasus dasar memberi titik berhenti, sedangkan kasus rekursif memberi pertumbuhan. Pola ini mirip dengan definisi bilangan asli pada matematika: nol adalah bilangan asli, dan penerus dari sebuah bilangan asli juga bilangan asli. Konstruktor tanpa field mengisi peran kasus dasar, sedangkan konstruktor yang membawa tipe itu kembali mengisi peran pertumbuhan.

Apabila kasus dasar tidak ada, tidak ada nilai berhingga yang dapat dibentuk, sehingga setiap penggunaannya berujung pada evaluasi yang tidak pernah berhenti. Karena itu, kasus dasar dirancang lebih dahulu sebelum kasus rekursifnya. Dua tipe berikut menunjukkan pola yang sama pada bentuk data yang berbeda, yaitu rantai satu arah untuk list dan percabangan dua arah untuk pohon biner.

List buatan sendiri#

List adalah struktur berantai satu arah, yaitu satu elemen yang diikuti sisa list. Deklarasi berikut menamai tipenya Deret a dengan dua alternatif, yaitu Kosong sebagai kasus dasar dan Ikut a (Deret a) sebagai kasus rekursif yang menyimpan satu elemen beserta sisanya. Parameter a membuat tipe ini generik, sehingga Deret Int dan Deret Char merupakan dua penerapan dari deklarasi yang sama.

-- List buatan sendiri: tipe rekursif paling sederhana
data Deret a
  = Kosong            -- kasus dasar
  | Ikut a (Deret a)  -- satu elemen beserta sisanya
  deriving (Show, Eq)

panjang :: Deret a -> Int
panjang Kosong        = 0
panjang (Ikut _ sisa) = 1 + panjang sisa

jumlah :: Num a => Deret a -> a
jumlah Kosong       = 0
jumlah (Ikut x sis) = x + jumlah sis

dariList :: [a] -> Deret a
dariList []     = Kosong
dariList (x:xs) = Ikut x (dariList xs)

main :: IO ()
main = do
  let belanja = Ikut 2 (Ikut 5 (Ikut 1 Kosong))
  print belanja
  print (panjang belanja)
  print (jumlah belanja)
  print (dariList "abc")

Ikut 2 (Ikut 5 (Ikut 1 Kosong))
3
8
Ikut 'a' (Ikut 'b' (Ikut 'c' Kosong))

Setiap fungsi menggunakan satu persamaan per konstruktor, yaitu persamaan Kosong untuk kasus dasar dan persamaan Ikut yang memanggil dirinya pada sisanya. Nilai Deret sendiri dibangun dengan menumpuk konstruktor, misalnya Ikut 2 (Ikut 5 (Ikut 1 Kosong)) yang menyatakan rantai tiga elemen yang berakhir di Kosong. Bentuk penulisan ini memperlihatkan struktur berantai secara harfiah, sehingga baris pertama keluaran program terbaca sebagai rantai dua, lima, satu. Fungsi dariList menerjemahkan list bawaan menjadi Deret, sehingga kedua struktur terbukti dapat dipertukarkan. Padanannya pada list bawaan sudah disediakan oleh laporan bahasa dengan definisi yang persis setara.

-- tidak-dijalankan
-- Sintaks khusus list bawaan yang tidak dapat dideklarasikan ulang:
data [a] = [] | a : [a]

Definisi di atas menjelaskan asal sintaksis [] dan (:), sehingga list bawaan tidak lain adalah tipe rekursif yang dikhususkan oleh laporan bahasa.

Pohon biner#

Pohon biner menumbuhkan struktur ke dua arah, yaitu setiap simpul menyimpan sebuah nilai beserta dua cabang yang bertipe pohon itu sendiri. Deklarasi berikut menamai tipenya Pohon a dengan alternatif Daun sebagai kasus dasar dan Simpul (Pohon a) a (Pohon a) sebagai kasus rekursif. Karena tipe itu sendiri muncul dua kali dalam konstruktor, setiap simpul menjadi akar dari dua subpohon.

-- Pohon biner: dua posisi rekursif pada setiap simpul
data Pohon a
  = Daun
  | Simpul (Pohon a) a (Pohon a)
  deriving (Show, Eq)

tinggi :: Pohon a -> Int
tinggi Daun                  = 0
tinggi (Simpul kiri _ kanan) = 1 + max (tinggi kiri) (tinggi kanan)

jumlah :: Num a => Pohon a -> a
jumlah Daun                  = 0
jumlah (Simpul kiri x kanan) = jumlah kiri + x + jumlah kanan

balik :: Pohon a -> Pohon a
balik Daun                   = Daun
balik (Simpul kiri x kanan)  = Simpul (balik kanan) x (balik kiri)

main :: IO ()
main = do
  let pohon = Simpul (Simpul Daun 2 Daun) 7 (Simpul Daun 1 Daun)
  print (tinggi pohon)
  print (jumlah pohon)
  print (balik pohon)

2
10
Simpul (Simpul Daun 1 Daun) 7 (Simpul Daun 2 Daun)

Fungsi tinggi mengambil nilai maksimum dari kedua cabang, sedangkan jumlah menjumlahkan tiga bagian simpul, yaitu subpohon kiri, nilai tengah, dan subpohon kanan. Fungsi balik menukar posisi kiri dan kanan pada setiap simpul secara rekursif, dan baris ketiga keluaran menunjukkan pohon yang sudah dicerminkan. Nilai tinggi bernilai dua, meskipun pohon itu memuat tiga simpul bernilai, karena kedalaman bukan jumlah simpul.

Dua posisi rekursif ini juga menjadikan pohon biner bentuk yang alami untuk ekspresi aritmetika, yaitu operator sebagai nilai simpul dan kedua operand sebagai cabang. Penelusuran pada pohon semacam itu mengikuti urutan pengerjaan hitungnya, sehingga banyak struktur program nyata dipetakan langsung ke bentuk ini. Struktur bawaan seperti Data.Map pada library containers juga dibangun di atas keluarga pohon yang sama, dengan tambahan penyeimbang agar kedalaman tetap terjaga.

Perilaku rekursif keduanya#

Tabel berikut membandingkan kedua tipe yang dibangun di atas.

Fungsi di atas tipe rekursif selalu mengikuti bentuk tipenya, yaitu satu persamaan per konstruktor dan pemanggilan ulang hanya pada posisi rekursifnya. Gaya ini disebut rekursi struktural (structural recursion), dan setiap fungsi yang mengikutinya dijamin berhenti pada nilai berhingga karena setiap pemanggilan menggunakan bagian yang lebih kecil dari nilai sebelumnya. Perbedaan biayanya terletak pada jumlah posisi rekursif: penelusuran list tumbuh linear terhadap jumlah elemen, sedangkan pohon menambah banyak simpul pada kedalaman yang sama melalui percabangannya. Perilaku inilah yang membuat pohon cocok untuk banyak data, sebab kedalaman pertumbuhannya jauh lebih lambat daripada jumlah simpulnya.

Kesalahan umum#

• Rekursi tanpa kasus dasar. Fungsi yang setiap persamaannya memanggil dirinya sendiri tidak pernah menghasilkan nilai, dan evaluasinya tidak berhenti. Perbaikannya adalah memastikan setiap jalur persamaan berakhir di kasus dasar, sebagaimana persamaan Kosong dan Daun pada program-program di atas.
• Nama tipe digunakan tanpa parameternya. Anotasi seperti panjang :: Deret -> Int ditolak compiler karena Deret masih kekurangan satu parameter tipe. Bentuk yang benar adalah Deret a, dan fungsi generik menuliskannya sebagai Deret a -> Int.
• Lupa klausa deriving. Fungsi print membutuhkan instans Show, sehingga deklarasi tanpa deriving (Show) menimbulkan pesan error tipe pada saat pencetakan. Tambahkan klausa deriving (Show) pada deklarasi tipe yang nilainya perlu dicetak.

Ringkasan#

• Tipe rekursif tersusun dari kasus dasar tanpa rekursi dan kasus rekursif yang menggunakan tipe itu sendiri.
• List adalah rantai satu arah dengan satu posisi rekursif, sedangkan pohon biner bercabang dua arah dengan dua posisi rekursif.
• Fungsi di atas tipe rekursif menggunakan satu persamaan per konstruktor dan hanya memanggil dirinya pada posisi rekursifnya.
• Rekursi struktural dijamin berhenti pada nilai berhingga karena setiap pemanggilan menggunakan bagian yang lebih kecil.

Referensi#

• Haskell 2010 Report, bab 4: Declarations and bindings — haskell.org — Bab deklarasi pada laporan bahasa resmi yang memuat bentuk deklarasi tipe rekursif dan sintaksis list bawaan.
• Algebraic data type — HaskellWiki — Penjelasan komunitas yang memuat contoh tipe rekursif seperti list dan pohon.