Apakah Banana split dan fusion dalam pemrograman fungsional?

22

Istilah-istilah ini disebutkan dalam kursus universitas saya. Googling cepat mengarahkan saya ke beberapa makalah universitas, tetapi saya mencari penjelasan sederhana.

functional-programming haskell Gaurav Abbi
sumber
@jozefg: Terima kasih atas tautan ke pos Anda. Satu pertanyaan tentang itu. Dalam kalimat "Aljabar dalam pengertian ini adalah sepasang objek C, dan peta FC → C.", apakah C benar-benar seharusnya menjadi objek, atau lebih tepatnya sebuah kategori? Dengan kata lain, saya tidak yakin apakah F menunjukkan functor dalam suatu kategori, dan F-aljabar adalah aljabar yang diinduksi oleh functor itu, jika F adalah panah tertentu dari suatu objek ke dirinya sendiri.
Giorgio
Cadalah objek dalam beberapa kategori (katakanlah CC), Fadalah functor dari CC -> CCsehingga memetakan CCkembali ke dirinya sendiri. Sekarang F CC -> CChanya panah normal dalam kategori ini CC. Jadi Faljabar adalah objek C : CCdan panah F C -> CdiCC
Daniel Gratzer

Jawaban:

4

Meskipun 2 jawaban sudah diberikan, saya kira "pisang split" belum dijelaskan di sini.

Ini memang didefinisikan dalam "Pemrograman Fungsional dengan Pisang, Lensa, Amplop dan Kawat Berduri, Erik Meijer Maarten Fokkinga, Ross Paterson, 1991"; artikel itu sulit dibaca (bagi saya) karena penggunaannya yang berat terhadap Squiggol. Namun, "Tutorial tentang universalitas dan ekspresifitas lipatan, Graham Hutton, 1999" berisi definisi yang lebih mudah diurai:

Sebagai contoh pertama sederhana dari penggunaan flip untuk menghasilkan tupel, mempertimbangkan fungsi sumlength yang menghitung dengan jumlah dan panjang dari daftar nomor:

sumlength :: [Int] → (Int,Int)
sumlength xs = (sum xs, length xs)

Dengan kombinasi langsung dari definisi jumlah fungsi dan panjang menggunakan lipatan yang diberikan sebelumnya, panjang gelombang fungsi dapat didefinisikan ulang sebagai aplikasi tunggal lipatan yang menghasilkan sepasang angka dari daftar angka:

sumlength = fold (λn (x, y) → (n + x, 1 + y)) (0, 0)

Definisi ini lebih efisien daripada definisi asli, karena hanya membuat satu traversal atas daftar argumen, daripada dua traversal yang terpisah. Secara umum dari contoh ini, setiap pasangan aplikasi lipatan ke daftar yang sama selalu dapat digabungkan untuk memberikan aplikasi lipatan tunggal yang menghasilkan sepasang, dengan mengajukan banding ke apa yang disebut properti 'split pisang' dari lipatan (Meijer, 1992) . Nama aneh properti ini berasal dari fakta bahwa operator flip kadang-kadang ditulis menggunakan tanda kurung (| |) yang menyerupai pisang, dan operator pasangan kadang-kadang disebut split. Karenanya, kombinasi mereka dapat disebut sebagai pisang split!

Klaas van Schelven
sumber
19

Jadi ini sebenarnya direferensikan ke makalah oleh Meijer dan beberapa orang lain yang disebut " Pemrograman Fungsional dengan Pisang, Lensa, Amplop dan Kawat Berduri ", ide dasarnya adalah bahwa kita dapat mengambil tipe data rekursif, seperti

 data List = Cons Int List | Nil

dan kita bisa memfaktorkan rekursi menjadi variabel tipe

 data ListF a = Cons Int a | Nil

alasan mengapa saya menambahkan itu Fkarena ini sekarang adalah functor! Itu juga memungkinkan kita untuk meniru daftar, tetapi dengan twist: untuk membangun daftar kita harus bersarang tipe daftar

type ThreeList = ListF (ListF (ListF Void)))

Untuk memulihkan daftar asli kita, kita perlu terus bersarang tanpa batas . Itu akan memberi kita jenis di ListFFmana

  ListF ListFF == ListFF

Untuk melakukan ini, tentukan "tipe titik tetap"

  data Fix f = Fix {unfix :: f (Fix f)}
  type ListFF = Fix ListF

Sebagai latihan, Anda harus memverifikasi ini memenuhi persamaan kami di atas. Sekarang kami akhirnya dapat menentukan apa pisang (katamorfisme)!

  type ListAlg a = ListF a -> a

ListAlgs adalah jenis "list algebras", dan kita dapat mendefinisikan fungsi tertentu

  cata :: ListAlg a -> ListFF -> a
  cata f = f . fmap (cata f) . unfix

Lebih jauh lagi

  cata :: ListAlg a -> ListFF -> a
  cata :: (Either () (Int, a) -> a) -> ListFF -> a
  cata :: (() -> a) -> ((Int, a) -> a) -> ListFF -> a
  cata :: a -> (Int -> a -> a) -> ListFF -> a
  cata :: (Int -> a -> a) -> a -> [Int] -> a

Terlihat familier? catapersis sama dengan lipatan kanan!

Yang benar-benar menarik adalah bahwa kita dapat melakukan ini lebih dari sekadar daftar, jenis apa pun yang didefinisikan dengan "titik tetap dari functor" ini memiliki catadan untuk memperbarui mereka semua kita hanya perlu bersantai dengan tanda tangan jenis

  cata :: (f a -> a) -> Fix f -> a

Ini sebenarnya diilhami dari sepotong teori kategori yang saya tulis , tetapi ini adalah daging dari sisi Haskell.

Daniel Gratzer
sumber
2
apakah perlu disebutkan bahwa pisang adalah tanda kurung (| |) yang digunakan oleh kertas asli untuk mendefinisikan cata
jk.
7

Meskipun jozefg memberikan jawaban, saya tidak yakin apakah itu menjawab pertanyaan. "Hukum fusi" dijelaskan dalam makalah berikut:

Tutorial tentang universalitas dan ekspresifitas lipatan, GRAHAM HUTTON, 1999

Pada dasarnya dikatakan bahwa dalam beberapa kondisi Anda dapat menggabungkan ("sekering") komposisi fungsi dan lipat menjadi satu lipatan, jadi pada dasarnya

h · lipat gw = lipat fv

Kondisi untuk kesetaraan ini adalah

hw = v
h (gxy) = fx (hy)

"Pisang split" atau "banana split law" berasal dari artikel

Pemrograman Fungsional dengan Pisang, Lensa, Amplop dan Kawat Berduri, Erik Meijer Maarten Fokkinga, Ross Paterson, 1991

Sayangnya artikel ini sangat sulit untuk diuraikan karena menggunakan formalisme Bird-Meertens sehingga saya tidak dapat membuat kepala atau ekornya. Sejauh yang saya mengerti "hukum perpecahan pisang" dikatakan bahwa jika Anda memiliki 2 lipatan yang beroperasi pada argumen yang sama, mereka dapat digabung menjadi satu lipatan.

Jackie
sumber