Sottostante Parsec Monade

Question

Molti dei combinatori Parsec che uso sono di tipo quali:

foo :: CharParser st Foo 

CharParser è definito here come:

type CharParser st = GenParser Char st 

CharParser è quindi un tipo sinonimi coinvolge GenParser, si definito come:

type GenParser tok st = Parsec [tok] st 

GenParser è poi un altro tipo sinonimi, assegnato attraverso Parsec, definita here come:

type Parsec s u = ParsecT s u Identity 

Quindi Parsec è un'applicazione parziale di , stesso elencato here con Tipo:

data ParsecT s u m a 

insieme alle parole :

"ParsecT suma è un parser con st tipo risma, tipo stato utente u, sottostante monad m e tipo di ritorno a. "

Qual è la monade sottostante? In particolare, cosa succede quando uso i parser CharParser? Non riesco a vedere dove è inserito nello stack. Esiste una relazione con l'uso della lista monad in Monadic Parsing in Haskell per restituire più risultati positivi da un parser ambiguo?

Answer 1

GenParser è definito in termini di Parsec, non di ParsecT. Parsec a sua volta, è definito come

type Parsec s u = ParsecT s u Identity 

Quindi la risposta è che quando si utilizza CharParser monade di fondo è la monade di identità.

Answer 2

Nel tuo caso la monade sottostante è Identity. Tuttavia ParsecT è diverso dalla maggior parte dei trasformatori monad in quanto è un'istanza della classe Monad anche se il parametro type m non lo è. Se si guarda il codice sorgente si noterà la mancanza di "(Monad m) =>" nella dichiarazione di istanza.

Quindi ti chiedi: "Se avessi uno stack monad non banale, dove verrebbe usato?"

Ci sono tre risposte a questa domanda:

1. E 'usato per uncons il token successivo dal flusso:

   class (Monad m) => Stream s m t | s -> t where 
       uncons :: s -> m (Maybe (t,s)) 
   

   noti che uncons prende un s (il flusso di token t) e restituisce il risultato avvolto nella tua monade. Ciò consente di fare cose interessanti durante o anche durante il processo di ottenere il prossimo token.

2. Viene utilizzato nell'output risultante di ciascun parser.Ciò significa che è possibile creare parser che non tocchino l'input ma agiscano nella monade sottostante e utilizzino i combinatori per collegarli a parser regolari. In altre parole, lift (x :: m a) :: ParsecT s u m a.

3. Infine, il risultato finale di RunParsecT e degli amici (finché non si accumula fino al punto in cui m è stato sostituito da Identity) restituiscono i risultati racchiusi in questa monade.

Non esiste una relazione tra questa monade e quella di Monadic Parsing in Haskell. In questo caso, Hutton e Meijer si riferiscono all'istanza monad per ParsecT stesso. Il fatto che in Parsec-3.0.0 e oltre ParsecT sia diventato un trasformatore monade con una monade sottostante non è rilevante per la carta.

Quello che penso tu stia cercando, tuttavia, è dove l'elenco di risultati possibili è andato. In Hutton e Meijer il parser restituisce un elenco di tutti i possibili risultati mentre Parsec restituisce testardamente solo uno. Penso che tu stia vedendo il m nel risultato e pensando a te stesso che l'elenco dei risultati deve nascondersi da qualche parte. Non è.

Parsec, per motivi di efficienza, ha scelto di preferire il primo risultato di corrispondenza nell'elenco dei risultati di Hutton e Meijer. Questo butta via entrambi i risultati inutilizzati nella coda della lista di Hutton e Meijer e anche il fronte del flusso di gettoni perché non torniamo indietro. In parsec, dato il parser combinato a <|> b, se a consuma qualsiasi input b non verrà mai valutato. Il modo per aggirare questo è try che ripristinerà lo stato di nuovo dove era se a fallisce quindi valutare b.

Nei commenti è stato chiesto se l'operazione è stata eseguita utilizzando Maybe o Either. La risposta è "quasi ma non del tutto". Se osservate le funzioni della leva bassa run*, vedete che restituiscono un tipo algebrico che indica che l'input del tempo è stato consumato, quindi un secondo che fornisce il risultato o un messaggio di errore. Questi tipi funzionano come Either, ma anche se non vengono utilizzati direttamente. Piuttosto, espanderlo ulteriormente, ti riferirò a the post di Antoine Latter che spiega come funziona e perché è fatto in questo modo.