Czy można zdefiniować `Komonady` oparte na` Monadach`?

Question

Ok, więc powiedzmy, że masz typ

newtype Dual f a = Dual {dual :: forall r. f(a -> r)->r} 

Jak się okazuje, kiedy f jest Comonad, Dual f jest Monada (zabawa ćwiczenie). Czy działa to na odwrót?

Można zdefiniować fmap ab (Dual da) = Dual $ \fb -> da $ fmap (. ab) fb i extract (Dual da) = da $ return id, ale nie wiem, jak zdefiniować duplicate lub extend.

Czy to możliwe? Jeśli nie, to jaki dowód nie istnieje (czy istnieje szczególny Monad m, dla którego można udowodnić, że Dual m nie jest komonadą)?

Niektóre obserwacje: Dual IO a jest zasadniczo Void (i Const Void jest poprawnym Comonad). Dual m a dla MonadPlus mjestVoid (wystarczy użyć dual mzero). Dual Reader jest Env. Dual Writer to Traced. Dual State jest Store, myślę.

Answer 1

Tak, w rzeczywistości każdy funktor tworzy w ten sposób unikatową kombinację, chyba że f == 0.

Niech F będzie endofunktorem na Hask. Niech

W(a) = ∀r.F(a->r)->r 
W(f) = F(f∗)∗ 
     where g∗(h) = h∘g 

Zagadka staje geometryczny/combinatoric w przyrodzie raz uświadomić sobie następującą izomorfizm:

Twierdzenie 1.

Załóżmy, ani typów (∀rr-> F (r)) (∀rF (r) -> r) jest pusty. Następnie występuje izomorfizm typów W (a) ≃ (∀r.F (r) -> r, a).

Dowód:

class Functor f => Fibration f where 
     projection :: ∀r. f(r)->r 
     some_section :: ∀r. r->f(r) -- _any_ section will work 

to :: forall f a. Fibration f 
     => (∀r.f(a->r) -> r) 
     -> (∀r.f(r)->r, a) 
to(f) = (f . fmap const 
     , f(some_section(id))) 

from :: forall f a. Fibration f 
     => (∀r.f(r)->r, a) 
     -> (∀r.f(a->r) -> r) 
from (π,η) = ev(η) . π 

ev :: a -> (a->b) -> b 
ev x f = f x 

Wypełnienie szczegóły tego (które można zamieścić na życzenie) będzie wymagać trochę parametricity i Yoneda lematu. Kiedy F nie jest Fibracją (jak to zdefiniowałem powyżej), W jest tak banalne, jak to zauważyłeś.

Nazwijmy fibrację okryciem, jeśli odwzorowanie jest unikalne (chociaż nie jestem pewien, czy to użycie jest odpowiednie).

Przyznając twierdzenie, widać W (a) jako współprodukt tematyce jest indeksowany przez _all możliwych fibrations ∀rF (R) -> r, czyli

W(a) ≃ ∐a 
     π::∀f.F(r)->r 

Innymi słowy, funktor W (jako presheaf na Func (Hask)) przyjmuje fumigację i konstruuje z niej kanonicznie trywializowaną przestrzeń krycia.

Jako przykład niech F (a) = (Int, a, a, a). Następnie mamy trzy oczywiste naturalne fibracje F (a) -> a. Pisanie koproduktu o + następujący schemat wraz z powyższego twierdzenia powinny być nadzieją na tyle, aby opisać comonads konkretnie:

  a 
     ^
      | ε 
      | 
     a+a+a 
     ^|^
    Wε | |δ | εW 
     | v | 
(a+a+a)+(a+a+a)+(a+a+a) 

Więc counit jest wyjątkowy.Przy użyciu oczywistych wskaźników do współproduktu, mapy Wε (i, j) do j, mapy εW (i, j) do i. Więc δ musi być unikalną "diagonalną" mapą, a mianowicie δ (i) == (i, i)!

Twierdzenie 2.

Niech F będzie Falifikacją i niech ΩW będzie zbiorem wszystkich komonads z podstawowym funktorem W. Następnie ΩW≃1.

(Niestety nie mam sformalizowane dowód.)

Analogiczny kombinatoryczne argumentem za zestaw monad uW byłoby interesujące zbyt, ale w tym przypadku uW nie może być pojedyncza. (Należy wziąć pewnej stałej C i zestaw Ti: 1-> c i | j (i, j) = l + jc).

Uwaga że monads/comonads tak są skonstruowane, że nie Podwójne pierwotnych comonads/monadach ogólnie. Na przykład niech M będzie monadą (F (a) = (Int, a), η (x) = (0, x), μ (n, (m, x)) = (n + m, x)) , czyli Writer. Naturalna projekcja jest wyjątkowa, stąd twierdzenie W (a) ≃a, i nie ma sposobu na poszanowanie oryginalnej algebry.

Należy również zauważyć, że komonad jest trywialnie Fibration (na wiele różnych sposobów), chyba że Void, i dlatego masz Monadę z Comonada (ale to niekoniecznie jest unikalne!).

Kilka uwag o swoich obserwacjach:

• Dual IO a jest zasadniczo brak

  O ile mi wiadomo, w Haskell IO jest zdefiniowany coś takiego:

  -- ghc/libraries/ghc-prim/GHC/Types.hs 
  newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #)) 
  

  co oznacza, ze sama teoria typu odpowiadająca warstwa pokrywająca jest unikalną kanoniczną przestrzenią pokrywającą indeksowaną przez wszystkie State# RealWorld s. To, czy możesz (lub powinieneś) odrzucić to prawdopodobnie pytanie filozoficzne, a nie techniczne.

• MonadPlus m => Dual m a jest nieważna

  Tak, ale należy pamiętać, że jeśli F (a) = 0 Then W (a) = 1 i nie jest to comonad (bo inaczej counit oznaczałoby typu W (0) -> 0 ≃ 1-> 0). Jest to jedyny przypadek, w którym W nie może być nawet banalną komonadą, biorąc pod uwagę arbitralnego funktora.

• Dual Reader jest .. Te oświadczenia będą czasem poprawne, czasami nie. Zależy od tego, czy (ko) algebra interesów zgadza się z (bi) algebrą pokrycia.

Jestem zaskoczony, jak interesująco jest geometryczny Haskell! Sądzę, że może istnieć wiele podobnych konstrukcji geometrycznych. Na przykład naturalną uogólnieniem tego byłoby rozważenie "kanonicznej trywializacji" F-> G dla niektórych kowariancyjnych funktorów F, G. Wówczas grupa automorfizmu dla przestrzeni bazowej nie byłaby już banalna, więc aby to właściwie zrozumieć, potrzebna byłaby nieco większa teoria.

Wreszcie, tutaj jest dowód kodu koncepcyjnego. Dzięki za wspaniały orzeźwiający układanki, i mają bardzo Wesołych świąt ;-)

{-# LANGUAGE RankNTypes #-} 
{-# LANGUAGE ScopedTypeVariables #-} 

import Control.Comonad 

class Functor f => Fibration f where 
     x0 :: f() 
     x0 = some_section() 

     some_section :: forall r. r -> f(r) 
     some_section x = fmap (const x) x0 

     projection :: forall r. f(r) -> r 

newtype W f a = W { un_w :: forall r. f(a->r)->r } 

instance Functor f => Functor (W f) where 
     fmap f (W c) = W $ c . fmap (. f) 

instance Fibration f => Comonad (W f) where 
     extract = ε 
     duplicate = δ 

-- The counit is determined uniquely, independently of the choice of a particular section. 
ε :: forall f a. Fibration f => W f a -> a 
ε (W f) = f (some_section id) 

-- The comultiplication is unique too. 
δ :: forall f a. Fibration f => W f a -> W f (W f a) 
δ f = W $ ev(f) . un_w f . fmap const 

ev :: forall a b. a -> (a->b)->b 
ev x f = f x 

-- An Example 
data Pair a = P {p1 ::a 
       ,p2 :: a 
       } 
       deriving (Eq,Show) 

instance Functor Pair where 
     fmap f (P x y) = P (f x) (f y) 

instance Fibration Pair where 
     x0 = P()() 
     projection = p1 

type PairCover a = W Pair a 

-- How to construct a cover (you will need unsafePerformIO if you want W IO.) 
cover :: a -> W Pair a 
cover x = W $ ev(x) . p1