Subyacente Parsec Mónada

Question

Muchos de los combinadores Parsec que uso son de un tipo tal como:

foo :: CharParser st Foo 

CharParser se define here como:

type CharParser st = GenParser Char st 

CharParser es por lo tanto un sinónimo tipo que implica GenParser, en sí definido here como:

type GenParser tok st = Parsec [tok] st 

GenParser es luego otro sinónimo de tipo, asignado usando Parsec, definido here como:

type Parsec s u = ParsecT s u Identity 

Así Parsec es una aplicación parcial de , en sí enumeran here con el tipo:

data ParsecT s u m a 

junto con las palabras :

"ParsecT suma es un analizador con st resma tipo s, estado de usuario tipo u, mónada subyacente y tipo de retorno a. "

¿Cuál es la mónada subyacente? En particular, ¿qué ocurre cuando uso los analizadores CharParser? No puedo ver dónde está insertado en la pila. ¿Existe una relación con el uso de la lista de mónada en Monadic Parsing in Haskell para devolver múltiples análisis exitosos de un analizador ambiguo?

Answer 1

GenParser se define en términos de Parsec, no ParsecT. Parsec a su vez se define como

type Parsec s u = ParsecT s u Identity 

Así que la respuesta es que al usar CharParser la mónada subyacente es la mónada de identidad.

Answer 2

En su caso, la mónada subyacente es Identity. Sin embargo, ParsecT es diferente de la mayoría de los transformadores de mónada en que es una instancia de la clase Monad, incluso si el parámetro de tipo m no lo es. Si observa el código fuente, notará la falta de "(Monad m) =>" en la declaración de la instancia.

Entonces, usted se pregunta: "Si tuviese una pila de mónadas no trivial, ¿dónde se usaría?"

Hay tres respuestas a esta pregunta:

1. Se utiliza para uncons el siguiente token de la corriente:

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

   en cuenta que uncons toma un s (la corriente de tokens t) y devuelve su resultado envuelto en su mónada. Esto le permite a uno hacer algo interesante mientras o incluso durante el proceso de obtener el siguiente token.

2. Se utiliza en la salida resultante de cada analizador.Esto significa que puede crear analizadores sintácticos que no toquen la entrada, sino que tomen medidas en la mónada subyacente y utilicen los combinadores para vincularlos a analizadores sintácticos regulares. En otras palabras, lift (x :: m a) :: ParsecT s u m a.

3. Finalmente, el resultado final de RunParsecT y sus amigos (hasta que se construya hasta el punto en que m se reemplaza por) devuelve sus resultados envueltos en esta mónada.

No existe una relación entre esta mónada y la de Monadic Parsing in Haskell. En este caso, Hutton y Meijer se están refiriendo a la instancia de mónada para ParsecT. El hecho de que en Parsec-3.0.0 y más allá de ParsecT se haya convertido en un transformador de mónada con una mónada subyacente no es relevante para el documento.

Lo que creo que está buscando, sin embargo, es donde fue la lista de resultados posibles. En Hutton y Meijer, el analizador regresa una lista de todos los resultados posibles, mientras que Parsec obstinadamente devuelve solo uno. Creo que estás viendo el m en el resultado y pensando para ti mismo que la lista de resultados debe estar escondida en alguna parte. No lo es.

Parsec, por razones de eficacia, hizo una elección para preferir el primer resultado coincidente en la lista de resultados de Hutton y Meijer. Esto permite descartar los resultados no utilizados en la cola de la lista de Hutton y Meijer y también el frente de la secuencia de tokens porque nunca retrocedemos. En parsec, dado el analizador combinado a <|> b, si a consume cualquier entrada, b nunca será evaluado. La forma de solucionar esto es try, que restablecerá el estado nuevamente donde estaba si a falla y luego evalúa b.

Usted preguntó en los comentarios si esto se hizo usando Maybe o Either. La respuesta es "casi, pero no del todo". Si observas las funciones de palanca baja run*, ves que devuelven un tipo algebraico que indica que la entrada del tiempo fue consumida y luego un segundo que da el resultado o un mensaje de error. Estos tipos funcionan como Either, pero incluso no se usan directamente. En lugar de extender esto más allá, lo referiré a the post por Antoine Latter que explica cómo funciona esto y por qué se hace de esta manera.