Folds and monoids

Bacaan tambahan:

Fold lagi

Kita telah melihat bagaimana mendefinisikan fungsi fold untuk list, tapi kita masi bisa membuatnya lebih umum sehingga bisa digunakan untuk tipe data lainnya.

Perhatikan tipe data binary tree berikut, yang menyimpan data di dalam node internal:

Mari kita buat sebuah fungsi untuk menghitung besarnya tree tersebut (banyaknya node):

Bagaimana dengan jumlah keseluruhan data dalam tree yang berisikan Integer?

Atau kedalaman sebuah tree?

Atau meratakan semua elemen di tree menjadi sebuah list?

Dapatkah kalian melihat polanya? Tiap fungsi di atas:

  1. menerima sebuah Tree sebagai input
  2. cocokkan pola pada Tree tersebut
  3. jika Empty, berikan hasil sederhana
  4. jika berisi Node:
    1. panggil dirinya sendiri secara rekursif di kedua subtree
    2. gabungkan hasil dari rekursif tersebut dengan data x untuk mendapatkan hasil akhir

Sebagai programer yang baik, kita harus selalu berjuang mengabstraksikan pola yang berulang. Mari kita generalisasi. Kita perlu menjadikan bagian-bagian dari contoh diatas sebagai parameter, yang berbeda dari contoh satu ke lainnya:

  1. Tipe hasil
  2. Jawaban untuk kasus Empty
  3. Cara untuk menggabungkan pemanggilan rekursifnya

Kita sebut tipe data yang terkandung di dalam tree sebagai a, dan tipe hasilnya sebagai b.

Sekarang kita bisa mendefinisikan treeSize, treeSum dan contoh lainnya dengan lebih sederhana. Mari kita lihat:

Kita juga bisa membuat fungsi fold tree baru dengan mudah:

Fold pada ekspresi

Di mana lagi kita telah melihat fold?

Ingat tipe ExprT dan fungsi eval dari tugas 5:

Hmm… terlihat familiar! Bagaimanakah bentuk fold untuk ExprT?

Sekarang kita bisa melakukan hal lain dengan mudah, seperti menghitung jumlah literal dalam sebuah ekspresi:

Fold secara umum

Intinya, kita bisa membuat sebuah fold untuk banyak tipe data (meski tidak semua). Fold dari tipe T akan menerima satu (higher-order) argumen untuk tiap konstruktor dari T, dan menjabarkan bagaimana mengubah nilai di dalam konstruktor tersebut menjadi nilai yang bertipe sama dengan tipe hasil akhirnya (dengan asumsi tiap rekursif tehadap T sudah di-fold ke hasil akhir tersebut). Hal ini menyebabkan fungsi-fungsi yang kita akan buat untuk T bisa diekspresikan dalam bentuk fold.

Monoid

Berikut adalah satu lagi type class yang patut kalian ketahui, yang terdapat di modul Data.Monoid:

(<>) didefinisikan sebagai sinonim untuk mappend (sejak GHC 7.4.1) karena menuliskan mappend cukup merepotkan.

Tipe yang merupakan anggota dari Monoid memiliki elemen spesialyang disebut mempty, dan sebuah operasi biner mappend (disingkat menjadi (<>)) yang menerima dua nilai dari tipe tersebut dan mengembalikan satu. mempty merupakan identitas untuk <>, dan <> bersifat asosiatif. Dengan kata lain, untuk semua x, y, and z,

  1. mempty <> x == x
  2. x <> mempty == x
  3. (x <> y) <> z == x <> (y <> z)

Asosiatif berarti kita bisa menulis seperti ini tanpa ambigu:

a <> b <> c <> d <> e

karena kita akan mendapatkan hal yang sama tidak peduli di mana kita meletakkan tanda kurung.

Ada pula mconcat, yang digunakan untuk menggabungkan nilai-nilaipada sebuah list.

Secara default, implementasi mconcat menggunakan foldr, tapi dia dimasukkan ke dalam kelas Monoid karena beberapa anggota Monoid mungkin saja memiliki implementasi yang lebih efisien.

Jika kalian perhatikan, monoid ada di mana-mana. Mari kita buat beberapa anggotanya sebagai latihan (semua ini sudah ada di pustaka bawaan).

List, dengan concatenation, merupakan sebuah monoid:

Bisa dilihat sebelumnya bahwa penjumlahan merupakan monoid pada bilangan bulat (atau bilangan rasional, atau bilangan riil..). Akan tetapi, begitu pula dengan perkalian! Jadi bagaimana? Kita tidak bisa membuat satu tipe menjadi dua anggota yang berbeda dari type class yang sama. Kita akan membuat dua buah newtype, satu untuk tiap anggota type class:

Perhatikan bahwa misalnya untuk menemukan product dari sebuah list Integer dengan menggunakan mconcat, kita harus mengubahnya dulu menjadi nilai-nilai bertipe Product Integer:

(Tentu contoh ini konyol karena kita bisa langsung menggunakan fungsi bawaan product, tapi pola seperti ini bisa berguna nantinya.)

Pair merupakan sebuah monoid selama komponen-komponennya juga monoid:

Tantangan: bisakah kalian membuat anggota Monoid untuk Bool? Ada berapa anggota berbeda?

Tantangan: bagaimana kalian membuat tipe fungsi sebagai anggota Monoid?