Apakah semua wadah ukuran tetap merupakan fungsi monoid yang kuat, dan / atau sebaliknya?

The Applicativetypeclass mewakili longgar monoidal functors yang melestarikan struktur monoidal Cartesian pada kategori fungsi diketik.

Dengan kata lain, diberikan kesaksian isomorfisme kanonik yang (,)membentuk struktur monoid:

-- Implementations left to the motivated reader
assoc_fwd :: ((a, b), c) -> (a, (b, c))
assoc_bwd :: (a, (b, c)) -> ((a, b), c)

lunit_fwd :: ((), a) -> a
lunit_bwd :: a -> ((), a)

runit_fwd :: (a, ()) -> a
runit_bwd :: a -> (a, ())

Typeclass dan hukum-hukumnya dapat ditulis seperti ini:

class Functor f => Applicative f
  where
  zip :: (f a, f b) -> f (a, b)
  husk :: () -> f ()

-- Laws:

-- assoc_fwd >>> bimap id zip >>> zip
-- =
-- bimap zip id >>> zip >>> fmap assoc_fwd

-- lunit_fwd
-- =
-- bimap husk id >>> zip >>> fmap lunit_fwd

-- runit_fwd
-- =
-- bimap id husk >>> zip >>> fmap runit_fwd

Orang mungkin bertanya-tanya seperti apa fungsi yang oplax monoidal sehubungan dengan struktur yang sama terlihat seperti:

class Functor f => OpApplicative f
  where
  unzip :: f (a, b) -> (f a, f b)
  unhusk :: f () -> ()

-- Laws:

-- assoc_bwd <<< bimap id unzip <<< unzip
-- =
-- bimap unzip id <<< unzip <<< fmap assoc_bwd

-- lunit_bwd
-- =
-- bimap unhusk id <<< unzip <<< fmap lunit_bwd

-- runit_bwd
-- =
-- bimap id unhusk <<< unzip <<< fmap runit_bwd

Jika kita berpikir tentang tipe-tipe yang terlibat dalam definisi dan hukum, kebenaran yang mengecewakan terungkap; OpApplicativetidak lebih spesifik daripada kendala Functor:

instance Functor f => OpApplicative f
  where
  unzip fab = (fst <$> fab, snd <$> fab)
  unhusk = const ()

Namun, sementara setiap Applicativefunctor (benar-benar, ada Functor) sepele OpApplicative, belum tentu ada hubungan yang baik antara Applicativekelemahan dan OpApplicativeoplaxities. Jadi kita dapat mencari functor monoid yang kuat dengan struktur monoid cartesian:

class (Applicative f, OpApplicative f) => StrongApplicative f

-- Laws:
-- unhusk . husk = id
-- husk . unhusk = id
-- zip . unzip = id
-- unzip . zip = id

Hukum pertama di atas adalah sepele, karena satu-satunya penghuni jenis () -> ()ini adalah fungsi identitas ().

Namun, tiga undang-undang yang tersisa, dan karenanya subkelas itu sendiri, tidak sepele. Secara khusus, tidak setiap Applicativecontoh turunan dari kelas ini.

Berikut adalah beberapa Applicativefungsi yang kami dapat nyatakan hal-hal yang sah dari StrongApplicative:

• Identity
• VoidF
• (->) r
• Monoid m => (,) m (Lihat jawaban)
• Vec (n :: Nat)
• Stream (tak terbatas)

Dan di sini ada beberapa Applicativeyang kita tidak bisa:

• []
• Either e
• Maybe
• NonEmptyList

Pola di sini menunjukkan bahwa StrongApplicativekelas dalam arti tertentu adalah FixedSizekelas, di mana "ukuran tetap" ^* berarti bahwa multiplisitas ^** penduduk adalam suatu penduduk f aadalah tetap.

Ini dapat dinyatakan sebagai dua dugaan:

• Setiap Applicativemewakili wadah "ukuran tetap" elemen dari argumen jenisnya adalah turunan dariStrongApplicative
• Tidak ada contoh StrongApplicativeada di mana jumlah kejadian adapat bervariasi

Adakah yang bisa memikirkan contoh tandingan yang menyangkal dugaan ini, atau beberapa alasan meyakinkan yang menunjukkan mengapa itu benar atau salah?

* Saya menyadari bahwa saya belum mendefinisikan kata sifat "ukuran tetap" dengan benar. Sayangnya tugasnya agak melingkar. Saya tidak tahu deskripsi formal dari wadah "ukuran tetap", dan saya mencoba untuk membuat satu. StrongApplicativeadalah upaya terbaik saya sejauh ini.

Untuk mengevaluasi apakah ini definisi yang baik, saya perlu membandingkannya. Diberikan beberapa definisi formal / informal tentang apa artinya bagi functor untuk memiliki ukuran atau multiplisitas yang diberikan sehubungan dengan penduduk dari argumen tipenya, pertanyaannya adalah apakah keberadaan sebuah StrongApplicativeinstance secara tepat membedakan functors dari fixed dan berbagai ukuran.

Karena tidak mengetahui definisi formal yang ada, saya memohon intuisi dalam penggunaan istilah "ukuran tetap". Namun jika seseorang sudah mengetahui formalisme yang ada untuk ukuran functor dan dapat membandingkannya StrongApplicative, itu jauh lebih baik.

** Dengan "multiplisitas" Saya mengacu pada pengertian longgar untuk "berapa banyak" elemen sewenang-wenang dari tipe parameter functor yang terjadi pada penghuni jenis codomain functor. Ini tanpa memperhatikan tipe spesifik dari functor diterapkan, dan karenanya tanpa memperhatikan penghuni spesifik dari tipe parameter.

Tidak tepatnya tentang hal ini telah menyebabkan beberapa kebingungan dalam komentar, jadi inilah beberapa contoh dari apa yang saya anggap ukuran / multiplisitas berbagai fungsi menjadi:

• VoidF: diperbaiki, 0
• Identity: diperbaiki, 1
• Maybe: variabel, minimum 0, maksimum 1
• []: variabel, minimum 0, maksimum tak terbatas
• NonEmptyList: variabel, minimum 1, maksimum tak terbatas
• Stream: diperbaiki, tak terbatas
• Monoid m => (,) m: diperbaiki, 1
• data Pair a = Pair a a: diperbaiki, 2
• Either x: variabel, minimum 0, maksimum 1
• data Strange a = L a | R a: diperbaiki, 1

• Setiap Applicativemewakili wadah "ukuran tetap" elemen dari argumen jenisnya adalah turunan dariStrongApplicative
• Tidak ada contoh StrongApplicativeada di mana jumlah kejadian adapat bervariasi

Adakah yang bisa memikirkan contoh tandingan yang menyangkal dugaan ini, atau beberapa alasan meyakinkan yang menunjukkan mengapa itu benar atau salah?

Saya tidak yakin tentang dugaan pertama itu, dan berdasarkan diskusi dengan @AsadSaeeduddin kemungkinan sulit untuk dibuktikan, tetapi dugaan kedua benar. Untuk melihat alasannya, pertimbangkan StrongApplicativehukum husk . unhusk == id; yaitu, untuk semua x :: f (), husk (unhusk x) == x. Namun dalam Haskell, unhusk == const ()sehingga hukum yang setara dengan mengatakan untuk semua x :: f (), husk () == x. Tetapi ini pada gilirannya menyiratkan bahwa hanya ada satu nilai tipe yang berbeda f (): jika ada dua nilai x, y :: f (), maka x == husk ()dan husk () == y, begitu x == y. Tetapi jika hanya ada satu f ()nilai yang mungkin , maka fharus dari bentuk tetap. (misalnya untuk data Pair a = Pair a a, hanya ada satu nilai tipe Pair (), makhluk ini Pair () (), tetapi ada beberapa nilai tipe Maybe ()atau [()].) Jadihusk . unhusk == idmenyiratkan bahwa fharus berbentuk tetap.

Kami dapat menjawab setidaknya satu dari pertanyaan ini dalam negatif:

Setiap Aplikatif yang mewakili wadah "ukuran tetap" elemen argumen tipenya adalah turunan dari StrongApplicative

Sebenarnya salah satu contoh halal StrongApplicativedalam pertanyaan asli salah. Pelamar penulis Monoid => (,) mtidak StrongApplicative, karena misalnya husk $ unhusk $ ("foo", ()) == ("", ()) /= ("foo", ()).

Demikian pula, contoh wadah ukuran tetap:

data Strange a = L a | R a

dari multiplisitas tetap 1, bukan aplikatif yang kuat, karena jika kita mendefinisikan husk = Leftkemudian husk $ unhusk $ Right () /= Right (), dan sebaliknya. Cara yang setara untuk melihat ini adalah bahwa ini hanya aplikasi penulis untuk monoid pilihan Anda Bool.

Jadi ada pelamar "ukuran tetap" yang tidak StrongApplicative. Apakah semua StrongApplicativeukuran tetap masih harus dilihat.

Mari kita ambil functors yang dapat direpresentasikan sebagai definisi kami tentang "wadah ukuran tetap":

class Representable f where
    type Rep f
    tabulate :: (Rep f -> a) -> f a
    index :: f a -> Rep f -> a

Real Representablememiliki beberapa hukum dan superclasses, tetapi untuk keperluan jawaban ini, kita sebenarnya hanya membutuhkan dua properti:

tabulate . index = id
index . tabulate = id

(Oke, kita juga perlu taat hukum instance StrongApplicative ((->) r). Mudah sekali, kamu sudah setuju itu ada.)

Jika kita mengambil definisi itu, maka saya dapat mengkonfirmasi dugaan 1:

Setiap Applicativemewakili wadah "ukuran tetap" elemen dari argumen jenisnya adalah turunan [patuh hukum]StrongApplicative

adalah benar. Begini caranya:

instance Representable f => Applicative f where
    zip (fa, fb) = tabulate (zip (index fa, index fb))
    husk = tabulate . husk

instance Representable f => OpApplicative f where
    unzip fab = let (fa, fb) = unzip (index fab) in (tabulate fa, tabulate fb)
    unhusk = unhusk . index

instance Representable f => StrongApplicative f

Ada banyak hukum untuk dibuktikan, tapi saya akan fokus hanya pada Big Four yang StrongApplicativemenambahkan - Anda mungkin sudah percaya yang memimpin untuk , Applicativedan OpApplicativejika Anda tidak, buktinya terlihat seperti yang di bawah ini ( yang pada gilirannya terlihat sangat mirip satu sama lain). Untuk kejelasan, saya akan menggunakan zipf, huskf, dll untuk contoh fungsi, dan zipr, huskr, dll untuk contoh representable, sehingga Anda dapat melacak yang mana. (Dan agar mudah untuk memverifikasi bahwa kita tidak mengambil hal yang kita coba buktikan sebagai asumsi! Tidak apa-apa untuk digunakan unhuskf . huskf = idketika membuktikan unhuskr . huskr = id, tetapi akan salah untuk mengasumsikan unhuskr . huskr = iddalam bukti yang sama.)

Bukti dari setiap hukum pada dasarnya menghasilkan cara yang sama: membuka gulungan definisi, menjatuhkan isomorfisme yang Representablememberi Anda, kemudian menggunakan hukum analog untuk fungsi.

unhuskr . huskr
= { def. of unhuskr and huskr }
(unhuskf . index) . (tabulate . huskf)
= { index . tabulate = id }
unhuskf . huskf
= { unhuskf . huskf = id }
id

huskr . unhuskr
= { def. of huskr and unhuskr }
(tabulate . huskf) . (unhuskf . index)
= { huskf . unhuskf = id }
tabulate . index
= { tabulate . index = id }
id

zipr (unzipr fab)
= { def. of unzipr }
zipr (let (fa, fb) = unzipf (index fab) in (tabulate fa, tabulate fb))
= { def. of zipr }
let (fa, fb) = unzipf (index fab) in tabulate (zipf (index (tabulate fa), index (tabulate fb)))
= { index . tabulate = id }
let (fa, fb) = unzipf (index fab) in tabulate (zipf (fa, fb))
= { def. of (fa, fb) }
tabulate (zipf (unzipf (index fab)))
= { zipf . unzipf = id }
tabulate (index fab)
= { tabulate . index = id }
fab

unzipr (zipr (fa, fb))
= { def. of zipr }
unzipr (tabulate (zipf (index fa, index fb)))
= { def. of unzipr }
let (fa', fb') = unzipf (index (tabulate (zipf (index fa, index fb))))
in (tabulate fa', tabulate fb')
= { index . tabulate = id }
let (fa', fb') = unzipf (zipf (index fa, index fb))
in (tabulate fa', tabulate fb')
= { unzipf . zipf = id }
let (fa', fb') = (index fa, index fb)
in (tabulate fa', tabulate fb')
= { def. of fa' and fb' }
(tabulate (index fa), tabulate (index fb))
= { tabulate . index = id }
(fa, fb)