Comonad funzione

Question

duplicare Perché quando si definisce la funzione duplicato

duplicate :: w a -> w (w a)  

per il typeclass Comonad (link) è necessario modificare tutti gli elementi "nel contesto" (cioè modificare elementi diversi rispetto alla corrente valore del contesto). Perché non usare semplicemente qualcosa come restituire in una Monade?

Esempio (zip):

data Z a = Z [a] a [a]  

perché non posso semplicemente definire duplicato come

duplicate z = Z [] z []  

ho cercato di ricavare un requisito per la duplicare funzione dalle regole Comonad, ma ho sempre finire con un duplicato che avvolge l'elemento in modo molto simile a restituendo in una monade senza bisogno di fare altro.

Uno blog post dice:

duplicato è un po 'più difficile da afferrare. Da una lista di cerniere, dobbiamo costruire una lista di cerniere lampo di lista. Il significato dietro questo (confermata dalle leggi comonad che ogni istanza deve soddisfare) è che lo spostamento all'interno della struttura duplicato restituisce la struttura originale, alterato dalla stessa mossa

Ma io non capisco perché deve essere quel modo. Il FMAP nelle regole Comonad vale sempre per l'elemento avvolto e poi questo elemento è sempre "da scartare" con estratto, perché preoccuparsi di fare qualsiasi altra cosa al duplicato funzione diversa solo avvolgendo l'argomento del duplicare ?

Puoi indicare cosa mi sono perso? Mi sento come se avessi fatto qualche ovvio errore da qualche parte, ma non riesco a capirlo da solo.

Grazie in anticipo per le vostre risposte!

Answer 1

È importante se si possono fare altre cose con il tipo di quello semplicemente extract da esso. Intuitivamente, se l'unica cosa che puoi fare è estrarre il valore, il tipo mantiene solo un valore, quindi duplicare quell'unico valore è duplicare tutto. Questo non è vero in generale, e non è vero per le chiusure lampo.

Le leggi Comonad sono solo le leggi di categoria sotto mentite spoglie sulle funzioni del tipo w a -> b. Poiché questi provengono da categorie, potrebbe essere più facile ragionarli in termini di categoria rispetto a quanto previsto dalle leggi Comonad. extract è l'identità di questa categoria e =<= è l'operatore di composizione.

-- | Right-to-left 'Cokleisli' composition 
(=<=) :: Comonad w => (w b -> c) -> (w a -> b) -> w a -> c 
f =<= g = f . extend g 

Sappiamo anche che extend f = fmap f . duplicate, in modo che possiamo scrivere

f =<= g = f . fmap g . duplicate 

Questo sembra abbastanza facile da ragionare su.Ora, equipaggiamo il tuo tipo Z con un'altra funzione di cui possiamo parlare. isFirst restituirà true solo quando Z rappresenta un valore in una posizione in un elenco con niente prima di esso.

isFirst :: Z a -> Bool 
isFirst (Z [] _ _) = True 
isFirst _   = False 

Ora, consideriamo che cosa accade quando usiamo isFirst con le tre leggi di categoria. Gli unici due che sembrano essere immediatamente applicabili ad esso sono che extract è un'identità sinistra e destra per composizione da =<=. Dal momento che stiamo solo smentendo questo, abbiamo solo bisogno di trovare un contro-esempio. Sospetto che uno di extract =<= isFirst o isFirst =<= extract non riuscirà per l'input Z [1] 2 []. Entrambi devono essere gli stessi di isFirst $ Z [1] 2 [], ovvero False. Proveremo prima il extract =<= isFirst, che capita di risolvere.

extract =<= isFirst    $ Z [1] 2 [] 
extract . fmap isFirst . duplicate $ Z [1] 2 [] 
extract . fmap isFirst $ Z []   (Z [1] 2 []) [] 
extract    $ Z [] (isFirst (Z [1] 2 [])) [] 
extract    $ Z [] False     [] 
           False 

Quando cerchiamo isFirst =<= extract non saremo così fortunati.

isFirst =<= extract    $ Z [1] 2 [] 
isFirst . fmap extract . duplicate $ Z [1] 2 [] 
isFirst . fmap extract $ Z []   (Z [1] 2 []) [] 
isFirst    $ Z [] (extract (Z [1] 2 [])) [] 
isFirst    $ Z [] 2      [] 
True 

Quando abbiamo duplicate d abbiamo perso informazioni sulla struttura. In effetti, abbiamo perso le informazioni su tutto ciò che veniva ovunque, tranne il singolo punto focale della cerniera. Il corretto duplicate avrebbe un intero 'nother zipper ovunque nel contesto che contiene il valore in quella posizione e il contesto di quella posizione.

Vediamo cosa possiamo dedurre da queste leggi. Con una piccola lancetta sulla categoria delle funzioni, possiamo vedere che =<= extract è fmap extract . duplicate e questa deve essere la funzione di identità. Apparentemente sto riscoprendo come sono scritte le leggi nella documentazione di Control.Category. Questo ci permette di scrivere qualcosa di simile

z = (=<= extract)    z 
z = fmap extract . duplicate $ z 

Ora, z ha un solo costruttore, in modo che possiamo sostituire che nel

Z left x right = fmap extract . duplicate $ Z left x right 

Da che tipo di duplicato, sappiamo che deve restituire lo stesso costruttore.

Z left x right = fmap extract $ Z lefts (Z l x' r) rights 

Se applichiamo fmap a questo Z abbiamo

Z left x right = Z (fmap extract lefts) (extract (Z l x' r)) (fmap extract rights) 

Se ci dividiamo questo dalle parti del costruttore Z abbiamo tre equazioni

left = fmap extract lefts 
x = extract (Z l x' r) 
right = fmap extract rights 

Questo ci dice che per lo meno il risultato di duplicate (Z left x right) deve contenere:

• una lista con la stessa lunghezza left per il lato sinistro
• un Z con x in mezzo per mezzo
• una lista con la stessa lunghezza right per il lato destro

Inoltre, possiamo vedere che i valori medi negli elenchi sul lato sinistro e destro devono essere uguali ai valori originali in tali elenchi.Considerando solo questa legge, sappiamo abbastanza da richiedere una struttura diversa per il risultato di duplicate.