Apa indeks monad dan motivasi untuk monad ini?

Saya telah membaca bahwa itu membantu untuk melacak efek samping. Tetapi tipe tanda tangan dan dokumentasi tidak membawa saya ke mana pun.

Apa yang akan menjadi contoh bagaimana itu dapat membantu untuk melacak efek samping (atau contoh valid lainnya)?

Seperti biasa, terminologi yang digunakan orang tidak sepenuhnya konsisten. Ada berbagai gagasan yang terinspirasi oleh monad tetapi secara tegas tidak cukup. Istilah "monad terindeks" adalah salah satu angka (termasuk "monadish" dan "monad berparameter" (nama Atkey untuk mereka)) dari istilah yang digunakan untuk menandai salah satu gagasan tersebut. (Gagasan lain seperti itu, jika Anda tertarik, adalah "efek parametrik monad" Katsumata, diindeks oleh monoid, di mana pengembalian diindeks secara netral dan ikatan terakumulasi dalam indeksnya.)

Pertama-tama, mari kita periksa jenisnya.

IxMonad (m :: state -> state -> * -> *)

Artinya, jenis "komputasi" (atau "tindakan", jika Anda mau, tetapi saya akan tetap menggunakan "komputasi"), terlihat seperti

m before after value

dimana before, after :: statedan value :: *. Idenya adalah untuk menangkap sarana untuk berinteraksi secara aman dengan sistem eksternal yang memiliki beberapa gagasan keadaan yang dapat diprediksi . Jenis komputasi memberi tahu Anda keadaan apa yang harus beforedijalankannya, keadaan apa yang akan afterdijalankannya dan (seperti dengan monad reguler *) jenis apa valueyang dihasilkan komputasi.

Bit dan potongan biasa adalah *-wise seperti monad dan state-wise seperti bermain domino.

ireturn  ::  a -> m i i a    -- returning a pure value preserves state
ibind    ::  m i j a ->      -- we can go from i to j and get an a, thence
             (a -> m j k b)  -- we can go from j to k and get a b, therefore
             -> m i k b      -- we can indeed go from i to k and get a b

Gagasan tentang "panah Kleisli" (fungsi yang menghasilkan komputasi) yang dihasilkan adalah

a -> m i j b   -- values a in, b out; state transition i to j

dan kami mendapatkan komposisi

icomp :: IxMonad m => (b -> m j k c) -> (a -> m i j b) -> a -> m i k c
icomp f g = \ a -> ibind (g a) f

dan, seperti biasa, hukum memastikan hal itu ireturndan icompmemberi kita kategori

      ireturn `icomp` g = g
      f `icomp` ireturn = f
(f `icomp` g) `icomp` h = f `icomp` (g `icomp` h)

atau, dalam komedi palsu C / Java / apapun,

      g(); skip = g()
      skip; f() = f()
{g(); h()}; f() = h(); {g(); f()}

Mengapa mengganggu? Untuk mencontohkan "aturan" interaksi. Misalnya, Anda tidak dapat mengeluarkan dvd jika tidak ada di drive, dan Anda tidak dapat memasukkan dvd ke dalam drive jika sudah ada di dalamnya. Begitu

data DVDDrive :: Bool -> Bool -> * -> * where  -- Bool is "drive full?"
  DReturn :: a -> DVDDrive i i a
  DInsert :: DVD ->                   -- you have a DVD
             DVDDrive True k a ->     -- you know how to continue full
             DVDDrive False k a       -- so you can insert from empty
  DEject  :: (DVD ->                  -- once you receive a DVD
              DVDDrive False k a) ->  -- you know how to continue empty
             DVDDrive True k a        -- so you can eject when full

instance IxMonad DVDDrive where  -- put these methods where they need to go
  ireturn = DReturn              -- so this goes somewhere else
  ibind (DReturn a)     k  = k a
  ibind (DInsert dvd j) k  = DInsert dvd (ibind j k)
  ibind (DEject j)      k  = DEject j $ \ dvd -> ibind (j dvd) k

Dengan ini, kita bisa mendefinisikan perintah "primitif"

dInsert :: DVD -> DVDDrive False True ()
dInsert dvd = DInsert dvd $ DReturn ()

dEject :: DVDrive True False DVD
dEject = DEject $ \ dvd -> DReturn dvd

dari mana orang lain berkumpul dengan ireturndan ibind. Sekarang, saya bisa menulis (meminjam- donotasi)

discSwap :: DVD -> DVDDrive True True DVD
discSwap dvd = do dvd' <- dEject; dInsert dvd ; ireturn dvd'

tapi bukan yang tidak mungkin secara fisik

discSwap :: DVD -> DVDDrive True True DVD
discSwap dvd = do dInsert dvd; dEject      -- ouch!

Alternatifnya, seseorang dapat mendefinisikan perintah primitifnya secara langsung

data DVDCommand :: Bool -> Bool -> * -> * where
  InsertC  :: DVD -> DVDCommand False True ()
  EjectC   :: DVDCommand True False DVD

dan kemudian membuat contoh template generik

data CommandIxMonad :: (state -> state -> * -> *) ->
                        state -> state -> * -> * where
  CReturn  :: a -> CommandIxMonad c i i a
  (:?)     :: c i j a -> (a -> CommandIxMonad c j k b) ->
                CommandIxMonad c i k b

instance IxMonad (CommandIxMonad c) where
  ireturn = CReturn
  ibind (CReturn a) k  = k a
  ibind (c :? j)    k  = c :? \ a -> ibind (j a) k

Akibatnya, kita telah mengatakan apa itu panah Kleisli primitif (apa itu "domino"), kemudian membangun gagasan yang sesuai tentang "urutan komputasi" di atasnya.

Perhatikan bahwa untuk setiap monad yang diindeks m, "tanpa perubahan diagonal" m i iadalah monad, tetapi secara umum m i jtidak. Selain itu, nilai tidak diindeks tetapi perhitungan diindeks, jadi monad yang diindeks bukan hanya gagasan biasa dari monad yang dipakai untuk beberapa kategori lain.

Sekarang, lihat kembali jenis panah Kleisli

a -> m i j b

Kami tahu kami harus berada dalam keadaan iuntuk memulai, dan kami memperkirakan bahwa kelanjutan apa pun akan dimulai dari keadaan j. Kami tahu banyak tentang sistem ini! Ini bukan operasi yang berisiko! Saat kita memasukkan dvd ke dalam drive, itu masuk! Drive dvd tidak dapat menentukan status setelah setiap perintah.

Tapi itu tidak benar secara umum, saat berinteraksi dengan dunia. Terkadang Anda mungkin perlu memberikan kendali dan membiarkan dunia melakukan apa yang disukainya. Misalnya, jika Anda adalah server, Anda mungkin menawarkan pilihan kepada klien, dan status sesi Anda akan bergantung pada apa yang mereka pilih. Operasi "pilihan penawaran" server tidak menentukan status yang dihasilkan, tetapi server harus dapat melanjutkannya. Ini bukan "perintah primitif" dalam pengertian di atas, jadi monad yang diindeks bukanlah alat yang baik untuk membuat model skenario yang tidak dapat diprediksi .

Alat apa yang lebih baik?

type f :-> g = forall state. f state -> g state

class MonadIx (m :: (state -> *) -> (state -> *)) where
  returnIx    :: x :-> m x
  flipBindIx  :: (a :-> m b) -> (m a :-> m b)  -- tidier than bindIx

Biskuit menakutkan? Tidak juga, karena dua alasan. Satu, lebih terlihat seperti apa itu monad, karena itu adalah monad, tetapi lebih (state -> *)daripada *. Kedua, jika Anda melihat jenis panah Kleisli,

a :-> m b   =   forall state. a state -> m b state

Anda mendapatkan jenis perhitungan dengan prasyarat a dan pascakondisi b, seperti di Good Old Hoare Logic. Pernyataan dalam logika program membutuhkan waktu kurang dari setengah abad untuk melintasi korespondensi Curry-Howard dan menjadi tipe Haskell. Jenis returnIxkata "Anda dapat mencapai kondisi akhir apa pun yang berlaku, hanya dengan tidak melakukan apa pun", yang merupakan aturan Logika Hoare untuk "lewati". Komposisi yang sesuai adalah aturan Hoare Logic untuk ";".

Mari selesaikan dengan melihat jenisnya bindIx, masukkan semua bilangannya.

bindIx :: forall i. m a i -> (forall j. a j -> m b j) -> m b i

Ini forallmemiliki polaritas yang berlawanan. Kami memilih status awal i, dan komputasi yang dapat dimulai pada i, dengan kondisi pos a. Dunia memilih negara perantara apa pun yang jdisukainya, tetapi dunia harus memberi kita bukti bahwa kondisi pasca bberlaku, dan dari keadaan seperti itu, kita dapat terus bmempertahankannya. Jadi, secara berurutan, kita bisa mencapai kondisi bdari negara i. Dengan melepaskan pegangan kita pada status "setelah", kita dapat membuat model komputasi yang tidak dapat diprediksi .

Keduanya IxMonaddan MonadIxberguna. Kedua model validitas komputasi interaktif sehubungan dengan perubahan keadaan, dapat diprediksi dan tidak dapat diprediksi, masing-masing. Prediktabilitas sangat berharga jika Anda bisa mendapatkannya, tetapi ketidakpastian terkadang merupakan fakta kehidupan. Mudah-mudahan, jawaban ini memberikan beberapa indikasi tentang apa itu indexed monads, memprediksi kapan mereka mulai berguna dan kapan berhenti.

Setidaknya ada tiga cara untuk mendefinisikan monad terindeks yang saya tahu.

Saya akan menyebut opsi ini sebagai monad yang diindeks à la X , di mana X berkisar di atas ilmuwan komputer Bob Atkey, Conor McBride dan Dominic Orchard, karena begitulah cara saya cenderung memikirkannya. Bagian dari konstruksi ini memiliki sejarah yang jauh lebih terkenal dan interpretasi yang lebih baik melalui teori kategori, tetapi saya pertama kali mempelajarinya terkait dengan nama-nama ini, dan saya mencoba untuk menjaga jawaban ini agar tidak terlalu esoteris.

Atkey

Gaya monad terindeks Bob Atkey bekerja dengan 2 parameter tambahan untuk menangani indeks monad.

Dengan itu Anda mendapatkan definisi yang telah dilontarkan orang-orang dalam jawaban lain:

class IMonad m where
  ireturn  ::  a -> m i i a
  ibind    ::  m i j a -> (a -> m j k b) -> m i k b

Kami juga dapat mendefinisikan comonads à la Atkey terindeks. Saya benar-benar mendapatkan banyak jarak tempuh dari mereka yang ada di lensbasis kode .

McBride

Bentuk indexed monad selanjutnya adalah definisi Conor McBride dari makalahnya "Kleisli Arrows of Outrageous Fortune" . Dia malah menggunakan satu parameter untuk indeks. Hal ini membuat definisi monad terindeks memiliki bentuk yang agak pintar.

Jika kita mendefinisikan transformasi natural menggunakan parametrikitas sebagai berikut

type a ~> b = forall i. a i -> b i 

kemudian kita dapat menuliskan definisi McBride sebagai

class IMonad m where
  ireturn :: a ~> m a
  ibind :: (a ~> m b) -> (m a ~> m b)

Ini terasa sangat berbeda dari Atkey, tetapi ini lebih terasa seperti Monad biasa, daripada membangun monad (m :: * -> *), kami membangunnya (m :: (k -> *) -> (k -> *).

Menariknya, Anda benar-benar dapat memulihkan gaya monad terindeks Atkey dari McBride dengan menggunakan tipe data yang cerdas, yang menurut McBride dalam gayanya yang tak ada bandingannya, Anda harus membaca sebagai "pada kunci".

data (:=) :: a i j where
   V :: a -> (a := i) i

Sekarang Anda bisa mengatasinya

ireturn :: IMonad m => (a := j) ~> m (a := j)

yang berkembang menjadi

ireturn :: IMonad m => (a := j) i -> m (a := j) i

hanya dapat dipanggil ketika j = i, dan membaca dengan cermat ibinddapat membuat Anda kembali sama seperti Atkey ibind. Anda perlu meneruskan struktur data (: =) ini, tetapi mereka memulihkan kekuatan presentasi Atkey.

Di sisi lain, presentasi Atkey tidak cukup kuat untuk memulihkan semua penggunaan versi McBride. Kekuasaan telah diperoleh dengan ketat.

Hal lain yang menyenangkan adalah bahwa monad terindeks McBride jelas merupakan monad, itu hanya monad pada kategori fungsi yang berbeda. Ia bekerja di atas fungsi akhir pada kategori fungsi dari (k -> *)ke (k -> *)daripada kategori fungsi dari *ke *.

Latihan yang menyenangkan adalah mencari tahu bagaimana melakukan konversi McBride ke Atkey untuk comonad terindeks . Saya pribadi menggunakan tipe data 'At' untuk konstruksi "pada kunci" dalam makalah McBride. Saya benar-benar berjalan ke Bob Atkey di ICFP 2013 dan mengatakan bahwa saya telah mengubahnya menjadi "Mantel". Dia tampak sangat terganggu. Garis itu dimainkan lebih baik di kepalaku. =)

Orchard

Akhirnya, penggugat ketiga yang jauh lebih jarang direferensikan untuk nama "monad terindeks" adalah karena Dominic Orchard, di mana ia malah menggunakan jenis level monoid untuk menghancurkan indeks bersama. Daripada membahas detail konstruksinya, saya hanya akan menautkan ke pembicaraan ini:

https://github.com/dorchard/effect-monad/blob/master/docs/ixmonad-fita14.pdf

Sebagai skenario sederhana, asumsikan Anda memiliki monad negara bagian. Tipe state adalah state yang besar dan kompleks, namun semua state ini dapat dibagi menjadi dua set: status merah dan biru. Beberapa operasi dalam monad ini masuk akal hanya jika keadaan saat ini adalah keadaan biru. Di antaranya, beberapa akan membuat status biru ( blueToBlue), sementara yang lain akan membuat status merah ( blueToRed). Dalam monad biasa, kita bisa menulis

blueToRed  :: State S ()
blueToBlue :: State S ()

foo :: State S ()
foo = do blueToRed
         blueToBlue

memicu kesalahan waktu proses karena tindakan kedua mengharapkan keadaan biru. Kami ingin mencegah ini secara statis. Monad yang diindeks memenuhi tujuan ini:

data Red
data Blue

-- assume a new indexed State monad
blueToRed  :: State S Blue Red  ()
blueToBlue :: State S Blue Blue ()

foo :: State S ?? ?? ()
foo = blueToRed `ibind` \_ ->
      blueToBlue          -- type error

Kesalahan tipe dipicu karena indeks kedua blueToRed( Red) berbeda dari indeks pertama blueToBlue( Blue).

Sebagai contoh lain, dengan monad terindeks Anda dapat mengizinkan monad status untuk mengubah jenis statusnya, misalnya Anda dapat memiliki

data State old new a = State (old -> (new, a))

Anda dapat menggunakan cara di atas untuk membangun keadaan yang merupakan tumpukan heterogen yang diketik secara statis. Operasi akan memiliki tipe

push :: a -> State old (a,old) ()
pop  :: State (a,new) new a

Sebagai contoh lain, misalkan Anda menginginkan monad IO terbatas yang tidak mengizinkan akses file. Anda bisa menggunakan mis

openFile :: IO any FilesAccessed ()
newIORef :: a -> IO any any (IORef a)
-- no operation of type :: IO any NoAccess _

Dengan cara ini, tindakan yang memiliki tipe IO ... NoAccess ()dijamin secara statis bebas akses file. Sebaliknya, suatu tindakan IO ... FilesAccessed ()dapat mengakses file. Memiliki monad terindeks berarti Anda tidak perlu membuat tipe terpisah untuk IO terbatas, yang akan memerlukan duplikasi setiap fungsi yang tidak terkait dengan file di kedua tipe IO.

Monad yang diindeks bukanlah monad spesifik seperti, misalnya, monad negara bagian, tetapi semacam generalisasi konsep monad dengan parameter tipe tambahan.

Sedangkan nilai monad "standar" memiliki tipe, Monad m => m anilai dalam monad terindeks berada di IndexedMonad m => m i j amana idan jmerupakan tipe indeks sehingga imerupakan jenis indeks pada awal komputasi monad dan jpada akhir komputasi. Di satu sisi, Anda dapat menganggapnya isebagai jenis masukan dan jjenis keluaran.

Menggunakan Statesebagai contoh, komputasi stateful State s amempertahankan status tipe di sseluruh komputasi dan mengembalikan hasil tipe a. Versi yang diindeks IndexedState i j a,, adalah komputasi berstatus di mana status dapat berubah ke jenis yang berbeda selama komputasi. Keadaan awal memiliki tipe idan status dan akhir komputasi memiliki tipenya j.

Menggunakan monad terindeks di atas monad normal jarang diperlukan, tetapi dapat digunakan dalam beberapa kasus untuk menyandikan jaminan statis yang lebih ketat.

Mungkin penting untuk melihat bagaimana pengindeksan digunakan dalam tipe dependen (misalnya di agda). Ini dapat menjelaskan bagaimana pengindeksan membantu secara umum, lalu menerjemahkan pengalaman ini ke monad.

Izin pengindeksan untuk membangun hubungan antara contoh jenis tertentu. Kemudian Anda dapat bernalar tentang beberapa nilai untuk menetapkan apakah hubungan tersebut berlaku.

Misalnya (dalam agda) Anda dapat menentukan bahwa beberapa bilangan asli terkait dengan _<_, dan jenisnya memberitahukan bilangan tersebut. Kemudian Anda dapat meminta beberapa fungsi diberikan saksi m < n, karena hanya dengan demikian fungsi tersebut bekerja dengan benar - dan tanpa memberikan saksi tersebut program tidak akan dapat dikompilasi.

Sebagai contoh lain, dengan ketekunan dan dukungan kompilator yang cukup untuk bahasa pilihan Anda, Anda dapat menyandikan bahwa fungsi mengasumsikan bahwa daftar tertentu diurutkan.

Monad yang diindeks memungkinkan untuk menyandikan beberapa dari apa yang dilakukan sistem tipe dependen, untuk mengelola efek samping dengan lebih tepat.