Puoi definire `Comonads 'basato su` Monads`?

Question

Okay, diciamo che avete il tipo

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

Come si è visto, quando f è un Comonad, Dual f è una Monade (divertente esercizio). Funziona il contrario?

È possibile definire fmap ab (Dual da) = Dual $ \fb -> da $ fmap (. ab) fb e extract (Dual da) = da $ return id, ma non so come definire duplicate o extend.

È possibile? In caso contrario, quale prova non c'è (c'è un particolare Monad m per il quale è possibile dimostrare che Dual m non è una comonad)?

Alcune osservazioni: Dual IO a è essenzialmente Void (e Const Void è una valida Comonad). Dual m a per MonadPlus mèVoid (utilizzare solo dual mzero). Dual Reader è Env. Dual Writer è Traced. Dual State è Store, penso.

Answer 1

Sì, in effetti qualsiasi functor genera una comonad unica in questo modo, a meno che f == 0.

Sia F un endofunctor su Hask. Lasciate

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

Il puzzle diventa geometrica/combinatoria in natura una volta che ci si rende conto quanto segue isomorfismo:

Teorema 1.

Supponiamo nessuno dei due tipi (∀rr-> F (r)) (∀rF (r) -> r) è vuoto. Poi c'è un isomorfismo dei tipi W (a) ≃ (∀r.F (r) -> r, a).

Dimostrazione:

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 

Riempire i dettagli di questo (che posso inviare su richiesta) richiederà un po 'di parametricity e Yoneda lemma. Quando F non è una Fibrazione (come sopra definito), W è banale come hai osservato.

Chiamiamo una fibrazione una copertura se la proiezione è unica (anche se non sono sicuro che questo uso sia appropriato).

Ammettendo teorema, si può vedere W (a) come coprodotto di un indicizzata dalla _tutti possibili fibrazioni ∀rF (r) -> R, cioè

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

In altre parole, il funtore W (come un presheaf su Func (Hask)) prende una fibrazione e costruisce da esso uno spazio di copertura canonicamente banalizzato.

Ad esempio, sia F (a) = (Int, a, a, a). Quindi abbiamo tre evidenti fibrazioni naturali F (a) -> a. Scrivere il coprodotto dal +, il seguente schema insieme con il teorema di cui sopra dovrebbe auspicabilmente essere sufficiente per descrivere le comonads concretamente:

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

Così il counit è unico.Utilizzando indici evidenti nel coprodotto, le mappe Wε (i, j) in j, εW (i, j) in i. Quindi δ deve essere l'unica mappa 'diagonale', cioè δ (i) == (i, i)!

Teorema 2.

Sia f un fibrazione e sia ΩW tramite l'insieme di tutti comonads con funtore sottostante W. Quindi ΩW≃1.

(Scusate non ho formalizzato la prova.)

Un argomento combinatorio analogo per l'insieme di monadi uW sarebbe troppo interessante, ma in questo caso uW potrebbe non essere un singleton. (Prendete un po 'costante c e impostare η: 1-> c e μ (i, j) = i + JC.)

Si noti che le monadi/comonads così costruite sono non i duali alle originali comonads/monadi in generale. Per esempio sia M una monade (F (a) = (Int, a), η (x) = (0, x), μ (n, (m, x)) = (n + m, x)) , ovvero a Writer. La proiezione naturale è unica quindi dal teorema W (a) ≃a, e non c'è modo di rispettare l'algebra originale.

Nota anche che una comonade è banalmente una Fibrazione (probabilmente in molti modi diversi) a meno che non sia Void, motivo per cui hai ottenuto un Monade da una Comonade (ma non è necessariamente unico!).

Alcuni commenti circa le vostre osservazioni:

• Dual IO a è essenzialmente Void

  qualcosa Per quanto ne so, in Haskell IO è definito come:

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

  che significa da solo la teoria del tipo la copertura corrispondente è l'unico spazio di copertura canonico indicizzato da tutti gli State# RealWorld s. Se è possibile (o dovrebbe) rifiutare questa è probabilmente una questione filosofica, piuttosto che tecnica.

• MonadPlus m => Dual m a è nullo

  Giusto, ma si noti che se F (a) = 0 allora W (a) = 1 e non è un comonad (perché altrimenti il ​​counit implicherebbe il tipo W (0) -> 0 ≃ 1-> 0). Questo è l'unico caso in cui W non può nemmeno essere una banale comonade data un functor arbitrario.

• Dual Reader è .. Tali dichiarazioni a volte sono corrette, a volte no. Dipende dal fatto che la (co) algebra di interesse sia d'accordo con la (bi) algebra dei rivestimenti.

Quindi sono sorpreso di quanto sia davvero interessante Haskell! Immagino che ci possano essere moltissime costruzioni geometriche simili a questa. Ad esempio una generalizzazione naturale di questo sarebbe considerare la 'banalizzazione canonica' di F-> G per alcuni funtori covarianti F, G. Quindi il gruppo di automorfismi per lo spazio di base non sarebbe più banale, quindi sarebbe necessario un po 'più di teoria per capire correttamente questo.

Infine, ecco una prova di codice concettuale. Grazie per un grande puzzle rinfrescante, e hanno un Buon Natale ;-)

{-# 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