Posso modellare un elenco di successi con errori di cortocircuito tramite la composizione di funtori applicativi?

Question

L'utente 'singpolyma' asked on reddit se ci fosse qualche struttura generale sottostante:

data FailList a e = Done | Next a (FailList a e) | Fail e 

una monade libera è stato suggerito, ma mi chiedevo se questo potrebbe essere modellato più in generale tramite funtori applicative. In Abstracting with Applicatives, Bazerman ci mostra che la somma di due funtori applicativi è anche un funtore applicativo, con distorsione a sinistra/a destra, a condizione che abbiamo una trasformazione naturale nella direzione del bias. Sembra che sia ciò di cui abbiamo bisogno! Così, ho iniziato la mia proposta, ma poi ho incontrato rapidamente problemi. Qualcuno può vedere soluzioni a questi problemi ?:

---

In primo luogo, iniziamo con la definizione della somma di due funtori. Ho iniziato qui perché vogliamo modellare i tipi di somma: successi o successi e un fallimento.

data Sum f g a = InL (f a) | InR (g a) 

E i due funtori che vogliamo lavorare con sono:

data Success a = Success [a] 
data Failure e a = Failure e [a] 

Success è semplice - è essenzialmente Const [a]. Tuttavia, Failure e non ne sono così sicuro. Non è un functor applicativo, perché pure non ha alcuna definizione. E ', tuttavia, un'istanza di Apply:

instance Functor Success where 
    fmap f (Success a) = Success a 

instance Functor (Failure e) where 
    fmap f (Failure e a) = Failure e a 

instance Apply (Failure e) where 
    (Failure e a) <.> (Failure _ b) = Failure e a 

instance Apply Success where 
    (Success a) <.> (Success b) = Success (a <> b) 

instance Applicative Success where 
    pure = const (Success []) 
    a <*> b = a <.> b 

Avanti, possiamo definire la somma di questi funtori, con una trasformazione naturale da destra a sinistra (quindi una polarizzazione sinistra):

instance (Apply f, Apply g, Applicative g, Natural g f) => Applicative (Sum f g) where 
    pure x = InR $ pure x 
    (InL f) <*> (InL x) = InL (f <*> x) 
    (InR g) <*> (InR y) = InR (g <*> y) 
    (InL f) <*> (InR x) = InL (f <.> eta x) 
    (InR g) <*> (InL x) = InL (eta g <.> x) 

E l'unica cosa che dobbiamo fare ora è definire la nostra trasformazione naturale, ed è qui che tutto viene a crollare.

instance Natural Success (Failure e) where 
    eta (Success a) = Failure ???? a 

L'incapacità di creare un Failure sembra essere il problema. Inoltre, anche l'hacky e l'uso di ⊥ non sono un'opzione, perché questo sarà valutato, nel caso in cui si disponga di InR (Success ...) <*> InL (Failure ...).

Mi sento come se mi mancasse qualcosa, ma non ho idea di cosa sia.

Questo può essere fatto?

Answer 1

Sono quasi sicuro che la risposta "corretta" è quella di rendere e un monoid, proprio come non ti piaceva l'idea sulla discussione reddit.

Considerare Failure "oops" [(*1),(*2),(*3)] <*> Failure "doh" [1,2,3] Il risultato dovrebbe avere "oops" o "doh" come errore?Facendo il e un monoide catturiamo il fatto che non c'è scelta canonica, e lasciare che il consumatore scegliere il loro veleno (sia esso First, Last, [], etc.)

Si noti che questa soluzione, molto simile al (Maybe e, [a]) di rappresentanza, non tratta correttamente con i dati di streaming/potenzialmente infiniti, dal momento che è severo stabilire se abbiamo un errore che termina la lista.

Una codifica diversa utilizza i punti di riferimento degli applicativi, come da post successivo (http://comonad.com/reader/2013/algebras-of-applicatives/).

Poi si prende la rappresentazione lista presentata lì (FixF (ProductF Embed (Sum (Const()))) a) e modificarlo attaccando il tuo monoid errore nella posizione unità, per ottenere quanto segue:

Monid mon => FixF (ProductF Embed (Sum (Const mon))) a

e si noti che è possibile utilizzare un Maybe invece di un monoide per ottenere esattamente a FailList, ma proprio come con FailList non si ottiene un'istanza applicativa gratuitamente a meno che non si scriva uno che specifica il modo giusto per combinare gli errori.

Si noti inoltre che con l'approccio punto fisso se abbiamo l'equivalente di Success [(*1),(*2),(*3)] <*> Failure "doh" [1,2,3,4,5] poi torniamo un Success con tre elementi (cioè siamo nonstrict veramente in fallimento), mentre l'approccio suggerisci, torniamo un Failure con tre elementi e l'errore dalla lista di errori di cinque elementi. Tali sono i compromessi dello streaming rispetto al rigoroso.

Infine, e in modo molto semplice, possiamo semplicemente prendere type FailList e = Product (Const (First e)) ZipList per utilizzare un macchinario applicativo standard e ottenere qualcosa di molto vicino al tipo di dati originale.

Answer 2

{-# LANGUAGE FlexibleInstances #-} 

instance Applicative (Sum Success (Failure e)) where 
    pure x = InL $ pure x 
    (InL f) <*> (InL x) = InL (f <*> x) 
    (InR (Failure e fs)) <*> (InR (Failure _ gs)) = InR (Failure e (fs <*> gs)) 
    (InR (Failure e fs)) <*> (InL (Success gs)) = InR (Failure e (fs <*> gs)) 
    (InL (Success gs)) <*> (InR (Failure e fs)) = InR (Failure e (gs <*> fs)) 

Questo perché si può sempre aggiungere un guasto a un elenco di successi;)

È inoltre possibile utilizzare questa classe tipo, invece di Natural f g:

class Transplant f g where 
    transplant :: f a -> g b -> f b 

instance Transplant (Failure e) Success where 
    transplant (Failure e _) (Success a) = Failure e a 

non hanno idea di che cosa significa teoria di categoria-saggio.