Contoh yang bagus dari Bukan Functor / Functor / Applicative / Monad?

Sambil menjelaskan kepada seseorang apa tipe kelas X itu, saya berjuang untuk menemukan contoh struktur data yang tepat yaitu X.

Jadi, saya meminta contoh untuk:

• Tipe konstruktor yang bukan merupakan Functor.
• Tipe konstruktor yang merupakan Functor, tetapi tidak berlaku.
• Tipe konstruktor yang merupakan Aplikasi, tetapi bukan Monad.
• Tipe konstruktor yang merupakan Monad.

Saya pikir ada banyak contoh Monad di mana-mana, tetapi contoh yang baik dari Monad dengan beberapa kaitannya dengan contoh-contoh sebelumnya dapat melengkapi gambarannya.

Saya mencari contoh yang akan mirip satu sama lain, hanya berbeda dalam aspek-aspek penting untuk menjadi milik kelas tipe tertentu.

Jika seseorang berhasil menyelinap contoh Arrow di suatu tempat dalam hierarki ini (apakah itu antara Applicative dan Monad?), Itu akan menjadi hebat juga!

Tipe konstruktor yang bukan merupakan Functor:

newtype T a = T (a -> Int)

Anda dapat membuat functor kontravarian darinya, tetapi bukan functor (kovarian). Cobalah menulis fmapdan Anda akan gagal. Perhatikan bahwa versi fungsi contravarian terbalik:

fmap      :: Functor f       => (a -> b) -> f a -> f b
contramap :: Contravariant f => (a -> b) -> f b -> f a

Tipe konstruktor yang merupakan functor, tetapi tidak berlaku:

Saya tidak punya contoh yang baik. Memang ada Const, tetapi idealnya saya ingin yang non-monoid dan saya tidak bisa memikirkannya. Semua tipe pada dasarnya numerik, enumerasi, produk, jumlah, atau fungsi saat Anda melakukannya. Anda dapat melihat di bawah ini pekerja pigmen dan saya tidak setuju tentang apakah Data.Voiditu Monoid;

instance Monoid Data.Void where
    mempty = undefined
    mappend _ _ = undefined
    mconcat _ = undefined

Karena _|_nilai legal di Haskell, dan pada kenyataannya satu-satunya nilai legal Data.Void, ini memenuhi aturan Monoid. Saya tidak yakin apa yang unsafeCoerceharus dilakukan dengan itu, karena program Anda tidak lagi dijamin tidak akan melanggar semantik Haskell segera setelah Anda menggunakan unsafefungsi apa pun .

Lihat Haskell Wiki untuk artikel di bagian bawah ( tautan ) atau fungsi tidak aman ( tautan ).

Saya ingin tahu apakah mungkin untuk membuat konstruktor tipe seperti itu menggunakan sistem tipe yang lebih kaya, seperti Agda atau Haskell dengan berbagai ekstensi.

Tipe konstruktor yang merupakan Aplikasi, tetapi bukan Monad:

newtype T a = T {multidimensional array of a}

Anda dapat membuat Applicative darinya, dengan sesuatu seperti:

mkarray [(+10), (+100), id] <*> mkarray [1, 2]
  == mkarray [[11, 101, 1], [12, 102, 2]]

Tetapi jika Anda menjadikannya monad, Anda bisa mendapatkan dimensi ketidakcocokan. Saya menduga bahwa contoh seperti ini jarang terjadi dalam praktiknya.

Tipe konstruktor yang merupakan Monad:

[]

Tentang Panah:

Bertanya di mana Arrow berada pada hierarki ini seperti menanyakan bentuk apa yang "merah". Perhatikan ketidakcocokan jenis:

Functor :: * -> *
Applicative :: * -> *
Monad :: * -> *

tapi,

Arrow :: * -> * -> *

Gaya saya mungkin sempit oleh ponsel saya, tapi begini saja.

newtype Not x = Kill {kill :: x -> Void}

tidak bisa menjadi Functor. Jika ya, kita harus melakukannya

kill (fmap (const ()) (Kill id)) () :: Void

dan Bulan akan terbuat dari keju hijau.

Sementara itu

newtype Dead x = Oops {oops :: Void}

adalah functor

instance Functor Dead where
  fmap f (Oops corpse) = Oops corpse

tetapi tidak bisa menjadi aplikatif, atau kita miliki

oops (pure ()) :: Void

dan Green akan dibuat dari keju Bulan (yang sebenarnya bisa terjadi, tetapi baru nanti malam).

(Catatan tambahan:, Voidseperti pada Data.Voiddatatype kosong. Jika Anda mencoba menggunakan undefineduntuk membuktikan itu adalah Monoid, saya akan gunakan unsafeCoerceuntuk membuktikan bahwa itu bukan.)

Dengan gembira,

newtype Boo x = Boo {boo :: Bool}

bersifat aplikatif dalam banyak hal, misalnya, seperti yang Dijkstra miliki,

instance Applicative Boo where
  pure _ = Boo True
  Boo b1 <*> Boo b2 = Boo (b1 == b2)

tapi itu tidak bisa menjadi Monad. Untuk melihat mengapa tidak, perhatikan bahwa pengembalian harus secara konstan Boo Trueatau Boo False, dan karenanya

join . return == id

tidak mungkin tahan.

Oh ya, aku hampir lupa

newtype Thud x = The {only :: ()}

adalah Monad. Gulung sendiri.

Pesawat untuk ditangkap ...

Saya percaya jawaban lain melewatkan beberapa contoh sederhana dan umum:

Tipe konstruktor yang merupakan Functor tetapi bukan Applicative. Contoh sederhana adalah pasangan:

instance Functor ((,) r) where
    fmap f (x,y) = (x, f y)

Tetapi tidak ada cara bagaimana mendefinisikan Applicativeinstance -nya tanpa memaksakan pembatasan tambahan r. Secara khusus, tidak ada cara bagaimana mendefinisikan pure :: a -> (r, a)untuk arbitrer r.

Tipe konstruktor yang merupakan Aplikasi, tetapi bukan Monad. Contoh yang terkenal adalah ZipList . (Ini adalah newtypeyang membungkus daftar dan memberikan Applicativecontoh berbeda untuk mereka.)

fmapdidefinisikan dengan cara biasa. Tetapi puredan <*>didefinisikan sebagai

pure x                    = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)

sehingga puremenciptakan daftar tak terbatas dengan mengulangi nilai yang diberikan, dan <*>ritsleting daftar fungsi dengan daftar nilai - berlaku i fungsi -th ke i elemen th. (Standar <*>pada []menghasilkan semua kemungkinan kombinasi menerapkan i fungsi -th ke j elemen th.) Tetapi tidak ada cara yang masuk akal bagaimana untuk menentukan monad (lihat posting ini ).

Bagaimana panah masuk ke dalam hierarki functor / applicative / monad? Lihat Idiom tidak menyadari, panah sangat teliti, monad bebas oleh Sam Lindley, Philip Wadler, Jeremy Yallop. MSFP 2008. (Mereka menyebut idiom fungsi aplikator .) Abstrak:

Kami meninjau kembali hubungan antara tiga gagasan perhitungan: monad Moggi, panah Hughes dan idiom McBride dan Paterson (juga disebut fungsi aplikatif). Kami menunjukkan bahwa idiom setara dengan panah yang memenuhi tipe isomorfisma A ~> B = 1 ~> (A -> B) dan bahwa monad setara dengan panah yang memenuhi tipe isomorfisma A ~> B = A -> (1 ~ > B). Selanjutnya, idiom ditanamkan ke panah dan panah ditanamkan ke monad.

Contoh yang baik untuk konstruktor tipe yang bukan functor adalah Set: Anda tidak dapat mengimplementasikan fmap :: (a -> b) -> f a -> f b, karena tanpa kendala tambahan Ord bAnda tidak dapat membangun f b.

Saya ingin mengusulkan pendekatan yang lebih sistematis untuk menjawab pertanyaan ini, dan juga untuk menunjukkan contoh-contoh yang tidak menggunakan trik khusus seperti nilai "bawah" atau tipe data yang tak terbatas atau semacamnya.

Kapan konstruktor tipe gagal memiliki instance kelas tipe?

Secara umum, ada dua alasan mengapa konstruktor tipe bisa gagal memiliki turunan dari kelas tipe tertentu:

1. Tidak dapat mengimplementasikan tanda tangan jenis metode yang diperlukan dari kelas tipe.
2. Dapat menerapkan tanda tangan jenis tetapi tidak dapat memenuhi hukum yang disyaratkan.

Contoh jenis pertama lebih mudah daripada jenis kedua karena untuk jenis pertama, kita hanya perlu memeriksa apakah seseorang dapat mengimplementasikan suatu fungsi dengan tipe tanda tangan yang diberikan, sedangkan untuk jenis kedua, kita diharuskan membuktikan bahwa tidak ada implementasi mungkin bisa memenuhi hukum.

Contoh spesifik

• Tipe konstruktor yang tidak dapat memiliki instance functor karena tipe tidak dapat diimplementasikan:

  data F z a = F (a -> z)

Ini adalah contrafunctortor, bukan functor, sehubungan dengan parameter tipe a, karena adalam posisi contravarian. Tidak mungkin untuk mengimplementasikan fungsi dengan tipe tanda tangan (a -> b) -> F z a -> F z b.

• Tipe konstruktor yang bukan merupakan fungsi yang sah meskipun tipe tanda tangan fmapdapat diimplementasikan:

  data Q a = Q(a -> Int, a)
  fmap :: (a -> b) -> Q a -> Q b
  fmap f (Q(g, x)) = Q(\_ -> g x, f x)  -- this fails the functor laws!

Aspek yang menarik dari contoh ini adalah bahwa kita dapat mengimplementasikan fmaptipe yang benar walaupun Ftidak mungkin menjadi functor karena digunakan adalam posisi contravarian. Jadi implementasi yang fmapditunjukkan di atas ini menyesatkan - meskipun memiliki tanda tangan jenis yang benar (saya percaya ini adalah satu-satunya implementasi yang mungkin dari tanda tangan jenis itu), undang-undang functor tidak puas. Misalnya, fmap id≠ id, karena let (Q(f,_)) = fmap id (Q(read,"123")) in f "456"memang 123, tetapi let (Q(f,_)) = id (Q(read,"123")) in f "456"ada 456.

Faktanya, Fini hanya seorang profunctor, - ia bukan functor atau contrafunctor.

• Functor sah yang tidak berlaku karena jenis tanda tangan puretidak dapat diterapkan: mengambil monad Penulis (a, w)dan menghapus kendala yang wseharusnya menjadi monoid. Maka tidak mungkin untuk membangun nilai tipe (a, w)out a.

• Sebuah functor yang tidak aplikatif karena jenis tanda tangan dari <*>kaleng tidak dilaksanakan: data F a = Either (Int -> a) (String -> a).

• Sebuah functor yang tidak sah secara hukum meskipun metode tipe kelas dapat diimplementasikan:

  data P a = P ((a -> Int) -> Maybe a)

Tipe konstruktor Padalah functor karena ahanya digunakan pada posisi kovarian.

instance Functor P where
   fmap :: (a -> b) -> P a -> P b
   fmap fab (P pa) = P (\q -> fmap fab $ pa (q . fab))

Satu-satunya implementasi yang mungkin dari tipe tanda tangan <*>adalah fungsi yang selalu mengembalikan Nothing:

 (<*>) :: P (a -> b) -> P a -> P b
 (P pfab) <*> (P pa) = \_ -> Nothing  -- fails the laws!

Tetapi implementasi ini tidak memenuhi hukum identitas untuk fungsi aplikator.

• Sebuah functor yang ApplicativebukanMonad karena tanda tangan jenis bindtidak dapat diimplementasikan.

Saya tidak tahu contoh seperti itu!

• Sebuah functor yang Applicativetetapi bukanMonad karena hukum tidak dapat dipenuhi meskipun jenis tanda tangan binddapat diterapkan.

Contoh ini telah menghasilkan sedikit diskusi, jadi aman untuk mengatakan bahwa membuktikan contoh ini dengan benar tidak mudah. Tetapi beberapa orang telah memverifikasi ini secara independen dengan metode yang berbeda. Lihat Apakah `data PoE a = Kosong | Pasangkan aa a monad? untuk diskusi tambahan.

 data B a = Maybe (a, a)
   deriving Functor

 instance Applicative B where
   pure x = Just (x, x)
   b1 <*> b2 = case (b1, b2) of
     (Just (x1, y1), Just (x2, y2)) -> Just((x1, x2), (y1, y2))
     _ -> Nothing

Agak sulit untuk membuktikan bahwa tidak ada Monadcontoh yang sah . Alasan untuk perilaku non-monadik adalah bahwa tidak ada cara alami untuk mengimplementasikan bindketika suatu fungsi f :: a -> B bdapat kembali Nothingatau Justuntuk nilai yang berbeda a.

Mungkin lebih jelas untuk mempertimbangkan Maybe (a, a, a), yang juga bukan monad, dan mencoba menerapkannya join. Seseorang akan menemukan bahwa tidak ada cara penerapan yang masuk akal secara intuitif join.

 join :: Maybe (Maybe (a, a, a), Maybe (a, a, a), Maybe (a, a, a)) -> Maybe (a, a, a)
 join Nothing = Nothing
 join Just (Nothing, Just (x1,x2,x3), Just (y1,y2,y3)) = ???
 join Just (Just (x1,x2,x3), Nothing, Just (y1,y2,y3)) = ???
 -- etc.

Dalam kasus yang ditunjukkan oleh ???, tampak jelas bahwa kita tidak dapat memproduksi Just (z1, z2, z3)dengan cara yang masuk akal dan simetris dari enam nilai tipe yang berbeda a. Kita tentu saja dapat memilih subset arbitrer dari enam nilai ini, - misalnya, selalu mengambil nonempty pertama Maybe- tetapi ini tidak akan memenuhi hukum monad. Kembali Nothingjuga tidak akan memenuhi hukum.

• Struktur data seperti pohon yang bukan monad meskipun memiliki asosiatifitas untuk bind- tetapi gagal dalam hukum identitas.

Monad seperti pohon (atau "pohon dengan cabang-cabang berbentuk fungsi") didefinisikan sebagai

 data Tr f a = Leaf a | Branch (f (Tr f a))

Ini adalah monad gratis di atas functor f. Bentuk data adalah pohon di mana setiap titik cabang adalah "functor-ful" dari sub pohon. Pohon biner standar akan diperoleh dengan type f a = (a, a).

Jika kita memodifikasi struktur data ini dengan membuat juga daun dalam bentuk functor f, kita memperoleh apa yang saya sebut "semimonad" - ia memiliki bindyang memenuhi hukum naturalitas dan asosiasi, tetapi puremetodenya gagal dalam salah satu hukum identitas. "Semimonad adalah semigroup dalam kategori endofunctor, apa masalahnya?" Ini adalah kelas tipe Bind.

Untuk mempermudah, saya mendefinisikan joinmetode alih-alih bind:

 data Trs f a = Leaf (f a) | Branch (f (Trs f a))
 join :: Trs f (Trs f a) -> Trs f a
 join (Leaf ftrs) = Branch ftrs
 join (Branch ftrstrs) = Branch (fmap @f join ftrstrs)

Pencangkokan cabang adalah standar, tetapi pencangkokan daun adalah non-standar dan menghasilkan a Branch. Ini bukan masalah bagi hukum asosiatif tetapi melanggar salah satu hukum identitas.

Kapan tipe polinom memiliki turunan monad?

Tak satu pun dari functors Maybe (a, a)dan Maybe (a, a, a)dapat diberikan Monadcontoh yang sah , meskipun mereka jelas Applicative.

Fungsi-fungsi ini tidak memiliki trik - tidak ada Voidatau di bottommana pun, tidak ada kemalasan / keketatan yang rumit, tidak ada struktur tanpa batas, dan tidak ada batasan kelas tipe. Mesin Applicativevirtual benar-benar standar. Fungsi returndan binddapat diterapkan untuk fungsi-fungsi ini tetapi tidak akan memenuhi hukum monad. Dengan kata lain, fungsi-fungsi ini bukan monad karena struktur spesifik tidak ada (tetapi tidak mudah untuk memahami apa yang sebenarnya hilang). Sebagai contoh, perubahan kecil pada functor dapat membuatnya menjadi monad: data Maybe a = Nothing | Just aadalah monad. Functor serupa lainnya data P12 a = Either a (a, a)juga monad.

Konstruksi untuk polinomial monad

Secara umum, berikut adalah beberapa konstruksi yang menghasilkan Monadjenis polinomial yang sah menurut hukum . Dalam semua konstruksi ini, Madalah monad:

1. type M a = Either c (w, a)di mana wada monoid
2. type M a = m (Either c (w, a))di mana mada monad dan wmonoid
3. type M a = (m1 a, m2 a)di mana m1dan m2apa pun monad
4. type M a = Either a (m a)dimanakah mmonad?

Konstruksi pertama adalah WriterT w (Either c), konstruksi kedua adalah WriterT w (EitherT c m). Konstruksi ketiga adalah produk bijak komponen: pure @Mdidefinisikan sebagai produk bijak komponen pure @m1dan pure @m2, dan join @Mdidefinisikan dengan menghilangkan data produk-silang (misalnya m1 (m1 a, m2 a)dipetakan m1 (m1 a)dengan menghilangkan bagian kedua tupel):

 join :: (m1 (m1 a, m2 a), m2 (m1 a, m2 a)) -> (m1 a, m2 a)
 join (m1x, m2x) = (join @m1 (fmap fst m1x), join @m2 (fmap snd m2x))

Konstruksi keempat didefinisikan sebagai

 data M m a = Either a (m a)
 instance Monad m => Monad M m where
    pure x = Left x
    join :: Either (M m a) (m (M m a)) -> M m a
    join (Left mma) = mma
    join (Right me) = Right $ join @m $ fmap @m squash me where
      squash :: M m a -> m a
      squash (Left x) = pure @m x
      squash (Right ma) = ma

Saya telah memeriksa bahwa keempat konstruksi menghasilkan monad yang sah.

Saya menduga bahwa tidak ada konstruksi lain untuk monad polinomial. Sebagai contoh, functor Maybe (Either (a, a) (a, a, a, a))tidak diperoleh melalui konstruksi ini dan tidak monadik. Namun, Either (a, a) (a, a, a)ini monadic karena isomorfik untuk produk dari tiga monads a, adan Maybe a. Juga, Either (a,a) (a,a,a,a)bersifat monadik karena isomorfik dengan produka dan Either a (a, a, a).

Keempat konstruksi yang ditunjukkan di atas akan memungkinkan kami untuk mendapatkan sejumlah produk dalam jumlah berapa pun a, misalnya Either (Either (a, a) (a, a, a, a)) (a, a, a, a, a))dan sebagainya. Semua konstruktor tipe seperti itu akan memiliki (setidaknya satu) Monadinstance.

Masih harus dilihat, kasus penggunaan apa yang mungkin ada untuk monad semacam itu. Masalah lain adalah bahwa Monadturunan yang diturunkan melalui konstruksi 1-4 pada umumnya tidak unik. Sebagai contoh, konstruktor tipe type F a = Either a (a, a)dapat diberikan Monadcontoh dalam dua cara: dengan konstruksi 4 menggunakan monad(a, a) , dan dengan konstruksi 3 menggunakan tipe isomorfisma Either a (a, a) = (a, Maybe a). Sekali lagi, menemukan kasus penggunaan untuk implementasi ini tidak segera jelas.

Sebuah pertanyaan tetap - diberikan tipe data polinomial sewenang-wenang, bagaimana mengenali apakah ia memiliki Monadinstance. Saya tidak tahu bagaimana membuktikan bahwa tidak ada konstruksi lain untuk polinomial monad. Saya tidak berpikir ada teori sejauh ini untuk menjawab pertanyaan ini.