Apa itu monad gratis?

Saya telah melihat istilah Free Monad muncul setiap sekarang dan kemudian untuk beberapa waktu, tetapi semua orang sepertinya menggunakan / mendiskusikannya tanpa memberikan penjelasan tentang apa itu mereka. Jadi: apa itu monad gratis? (Saya akan mengatakan saya akrab dengan monad dan dasar-dasar Haskell, tetapi hanya memiliki pengetahuan yang sangat kasar tentang teori kategori.)

Jawaban Edward Kmett jelas luar biasa. Tapi, ini agak teknis. Berikut ini penjelasan yang mungkin lebih mudah diakses.

Monad gratis hanyalah cara umum untuk mengubah functors menjadi monad. Artinya, mengingat functor f Free fadalah monad. Ini tidak akan sangat berguna, kecuali Anda mendapatkan sepasang fungsi

liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r

yang pertama memungkinkan Anda "memasuki" monad Anda, dan yang kedua memberi Anda cara untuk "keluar" darinya.

Lebih umum, jika X adalah Y dengan beberapa hal tambahan P, maka "X gratis" adalah cara untuk mendapatkan dari Y ke X tanpa mendapatkan tambahan apa pun.

Contoh: monoid (X) adalah himpunan (Y) dengan struktur ekstra (P) yang pada dasarnya mengatakan ia memiliki operasi (Anda dapat memikirkan penambahan) dan beberapa identitas (seperti nol).

Begitu

class Monoid m where
   mempty  :: m
   mappend :: m -> m -> m

Sekarang, kita semua tahu daftar

data [a] = [] | a : [a]

Nah, mengingat jenis apa pun yang tkita tahu itu [t]adalah monoid

instance Monoid [t] where
  mempty   = []
  mappend = (++)

dan daftar adalah "monoid gratis" atas set (atau dalam tipe Haskell).

Oke, jadi monad gratis adalah ide yang sama. Kami mengambil functor, dan mengembalikan monad. Bahkan, karena monad dapat dilihat sebagai monoids dalam kategori endofunctors, definisi daftar

data [a] = [] | a : [a]

terlihat sangat mirip dengan definisi monads gratis

data Free f a = Pure a | Roll (f (Free f a))

dan Monadinstance memiliki kesamaan dengan Monoidinstance untuk daftar

--it needs to be a functor
instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Roll x) = Roll (fmap (fmap f) x)

--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
concatFree (Pure x) = x
concatFree (Roll y) = Roll (fmap concatFree y)

instance Functor f => Monad (Free f) where
  return = Pure -- just like []
  x >>= f = concatFree (fmap f x)  --this is the standard concatMap definition of bind

sekarang, kami mendapatkan dua operasi kami

-- this is essentially the same as \x -> [x]
liftFree :: Functor f => f a -> Free f a
liftFree x = Roll (fmap Pure x)

-- this is essentially the same as folding a list
foldFree :: Functor f => (f r -> r) -> Free f r -> r
foldFree _ (Pure a) = a
foldFree f (Roll x) = f (fmap (foldFree f) x)

Inilah jawaban yang bahkan lebih sederhana: Monad adalah sesuatu yang "menghitung" ketika konteks monadik dihancurkan oleh join :: m (m a) -> m a(mengingat yang >>=dapat didefinisikan sebagai x >>= y = join (fmap y x)). Ini adalah cara Monads membawa konteks melalui rantai perhitungan berurutan: karena pada setiap titik dalam rangkaian, konteks dari panggilan sebelumnya dihancurkan dengan yang berikutnya.

Sebuah monad bebas memenuhi semua hukum Monad, tetapi tidak melakukan runtuh (yaitu, perhitungan). Itu hanya membangun serangkaian konteks bersarang. Pengguna yang menciptakan nilai monadik bebas bertanggung jawab untuk melakukan sesuatu dengan konteks bersarang tersebut, sehingga makna komposisi tersebut dapat ditangguhkan hingga setelah nilai monadik dibuat.

Foo bebas merupakan hal paling sederhana yang memenuhi semua hukum 'foo'. Dengan kata lain itu memenuhi hukum yang diperlukan untuk menjadi foo dan tidak ada yang ekstra.

Functor pelupa adalah salah satu yang "lupa" bagian dari struktur saat berjalan dari satu kategori ke yang lain.

Fungsi yang diberikan F : D -> C, dan G : C -> D, kita katakan F -| G, Fdibiarkan bersebelahan dengan G, atau berbelok ke Gkanan Fsetiap kali, a: b F a -> badalah isomorfik a -> G b, di mana panah berasal dari kategori yang sesuai.

Secara formal, functor gratis dibiarkan berdekatan dengan functor yang pelupa.

Monoid Gratis

Mari kita mulai dengan contoh sederhana, monoid gratis.

Ambil monoid, yang didefinisikan oleh beberapa operator set T, fungsi biner untuk mash sepasang elemen bersama-sama f :: T → T → T, dan unit :: T, seperti bahwa Anda memiliki hukum asosiatif, dan hukum identitas: f(unit,x) = x = f(x,unit).

Anda dapat membuat functor Udari kategori monoids (di mana panah adalah homomorfisma monoid, yaitu, mereka memastikan mereka memetakan unitke unitmonoid lain, dan bahwa Anda dapat menyusun sebelum atau setelah pemetaan ke monoid lain tanpa mengubah makna) ke kategori set (di mana panah hanya panah fungsi) yang 'lupa' tentang operasi dan unit, dan hanya memberi Anda set operator.

Kemudian, Anda dapat mendefinisikan functor Fdari kategori set kembali ke kategori monoids yang dibiarkan bersebelahan dengan functor ini. Functor itu adalah functor yang memetakan set ake monoid [a], di mana unit = [], dan mappend = (++).

Jadi untuk meninjau contoh kita sejauh ini, di pseudo-Haskell:

U : Mon → Set -- is our forgetful functor
U (a,mappend,mempty) = a

F : Set → Mon -- is our free functor
F a = ([a],(++),[])

Kemudian untuk menunjukkan Fitu gratis, kita perlu menunjukkan bahwa itu dibiarkan bersebelahan dengan U, sebuah fungsi yang pelupa, yaitu, seperti yang kita sebutkan di atas, kita perlu menunjukkan bahwa

F a → b isomorfik untuk a → U b

sekarang, ingat bahwa target Fberada dalam kategori Monmonoids, di mana panah adalah homomorfisma monoid, jadi kita perlu untuk menunjukkan bahwa homomorfisma monoid [a] → bdapat digambarkan secara tepat dengan fungsi dari a → b.

Dalam Haskell, kita menyebut sisi dari ini yang hidup dalam Set(eh,, Haskkategori tipe Haskell yang kita pura-pura adalah Set), adil foldMap, yang ketika dikhususkan Data.Foldableuntuk dari memiliki tipe Monoid m => (a → m) → [a] → m.

Ada konsekuensi yang mengikuti dari ini menjadi tambahan. Khususnya jika Anda lupa maka membangun dengan gratis, lalu lupakan lagi, sama seperti Anda lupa sekali, dan kita bisa menggunakan ini untuk membangun monadik bergabung. sejak UFUF~ U(FUF)~ UF, dan kita bisa lulus dalam homomorfisma identitas monoid dari [a]ke [a]melalui isomorfisma yang mendefinisikan adjunction kami, mendapatkan bahwa daftar isomorfisma dari [a] → [a]adalah fungsi dari jenis a -> [a], dan ini hanya kembali untuk daftar.

Anda dapat menyusun semua ini lebih langsung dengan menggambarkan daftar dalam istilah ini dengan:

newtype List a = List (forall b. Monoid b => (a -> b) -> b)

Monad Gratis

Jadi, apa itu Monad Gratis ?

Ya, kami melakukan hal yang sama dengan yang kami lakukan sebelumnya, kami mulai dengan functor U yang pelupa dari kategori monad di mana panah adalah homomorfisma monad ke kategori endofunctor di mana panah adalah transformasi alami, dan kami mencari functor yang dibiarkan berdekatan untuk itu.

Jadi, bagaimana ini berhubungan dengan gagasan tentang monad gratis seperti yang biasanya digunakan?

Mengetahui bahwa sesuatu adalah monad bebas Free f,, memberitahu Anda bahwa memberi homomorfisme monad dari Free f -> m, adalah hal yang sama (isomorfik ke) dengan memberikan transformasi alami (homomorfisme functor) dari f -> m. Ingat F a -> bharus isomorfik agar a -> U bF dibiarkan bersebelahan dengan U. U di sini memetakan monad ke functors.

F setidaknya isomorfis dengan Freetipe yang saya gunakan dalam freepaket saya tentang peretasan.

Kita juga dapat membangunnya dalam analogi yang lebih ketat dengan kode di atas untuk daftar gratis, dengan mendefinisikan

class Algebra f x where
  phi :: f x -> x

newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)

Cofree Comonads

Kita dapat membangun sesuatu yang serupa, dengan melihat adjoint yang tepat ke functor yang pelupa dengan asumsi itu ada. Sebuah functor cofree hanyalah adjoin kanan / ke functor pelupa, dan dengan simetri, mengetahui sesuatu adalah comofad cofree sama dengan mengetahui bahwa memberikan homomorfisme comonad dari w -> Cofree fadalah hal yang sama seperti memberikan transformasi alami dari w -> f.

Free Monad (struktur data) adalah untuk Monad (kelas) seperti Daftar (struktur data) ke Monoid (kelas): Ini adalah implementasi sepele, di mana Anda dapat memutuskan setelahnya bagaimana konten akan digabungkan.

Anda mungkin tahu apa itu Monad dan bahwa masing-masing Monad membutuhkan implementasi ( fmap+ -tang hukum Monad) khusus untuk + join+ returnatau bind+ return.

Mari kita asumsikan Anda memiliki Functor (implementasi dari fmap) tetapi sisanya tergantung pada nilai dan pilihan yang dibuat saat run-time, yang berarti bahwa Anda ingin dapat menggunakan properti Monad tetapi ingin memilih fungsi Monad sesudahnya.

Itu dapat dilakukan dengan menggunakan Free Monad (struktur data), yang membungkus Functor (tipe) sedemikian rupa sehingga joinlebih merupakan susunan fungsi-fungsi tersebut daripada pengurangan.

Yang asli returndan joinyang ingin Anda gunakan, sekarang dapat diberikan sebagai parameter ke fungsi reduksi foldFree:

foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree return join :: Monad m => Free m a -> m a

Untuk menjelaskan jenisnya, kita dapat mengganti Functor fdengan Monad mdan bdengan (m a):

foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)

Monad gratis Haskell adalah daftar functors. Membandingkan:

data List a   = Nil    | Cons  a (List a  )

data Free f r = Pure r | Free (f (Free f r))

Pureanalog dengan Nildan Freeanalog dengan Cons. Monad gratis menyimpan daftar fungsi alih-alih daftar nilai. Secara teknis, Anda bisa mengimplementasikan monad gratis menggunakan tipe data yang berbeda, tetapi implementasi apa pun harus isomorfis dengan yang di atas.

Anda menggunakan monad gratis setiap kali Anda membutuhkan pohon sintaksis abstrak. Functor dasar dari monad gratis adalah bentuk setiap langkah dari pohon sintaks.

Pos saya , yang sudah ditautkan oleh seseorang, memberikan beberapa contoh cara membangun pohon sintaksis abstrak dengan monad gratis

Saya pikir contoh nyata yang sederhana akan membantu. Misalkan kita memiliki functor

data F a = One a | Two a a | Two' a a | Three Int a a a

dengan jelas fmap. Maka Free F aadalah jenis pohon yang daunnya memiliki jenis adan yang node ditandai dengan One, Two, Two'dan Three. One-node memiliki satu anak, Two- dan Two'-nodes memiliki dua anak dan Three-nodes memiliki tiga anak dan juga ditandai dengan Int.

Free Fadalah monad. returnpeta xke pohon yang hanya daun dengan nilai x. t >>= fmelihat masing-masing daun dan menggantinya dengan pohon. Ketika daun memiliki nilai yitu menggantikan daun itu dengan pohon f y.

Diagram membuat ini lebih jelas, tetapi saya tidak memiliki fasilitas untuk menggambarnya dengan mudah!